Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋くんは、N 個の品物と 1 つのカバンを持っています。
i 番目 (1\le i\le N) の品物の大きさは A _ i で、カバンの大きさは M です。
カバンに入れようとしている品物の大きさの合計が M 以下のとき、かつそのときに限り、それらの品物をすべて同時にカバンに入れることができます。
高橋くんが N 個の品物すべてを同時にカバンに入れることができるなら Yes 、そうでなければ No と出力してください。
制約
- 1\le N\le100
- 1\le M\le10000
- 1\le A _ i\le100\ (1\le i\le N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A _ 1 A _ 2 \ldots A _ N
出力
高橋くんがすべての品物を同時にカバンに入れられるなら Yes を、そうでなければ No を出力せよ。
入力例 1
5 15 3 1 4 1 5
出力例 1
Yes
5 つの品物の大きさの合計は 3+1+4+1+5=14 です。
これは、カバンの大きさ 15 以下なので、高橋くんはすべての品物を同時にカバンに入れることができます。
なので、Yes を出力してください。
入力例 2
5 5 3 1 4 1 5
出力例 2
No
5 つの品物の大きさの合計は 14 で、カバンの大きさ 5 より大きいため、高橋くんはすべての品物を同時にカバンに入れることができません。
なので、No を出力してください。
入力例 3
1 10000 100
出力例 3
Yes
Score : 100 points
Problem Statement
Takahashi has N items and one bag.
The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.
If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.
If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.
Constraints
- 1\le N\le100
- 1\le M\le10000
- 1\le A_i\le100\ (1\le i\le N)
- All input values are integers.
Input
The input is given from standard input in the following format:
N M A_1 A_2 \ldots A_N
Output
If Takahashi can put all items in the bag simultaneously, print Yes; otherwise, print No.
Sample Input 1
5 15 3 1 4 1 5
Sample Output 1
Yes
The total size of the 5 items is 3+1+4+1+5=14.
Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously.
Thus, print Yes.
Sample Input 2
5 5 3 1 4 1 5
Sample Output 2
No
The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously.
Thus, print No.
Sample Input 3
1 10000 100
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は、時刻 0 にパソコンの電源をつけ、それからマウスを N 回クリックしました。i(1 \le i \le N) 回目のクリックは時刻 T_i に行われました。
高橋君が時刻 x_1 と時刻 x_2 (ただし x_1 < x_2)にマウスを連続してクリックしたとき、x_2 - x_1 \le D であれば時刻 x_2 にダブルクリックが成立したと言います。
高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が 1 回もダブルクリックを成立させていないならば -1 を出力してください。
制約
- 1 \le N \le 100
- 1 \le D \le 10^9
- 1 \le T_i \le 10^9(1 \le i \le N)
- T_i < T_{i+1}(1 \le i \le N-1)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D T_1 T_2 \dots T_N
出力
高橋君が 1 回でもダブルクリックを成立させたならば最初にダブルクリックが成立した時刻を、そうでないならば -1 を出力せよ。
入力例 1
4 500 300 900 1300 1700
出力例 1
1300
高橋君は時刻 900,1300 にマウスをクリックしていて、1300 - 900 \le 500 であるため時刻 1300 にダブルクリックが成立しています。
時刻 1300 より前にダブルクリックは成立していないため、1300 を出力してください。
入力例 2
5 99 100 200 300 400 500
出力例 2
-1
高橋君は 1 回もダブルクリックを成立させていません。よって、-1 を出力してください。
入力例 3
4 500 100 600 1100 1600
出力例 3
600
高橋君が複数回ダブルクリックを成立させていても、そのうち最初の時刻のみを出力することに注意してください。
Score : 100 points
Problem Statement
Takahashi turned on a computer at time 0 and clicked the mouse N times. The i-th (1 \le i \le N) click was at time T_i.
If he consecutively clicked the mouse at time x_1 and time x_2 (where x_1 < x_2), a double click is said to be fired at time x_2 if and only if x_2 - x_1 \le D.
What time was a double click fired for the first time? If no double click was fired, print -1 instead.
Constraints
- 1 \le N \le 100
- 1 \le D \le 10^9
- 1 \le T_i \le 10^9(1 \le i \le N)
- T_i < T_{i+1}(1 \le i \le N-1)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N D T_1 T_2 \dots T_N
Output
If at least one double click was fired, print the time of the first such event; otherwise, print -1.
Sample Input 1
4 500 300 900 1300 1700
Sample Output 1
1300
Takahashi clicked the mouse at time 900 and 1300. Since 1300 - 900 \le 500, a double click was fired at time 1300.
A double click had not been fired before time 1300, so 1300 should be printed.
Sample Input 2
5 99 100 200 300 400 500
Sample Output 2
-1
No double click was fired, so print -1.
Sample Input 3
4 500 100 600 1100 1600
Sample Output 3
600
If multiple double clicks were fired, be sure to print only the first such event.
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 点
問題文
3 桁の正整数であって、百の位の数と十の位の数の積が一の位の数と等しいものを 326-like number と呼びます。
例えば 326,400,144 は 326-like number であり、623,777,429 は 326-like number ではありません。
整数 N が与えられるので、N 以上の最小の 326-like number を求めてください。なお、制約の条件下で答えは必ず存在します。
制約
- 100 \leq N \leq 919
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
320
出力例 1
326
320,321,322,323,324,325 は 326-like number ではなく、326 は 326-like number です。
入力例 2
144
出力例 2
144
144 は 326-like number です。
入力例 3
516
出力例 3
600
Score : 200 points
Problem Statement
A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.
For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.
Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.
Constraints
- 100 \leq N \leq 919
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
320
Sample Output 1
326
320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.
Sample Input 2
144
Sample Output 2
144
144 is a 326-like number.
Sample Input 3
516
Sample Output 3
600
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 K = 0, 1, 2, \ldots, N-1 のそれぞれについて、下記の問題を解いてください。
1 以上 N 以下の整数 i であって、次の条件を満たすものの個数を求めよ。
- A に含まれる整数のうち A_i より大きいものはちょうど K 種類である。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には K = i-1 の場合の問題の答えを出力せよ。
入力例 1
6 2 7 1 8 2 8
出力例 1
2 1 2 1 0 0
例として、K = 2 の場合の問題の答えを以下で求めます。
- A_1 = 2 に関して、A に含まれる整数のうち A_1 より大きいものは、7, 8 の 2 種類です。
- A_2 = 7 に関して、A に含まれる整数のうち A_2 より大きいものは、8 の 1 種類です。
- A_3 = 1 に関して、A に含まれる整数のうち A_3 より大きいものは、2, 7, 8 の 3 種類です。
- A_4 = 8 に関して、A に含まれる整数のうち A_4 より大きいものは、0 種類です（存在しません）。
- A_5 = 2 に関して、A に含まれる整数のうち A_5 より大きいものは、7, 8 の 2 種類です。
- A_6 = 8 に関して、A に含まれる整数のうち A_6 より大きいものは、0 種類です（存在しません）。
よって、A に含まれる整数のうちA_i より大きいものがちょうど K = 2 種類であるような i は、i = 1 と i = 5 の 2 つです。よって、K = 2 の場合の答えは 2 です。
入力例 2
1 1
出力例 2
1
入力例 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
出力例 3
2 1 2 1 2 1 1 0 0 0
Score : 300 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.
Find the number of integers i between 1 and N (inclusive) such that:
- A contains exactly K distinct integers greater than A_i.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain the answer for K = i-1.
Sample Input 1
6 2 7 1 8 2 8
Sample Output 1
2 1 2 1 0 0
For example, we will find the answer for K=2.
- Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
- Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
- Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
- Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
- Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
- Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).
Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
10 979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527
Sample Output 3
2 1 2 1 2 1 1 0 0 0