首页 > 试题广场 >

CodeForces 13E Holes

[编程题]CodeForces 13E Holes

热度指数：4 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are N holes located in a single row and numbered from left to right with numbers from 1 to N . Each hole has it's own power (hole number i has the power a _i ). If you throw a ball into hole i it will immediately jump to hole i + a _i , then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M moves the player can perform one of two actions:

Set the power of the hole a to value b .
Throw a ball into the hole a and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row.

Petya is not good at math, so, as you have already guessed, you are to perform all computations.

输入描述:

The first line contains two integers N and M (1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M lines describe moves made by Petya. Each of these line can be one of the two types:

Type 0 means that it is required to set the power of hole a to b, and type 1 means that it is required to throw a ball into the a-th hole. Numbers a and b are positive integers do not exceeding N.

输出描述:

For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

示例1

输入

8 5<br />1 1 1 1 1 2 8 2<br />1 1<br />0 1 3<br />1 1<br />0 3 4<br />1 2<br />

输出

8 7<br />8 5<br />7 3<br />

算法知识视频讲解

Disconnect


	import java.util.*;



	public class Main {
 public static void main(String[] args)
 {
  int n,m;
  String[] tmpStrings;
  Scanner scanner = new Scanner(System.in);
  tmpStrings = scanner.nextLine().split(" ");
  n = Integer.parseInt(tmpStrings[0]);
  m = Integer.parseInt(tmpStrings[1]);
  int[] row = new int[n+1];
  int step,hole;
  tmpStrings = scanner.nextLine().split(" ");
  for(int i=1;i<=n;i++)
  {
   row[i] = Integer.parseInt(tmpStrings[i-1]);
  }
  for(int i=0;i<m;i++)
  {
   tmpStrings = scanner.nextLine().split(" ");
   if(tmpStrings.length==3)
   {
    int index = Integer.parseInt(tmpStrings[1]);
    int changeTo = Integer.parseInt(tmpStrings[2]);
    row[index] = changeTo;
   }
   else{
    hole = Integer.parseInt(tmpStrings[1]);
    step = 0;
    int t = 0;
    while(hole<=n)
    {
     t = row[hole];
     hole = hole + row[hole];
     step++;
    }
    System.out.println((hole-t)+" "+step);
   }
  }
 }
}

有哪个大佬能指点一下小弟不，是不是漏考虑了什么特殊情况。。。

发表于 2019-06-17 10:50:02 回复(0)