Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君の財布の中には 100 円硬貨が 1 枚以上入っており、それ以外には何も入っていません。
高橋君の財布の中の合計金額が X 円である可能性はありますか？
制約
- 0 \leq X \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
X
出力
高橋君の財布の中の合計金額が X 円である可能性がある場合は Yes、そうでない場合は No と出力せよ。
入力例 1
500
出力例 1
Yes
財布に 100 円硬貨が 5 枚入っているとき、合計金額は 500 円になります。故に財布の中の合計金額は X=500 円になりうるため、Yes を出力します。
入力例 2
40
出力例 2
No
入力例 3
0
出力例 3
No
財布の中には 100 円硬貨が 1 枚以上入っていることに注意してください。
Score : 100 points
Problem Statement
Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)
Is it possible that the total amount of money in the purse is X yen?
Constraints
- 0 \leq X \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X
Output
If it is possible that the total amount of money in Takahashi's purse is X yen, print Yes; otherwise, print No.
Sample Input 1
500
Sample Output 1
Yes
If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.
Sample Input 2
40
Sample Output 2
No
Sample Input 3
0
Sample Output 3
No
Note that the purse has at least one 100-yen coin.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
A, B, C からなる文字列 S が与えられます。S は A, B, C を全て含むことが保証されます。
S を左から 1 文字ずつ見ていったときに、はじめて次の条件を満たした状態になるのは、左から何文字目まで見たときですか？
A,B,Cが全て 1 回以上出現している。
制約
- 3 \leq N \leq 100
- S は
A,B,Cからなる長さ N の文字列 - S は
A,B,Cを全て含む
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
5 ACABB
出力例 1
4
左から 4 文字目までに A は 2 回, B は 1 回, C は 1 回出現していて、条件を満たします。
3 文字目以前では条件を満たさないので答えは 4 です。
入力例 2
4 CABC
出力例 2
3
左から 3 文字目までに A, B, C は 1 回ずつ出現していて、条件を満たします。
入力例 3
30 AABABBBABABBABABCABACAABCBACCA
出力例 3
17
Score : 100 points
Problem Statement
You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.
If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?
- All of
A,B, andChave appeared at least once.
Constraints
- 3 \leq N \leq 100
- S is a string of length N consisting of
A,B, andC. - S contains all of
A,B, andC.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
5 ACABB
Sample Output 1
4
In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.
Sample Input 2
4 CABC
Sample Output 2
3
In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.
Sample Input 3
30 AABABBBABABBABABCABACAABCBACCA
Sample Output 3
17
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の人がいます。N 人の人には人 1, 人 2,\dots, 人 N と番号がついています。
人 i(2 \le i \le N) の親は人 P_i です。ここで、P_i < i が保証されます。
人 1 が人 N の何代前か求めてください。
制約
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N P_2 P_3 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2
出力例 1
2
人 2 は人 3 の親であるため、人 3 の 1 代前です。
人 1 は人 2 の親であるため、人 3 の 2 代前です。
よって解は 2 です。
入力例 2
10 1 2 3 4 5 6 7 8 9
出力例 2
9
Score : 200 points
Problem Statement
There are N people, called Person 1, Person 2, \ldots, Person N.
The parent of Person i (2 \le i \le N) is Person P_i. Here, it is guaranteed that P_i < i.
How many generations away from Person N is Person 1?
Constraints
- 2 \le N \le 50
- 1 \le P_i < i(2 \le i \le N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \dots P_N
Output
Print the answer as a positive integer.
Sample Input 1
3 1 2
Sample Output 1
2
Person 2 is a parent of Person 3, and thus is one generation away from Person 3.
Person 1 is a parent of Person 2, and thus is two generations away from Person 3.
Therefore, the answer is 2.
Sample Input 2
10 1 2 3 4 5 6 7 8 9
Sample Output 2
9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。
座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。
高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。
制約
- -1000 \leq X,Y,Z \leq 1000
- X,Y,Z は相異なり、いずれも 0 でない
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。
入力例 1
10 -10 1
出力例 1
10
高橋君はまっすぐゴールに向かうことができます。
入力例 2
20 10 -10
出力例 2
40
ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。
入力例 3
100 1 1000
出力例 3
-1
Score : 200 points
Problem Statement
Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.
There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.
Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.
Constraints
- -1000 \leq X,Y,Z \leq 1000
- X, Y, and Z are distinct, and none of them is 0.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
X Y Z
Output
If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.
Sample Input 1
10 -10 1
Sample Output 1
10
Takahashi can go straight to the goal.
Sample Input 2
20 10 -10
Sample Output 2
40
The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.
Sample Input 3
100 1 1000
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
回転テーブルの周りに人 0、人 1、\ldots、人 N-1 がこの順番で反時計回りに等間隔で並んでいます。また、人 i の目の前には料理 p_i が置かれています。
あなたは次の操作を 0 回以上何度でも行うことが出来ます。
- 回転テーブルを反時計回りに 1 周の \frac{1}{N} だけ回す。これによって、(この操作の直前に)人 i の目の前にあった料理は人 (i+1) \bmod N の目の前に移動する。
操作を完了させた後において、人 i は料理 i が人 (i-1) \bmod N、人 i、人 (i+1) \bmod N のいずれかの目の前に置かれていると喜びます。
喜ぶ人数の最大値を求めてください。
a \bmod m とは
整数 a と正整数 m に対し、a \bmod m は a-x が m の倍数となるような 0 以上 m 未満の整数 x を表します。(このような x は一意に定まることが証明できます)制約
- 3 \leq N \leq 2 \times 10^5
- 0 \leq p_i \leq N-1
- i \neq j ならば p_i \neq p_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
p_0 \ldots p_{N-1}
出力
答えを出力せよ。
入力例 1
4 1 2 0 3
出力例 1
4
操作を 1 回行うと下の画像のようになります。
この時、4 人が喜ぶことを以下のように確かめられます。
- 人 0 は料理 0 が人 3\ (=(0-1) \bmod 4) の目の前に置かれているので喜びます。
- 人 1 は料理 1 が人 1\ (=1) の目の前に置かれているので喜びます。
- 人 2 は料理 2 が人 2\ (=2) の目の前に置かれているので喜びます。
- 人 3 は料理 3 が人 0\ (=(3+1) \bmod 4) の目の前に置かれているので喜びます。
5 人以上が喜ぶことは無いため、答えは 4 です。
入力例 2
3 0 1 2
出力例 2
3
入力例 3
10 3 9 6 1 7 2 8 0 5 4
出力例 3
5
Score : 300 points
Problem Statement
Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:
- Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.
When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.
What is a \bmod m?
For an integer a and a positive integer m, a \bmod m denotes the integer x between 0 and (m-1) (inclusive) such that (a-x) is a multiple of m. (It can be proved that such x is unique.)Constraints
- 3 \leq N \leq 2 \times 10^5
- 0 \leq p_i \leq N-1
- p_i \neq p_j if i \neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
p_0 \ldots p_{N-1}
Output
Print the answer.
Sample Input 1
4 1 2 0 3
Sample Output 1
4
The figure below shows the table after one operation.
Here, there are four happy people:
- Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
- Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
- Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
- Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).
There cannot be five or more happy people, so the answer is 4.
Sample Input 2
3 0 1 2
Sample Output 2
3
Sample Input 3
10 3 9 6 1 7 2 8 0 5 4
Sample Output 3
5