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 点
問題文
正整数 D が与えられます。
直径が D の円の面積を求めて下さい。
制約
- 1\le D\le 100
- 入力される値は整数
入力
入力は以下の形式で標準入力から与えられる。
D
出力
答えを出力せよ。
真の解との絶対誤差または相対誤差が 10^{-6} 以下のとき正解と判定される。
入力例 1
2
出力例 1
3.141592653589793
直径が 2 の円の面積は 3.141592653589793\ldots です。
入力例 2
7
出力例 2
38.48451000647496
入力例 3
98
出力例 3
7542.9639612690935
Score : 100 points
Problem Statement
You are given a positive integer D.
Find the area of a circle with diameter D.
Constraints
- 1\le D\le 100
- The input value is an integer.
Input
The input is given from Standard Input in the following format:
D
Output
Output the answer.
Your answer is considered correct if the absolute or relative error from the true answer is at most 10^{-6}.
Sample Input 1
2
Sample Output 1
3.141592653589793
The area of a circle with diameter 2 is 3.141592653589793\ldots.
Sample Input 2
7
Sample Output 2
38.48451000647496
Sample Input 3
98
Sample Output 3
7542.9639612690935
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
英小文字と ? からなる文字列 T と、英小文字のみからなる文字列 U が与えられます。
T は、英小文字のみからなる文字列 S のちょうど 4 文字を ? で置き換えることで得られた文字列です。
S が U を連続部分文字列として含んでいた可能性があるかどうか判定してください。
制約
- T は長さ 4 以上 10 以下の英小文字と
?からなる文字列 - T にはちょうど 4 つの
?が含まれる - U は長さ 1 以上 |T| 以下の英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
T U
出力
S が U を部分文字列として含んでいた可能性があるならば Yes を、そうでないならば No を出力せよ。
入力例 1
tak??a?h? nashi
出力例 1
Yes
例えば、S が takanashi である場合、これは nashi を連続部分文字列として含みます。
入力例 2
??e??e snuke
出力例 2
No
? がどのような文字であっても、S は snuke を連続部分文字列として含むことがありません。
入力例 3
???? aoki
出力例 3
Yes
Score : 250 points
Problem Statement
You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.
The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.
Determine whether it is possible that the original string S contained U as a contiguous substring.
Constraints
- T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and
?. - T contains exactly four occurrences of
?. - U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.
Input
The input is given from Standard Input in the following format:
T U
Output
Print Yes if it is possible that the original string S contained U as a contiguous substring; otherwise, print No.
Sample Input 1
tak??a?h? nashi
Sample Output 1
Yes
For example, if S is takanashi, it contains nashi as a contiguous substring.
Sample Input 2
??e??e snuke
Sample Output 2
No
No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.
Sample Input 3
???? aoki
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
長さ M の整数列 A=(A_1,A_2,\dots,A_M) が与えられます。
A の各要素は 1 以上 N 以下で、全ての要素は相異なります。
A の要素として含まれない 1 以上 N 以下の整数を、昇順に全て列挙してください。
制約
- 入力は全て整数
- 1 \le M \le N \le 1000
- 1 \le A_i \le N
- A の要素は相異なる
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
A の要素として含まれない 1 以上 N 以下の整数を昇順に全て挙げた列が (X_1,X_2,\dots,X_C) であるとき、以下の形式で出力せよ。
C X_1 X_2 \dots X_C
入力例 1
10 3 3 9 2
出力例 1
7 1 4 5 6 7 8 10
A=(3,9,2) です。
A の要素として含まれない 1 以上 10 以下の整数を昇順に全て挙げると、 1,4,5,6,7,8,10 となります。
入力例 2
6 6 1 3 5 2 4 6
出力例 2
0
A の要素として含まれない 1 以上 6 以下の整数がひとつもありません。
この場合、 1 行目に 0 と出力し、 2 行目は空行としてください。
入力例 3
9 1 9
出力例 3
8 1 2 3 4 5 6 7 8
Score : 200 points
Problem Statement
You are given a sequence of M integers A = (A_1, A_2, \dots, A_M).
Each element of A is an integer between 1 and N, inclusive, and all elements are distinct.
List all integers between 1 and N that do not appear in A in ascending order.
Constraints
- All input values are integers.
- 1 \le M \le N \le 1000
- 1 \le A_i \le N
- The elements of A are distinct.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Let (X_1, X_2, \dots, X_C) be the sequence of all integers between 1 and N, inclusive, that do not appear in A, listed in ascending order. The output should be in the following format:
C X_1 X_2 \dots X_C
Sample Input 1
10 3 3 9 2
Sample Output 1
7 1 4 5 6 7 8 10
Here, A=(3,9,2).
The integers between 1 and 10 that do not appear in A, listed in ascending order, are 1,4,5,6,7,8,10.
Sample Input 2
6 6 1 3 5 2 4 6
Sample Output 2
0
No integer between 1 and 6 is missing from A.
In this case, print 0 on the first line and leave the second line empty.
Sample Input 3
9 1 9
Sample Output 3
8 1 2 3 4 5 6 7 8
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)
i=1,2,\dots,N に対して、以下の問題を解いてください。
- i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。
制約
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
N 行出力せよ。
i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。
入力例 1
3 2 2 3
出力例 1
1 0 0
AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。
- 1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
- 2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
- 3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。
入力例 2
8 5 1 3 4 7 8
出力例 2
0 1 0 0 2 1 0 0
Score : 250 points
Problem Statement
The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)
For each i=1,2,\dots,N, solve the following problem.
- How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.
Constraints
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Print N lines.
The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.
Sample Input 1
3 2 2 3
Sample Output 1
1 0 0
The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.
- From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
- From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
- From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.
Sample Input 2
8 5 1 3 4 7 8
Sample Output 2
0 1 0 0 2 1 0 0