AT_joi2010yo_b すごろく题解-创锋一号

AT_joi2010yo_b すごろく

题目描述

Link: https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_b

JOI さんは一人ですごろく遊びをしている．このすごろくには一直線上にN NN個のマスがあり，それぞれ移動の指示が書かれている．スタート地点は1 11マス目であり，ゴールはN NNマス目である．JOI さんはゴールするまで次を繰り返す．

サイコロを振って出た目の数だけ現在のマスから進み，そのマスの指示に従う．指示に従って移動した先のマスの指示には従わない．

ちょうどN NNマス目に止まる時だけでなく，移動先がN NNマス目を超える場合もゴールとなる．

すごろくの盤面と，M MM回分のサイコロの出る目が与えられたとき，サイコロを何回振ったところでゴールするかを出力するプログラムを作成せよ．

输入格式

入力は1 + N + M 1\ +\ N\ +\ M1+N+M行からなる．

入力の1 11行目には2 22つの整数N , M N,MN,M(2 ≦ N ≦ 1 000 2\ \leqq\ N\ \leqq\ 1\,0002≦N≦1000，1 ≦ M ≦ 1 000 1\ \leqq\ M\ \leqq\ 1\,0001≦M≦1000) が空白を区切りとして書かれている．N NNはすごろくのマス目の個数を，M MMは与えられるサイコロの目の個数を表す．

続く $ N $ 行には− 999 -999−999以上999 999999以下の整数が１つずつ書かれている．1 + i 1+i1+i行目 (1 ≦ i ≦ N 1\ \leqq\ i\ \leqq\ N1≦i≦N) の整数は，すごろくのi ii番目のマスの指示を表す．書かれている整数を $ X $ とする．X = 0 X\ =\ 0X=0のときは「何もしない」を，$ X\ >\ 0 $ のときは「$ X $ マス進む」を，X < 0 X\ <\ 0X<0のときは「∣ X ∣ |X|∣X∣マス戻る」の指示を表す．ただし，∣ X ∣ |X|∣X∣はX XXの絶対値を表す．

続くM MM行には1 11以上6 66以下の整数が1 11つずつ書かれており，1 + N + j 1\ +\ N\ +\ j1+N+j行目 (1 ≦ j ≦ M 1\ \leqq\ j\ \leqq\ M1≦j≦M) の数は $ j $ 回目に出るサイコロの目を表す．

ただし，2 22行目と1 + N 1\ +\ N1+N行目の数は必ず0 00である．1 11マス目よりも前のマスに移動させる指示が書かれているマスはない．また，どの採点用入力データにおいてもサイコロを振る回数がM MM以下でゴールできる．

输出格式

出力は，サイコロを何回振ったところでゴールするかを表す整数のみを含む1 11行からなる．

输入输出样例 #1

输入 #1

10 5 0 0 5 6 -3 8 1 8 -4 0 1 3 5 1 5

输出 #1

输入输出样例 #2

输入 #2

10 10 0 -1 -1 4 4 -5 0 1 -6 0 1 5 2 4 6 5 5 4 1 6

输出 #2

Solution

分析

本题数据范围不大，因此直接按照题意模拟即可。

根据题意，a , b a,ba,b表示两个数列，t tt表示当前的累计结果，初始值为1 11。运行过程中，每轮循环中t tt先加上b i b_ibi然后再加上a t a_tat（注意这里的t tt是新的t tt），然后判断是否大于n nn，如果大于n nn，那么就输出i ii的值，否则继续新一轮循环。

需要注意的是：

增加b i b_ibi和增加a t a_tat两个操作之间具有先后关系，因此直接写作t+=b[i]+a[t]是错误的，如果要合并成一条语句，应写为t+=b[i]+a[t+b[i]]；
记得最后输出换行符。

代码

#include<cstdio>intn,m,t=1,a[1004],b[1004];intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i+=1)scanf("%d",&a[i]);for(inti=1;i<=m;i+=1)scanf("%d",&b[i]);for(inti=1;i<=n;i+=1){t+=b[i]+a[t+b[i]];if(t>=n){printf("%d\n",i);return0;}}}

企业官网建设流程全解析