Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
A 以上 B 以下であるような C の倍数を、1 つ出力してください。
条件を満たす数が存在しない場合は -1 を出力してください。
制約
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
答えを出力せよ。
条件を満たす数が存在しない場合は -1 を出力せよ。
入力例 1
123 456 100
出力例 1
200
300 や 400 も正解です。
入力例 2
630 940 314
出力例 2
-1
Score : 100 points
Problem Statement
Print a number between A and B (inclusive) that is a multiple of C.
If there is no such number, print -1.
Constraints
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the answer.
If there is no number with the desired property, print -1.
Sample Input 1
123 456 100
Sample Output 1
200
300 or 400 would also be accepted.
Sample Input 2
630 940 314
Sample Output 2
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
関数 f を f(x) = x^2 + 2x + 3 と定義します。
整数 t が入力されるので、 f(f(f(t)+t)+f(f(t))) を求めてください。
ただし、答えは 2 \times 10^9 以下の整数であることが保証されます。
制約
- t は 0 以上 10 以下の整数である
入力
入力は以下の形式で標準入力から与えられる。
t
出力
答えを整数として出力せよ。
入力例 1
0
出力例 1
1371
答えは以下の手順によって計算されます。
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
入力例 2
3
出力例 2
722502
入力例 3
10
出力例 3
1111355571
Score : 100 points
Problem Statement
Let us define a function f as f(x) = x^2 + 2x + 3.
Given an integer t, find f(f(f(t)+t)+f(f(t))).
Here, it is guaranteed that the answer is an integer not greater than 2 \times 10^9.
Constraints
- t is an integer between 0 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
t
Output
Print the answer as an integer.
Sample Input 1
0
Sample Output 1
1371
The answer is computed as follows.
- f(t) = t^2 + 2t + 3 = 0 \times 0 + 2 \times 0 + 3 = 3
- f(t)+t = 3 + 0 = 3
- f(f(t)+t) = f(3) = 3 \times 3 + 2 \times 3 + 3 = 18
- f(f(t)) = f(3) = 18
- f(f(f(t)+t)+f(f(t))) = f(18+18) = f(36) = 36 \times 36 + 2 \times 36 + 3 = 1371
Sample Input 2
3
Sample Output 2
722502
Sample Input 3
10
Sample Output 3
1111355571
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S と T が与えられます。
以下の条件を満たす 1 \leq c \leq w < |S| となる整数の組 c と w が存在するか判定してください。ただし、 |S| は文字列 S の長さを表します。ここで、w は |S| 未満である必要があることに注意してください。
- S を先頭から順に w 文字毎に区切ったとき、長さが c 以上の文字列の c 文字目を順番に連結した文字列が T と一致する
制約
- S と T は英小文字からなる文字列
- 1 \leq |T| \leq |S| \leq 100
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
条件を満たすような 1 \leq c \leq w < |S| となる整数の組 c と w が存在する場合は Yes を、存在しない場合は No を出力せよ。
入力例 1
atcoder toe
出力例 1
Yes
S を 2 文字毎に区切ると以下のようになります。
at co de r
区切った後、 2 文字以上の文字列の 2 文字目を取り出し連結させたときの文字列は、 toe となり T と一致します。よって、 Yes を出力します。
入力例 2
beginner r
出力例 2
No
w=|S| であることはないため、条件を満たすような 1 \leq c \leq w < |S| となる整数の組 c と w は存在しません。よって、 No を出力します。
入力例 3
verticalreading agh
出力例 3
No
Score : 200 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters.
Determine if there exists a pair of integers c and w such that 1 \leq c \leq w < |S| and the following condition is satisfied. Here, |S| denotes the length of the string S. Note that w must be less than |S|.
- If S is split at every w characters from the beginning, the concatenation of the c-th characters of the substrings of length at least c in order equals T.
Constraints
- S and T are strings consisting of lowercase English letters.
- 1 \leq |T| \leq |S| \leq 100
Input
The input is given from Standard Input in the following format:
S T
Output
Print Yes if there exists a pair of integers c and w such that 1 \leq c \leq w < |S| and the condition is satisfied, and No otherwise.
Sample Input 1
atcoder toe
Sample Output 1
Yes
If S is split at every two characters, it looks like this:
at co de r
Then, the concatenation of the 2nd characters of the substrings of length at least 2 is toe, which equals T. Thus, print Yes.
Sample Input 2
beginner r
Sample Output 2
No
w=|S| is not allowed, and no pair of integers 1 \leq c \leq w < |S| satisfies the condition. Thus, print No.
Sample Input 3
verticalreading agh
Sample Output 3
No
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
配点 : 300 点
問題文
高橋君は座標平面上で龍を操作するゲームを作成しました。
龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭 と呼びます。
最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。
1 C: 頭を方向 C に 1 移動させる。ここで、C はR,L,U,Dのいずれかであり、それぞれ x 軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i\ \ (2\leq i \leq N) は移動前にパーツ i-1 があった座標に移動する。2 p: パーツ p のある座標を求める。
制約
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 2\times 10^5
- 1 種類目のクエリにおいて、C は
R,L,U,Dのいずれか - 2 種類目のクエリにおいて、1\leq p \leq N
- 入力に含まれる数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
各クエリは以下の 2 種類のいずれかの形式である。
1 C
2 p
出力
2 種類目のクエリの回数を q として q 行出力せよ。
i 行目には、i 番目のそのようなクエリに対する答えの座標を (x,y) としたとき、x,y を空白区切りで出力せよ。
入力例 1
5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5
出力例 1
3 0 2 0 1 1 1 0 1 0
2 種類目のクエリを処理する各タイミングにおいて、パーツの位置は次のようになっています。
複数のパーツが同じ座標に存在しうることに注意してください。
Score : 300 points
Problem Statement
Takahashi has created a game where the player controls a dragon on a coordinate plane.
The dragon consists of N parts numbered 1 to N, with part 1 being called the head.
Initially, part i is located at the coordinates (i,0). Process Q queries as follows.
1 C: Move the head by 1 in direction C. Here, C is one ofR,L,U, andD, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.2 p: Find the coordinates of part p.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 2\times 10^5
- For the first type of query, C is one of
R,L,U, andD. - For the second type of query, 1\leq p \leq N.
- All numerical input values are integers.
Input
The input is given from Standard Input in the following format:
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
Each query is in one of the following two formats:
1 C
2 p
Output
Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.
Sample Input 1
5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5
Sample Output 1
3 0 2 0 1 1 1 0 1 0
At each time when processing the second type of query, the parts are at the following positions:
Note that multiple parts may exist at the same coordinates.