← 返回题目列表

AtCoder · joi2010ho_a

A. 旅行者

中文机器翻译题面 查看原题

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

旅人 - 原题 PDF 第 1 页
原题PDF第1页
旅人 - 原题 PDF 第 2 页
原题PDF第2页
旅人 - 原题 PDF 第 3 页
原题PDF第3页
旅人 - 原题 PDF 第 4 页
原题PDF第4页
可复制的 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