以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
第9回日本情報オリンピック本選問題1
2010年2月14日
受験生への注意事項
• 試験開始の指示のあるまで, 問題が入った封筒を開けないで下さい.
• 問題は5 問, 試験時間は4 時間(10 時~14 時)です.
• 提出方法や注意事項はoverview sheet に記述されています.
• home directory にjoi2010 というdirectory が存在します.その下に2010-ho-t1,
2010-ho-t2, 2010-ho-t3, 2010-ho-t4, 2010-ho-t5 の5つのdirectory が作成
されます.解答はこれらのdirectory で,overview sheet の指示に従い行ってく
ださい.また,これらのdirectory には,各問の
– 入力データ例とその入力に対する正解出力データ
– 採点時と同じ方法でコンパイルするスクリプト
– 上のスクリプトでコンパイルしたプログラムを,指定した入力データ例
に対して実行するスクリプト
– 上のスクリプトでコンパイルしたプログラムを,指定した入力データ例
に対して実行しその出力を正解と比較するスクリプト
があります.
情報オリンピック日本委員会
1Copyright c⃝2010 The Japanese Committee for International Olympiad in Informatics
著作権は情報オリンピック日本委員会に帰属します.
1 旅人
問題
あなたはJOI 街道を旅する旅人である.JOI 街道は東西にまっすぐに延びた道路で,
JOI 街道上にはn 個の宿場町がある.宿場町には西から東の順に1 からn までの番
号が付けられている.JOI 街道上の最も西の宿場町が宿場町1 であり,最も東の宿場
町が宿場町n である.
あなたは,宿場町1 から出発してm 日間の旅に出ることになった.あなたの旅程
は数列a1, a2, . . . , am に従い,次のように決められている.ai はi 日目の移動方法を
表す0 ではない整数である.i 日目にあなたが出発する宿場町を宿場町k とおくと,
i 日目にあなたは宿場町k から宿場町k + ai までまっすぐに移動することを意味する.
宿場町の個数n,旅の日数m,宿場町間の距離の情報と,移動方法を表す数列
a1, a2, . . . , am が与えられたとき,m 日間の旅におけるあなたの移動距離の合計を
100000 = 105 で割った余りを求めるプログラムを作成せよ.
入出力の例に対応する図
宿場町3 宿場町6
宿場町1 宿場町2 宿場町4 宿場町5 宿場町7
西 東
2 1 1 3 2 1
1 日目 a1 = 2
2 日目 a2 = −1
3 日目 a3 = 3
4 日目 a4 = 2
5 日目 a5 = −3
問題1-1
入力
入力ファイルのファイル名はinput.txt である.
1 行目には整数n, m が空白区切りで書かれている.n (2 ≦n ≦100000 = 105) は
JOI 街道上の宿場町の個数を,m (1 ≦m ≦100000 = 105) は旅の日数を表す.
続くn −1 行はJOI 街道上の宿場町間の距離を表す.i + 1 行目(1 ≦i ≦n −1) に
は宿場町i と宿場町i + 1 の距離を表す正整数si (1 ≦si ≦100) が書かれている.
続くm 行にはm 日間の移動方法を表す数列が書かれている.i+n 行目(1 ≦i ≦m)
にはi 日目のあなたの移動方法を表す0 ではない整数ai が書かれている.
採点用データにおいて,宿場町1 より西に移動することや,宿場町n より東に移
動することはない.
採点用データのうち,配点の50% 分については,n ≦100 かつm ≦100 を満たす.
出力
出力ファイルのファイル名はoutput.txt である.
output.txt は,m 日間の旅におけるあなたの移動距離の合計を100000 = 105 で
割った余りを含む1 行からなる.
問題1-2
入出力の例
input.txt
7 5
2
1
1
3
2
1
2
-1
3
2
-3
output.txt
18
1 日目に,あなたは宿場町1 から宿場町3 まで移動する.2 日目に,あなたは宿場
町3 から宿場町2 まで移動する.そして,3 日目に宿場町2 から宿場町5 まで移動
し,4 日目に宿場町5 から宿場町7 まで移動し,5 日目に宿場町7 から宿場町4 ま
で移動する.5 日間の旅におけるあなたの移動距離の合計は18 である.
宿場町3 宿場町6
宿場町1 宿場町2 宿場町4 宿場町5 宿場町7
西 東
2 1 1 3 2 1
1 日目 a1 = 2
2 日目 a2 = −1
3 日目 a3 = 3
4 日目 a4 = 2
5 日目 a5 = −3
入出力の例に対応する図(再掲)
問題1-3