Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。
A から偶数だけすべて取り出し、もとの順番を保って出力してください。
制約
- 1\leq N\leq 100
- 1\leq A _ i\leq 100\ (1\leq i\leq N)
- A には 1 つ以上偶数が含まれる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N
出力
A から偶数を取り出した列を、空白区切りで 1 行に出力せよ。
入力例 1
5 1 2 3 5 6
出力例 1
2 6
A=(1,2,3,5,6) です。 このうち偶数なのは A _ 2=2,A _ 5=6 の 2 つなので、2 と 6 をこの順に空白区切りで出力してください。
入力例 2
5 2 2 2 3 3
出力例 2
2 2 2
A の中には同じ要素がある場合もあります。
入力例 3
10 22 3 17 8 30 15 12 14 11 17
出力例 3
22 8 30 12 14
Score : 100 points
Problem Statement
You are given a sequence of N integers: A=(A _ 1,A _ 2,\ldots,A _ N).
Print all even numbers in A without changing the order.
Constraints
- 1\leq N\leq 100
- 1\leq A _ i\leq 100\ (1\leq i\leq N)
- A contains at least one even number.
- 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 a line containing the sequence of all even numbers in A, with spaces in between.
Sample Input 1
5 1 2 3 5 6
Sample Output 1
2 6
We have A=(1,2,3,5,6). Among them are two even numbers, A _ 2=2 and A _ 5=6, so print 2 and 6 in this order, with a space in between.
Sample Input 2
5 2 2 2 3 3
Sample Output 2
2 2 2
A may contain equal elements.
Sample Input 3
10 22 3 17 8 30 15 12 14 11 17
Sample Output 3
22 8 30 12 14
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
サンタさんに手紙を出したい高橋くんは、 X 円切手が 1 枚だけ貼られた封筒を用意しました。
サンタさんに手紙を届けるためには、貼られている切手の総額が Y 円以上である必要があります。
高橋くんは、この封筒に 10 円切手を何枚か貼り足すことで、貼られている切手の総額を Y 円以上にしたいです。
高橋くんはこの封筒に、最小で何枚の 10 円切手を貼り足す必要がありますか?
制約
- X,Y は整数
- 1 \le X,Y \le 1000
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
答えを整数として出力せよ。
入力例 1
80 94
出力例 1
2
- 80 円切手に 0 枚の 10 円切手を貼り足せば総額が 80 円となり、これは手紙を届けるのに必要な 94 円未満です。
- 80 円切手に 1 枚の 10 円切手を貼り足せば総額が 90 円となり、これは手紙を届けるのに必要な 94 円未満です。
- 80 円切手に 2 枚の 10 円切手を貼り足せば総額が 100 円となり、これは手紙を届けるのに必要な 94 円以上です。
入力例 2
1000 63
出力例 2
0
もともと貼られている切手だけで金額が十分である可能性もあります。
入力例 3
270 750
出力例 3
48
Score : 100 points
Problem Statement
Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?
Constraints
- X and Y are integers.
- 1 \le X,Y \le 1000
Input
Input is given from Standard Input in the following format:
X Y
Output
Print the answer as an integer.
Sample Input 1
80 94
Sample Output 1
2
- After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
- After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
- After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.
Sample Input 2
1000 63
Sample Output 2
0
The envelope may already have a stamp with enough value.
Sample Input 3
270 750
Sample Output 3
48
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
. および # からなる文字列 S が与えられます。
以下の条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ求めてください。
- T の長さは S の長さと等しい。
- T は
.、#、oからなる。 - S_i=
#であるとき、またそのときに限り T_i=#である。 - T_i=T_j=
o(i < j) ならば、 T_{i+1},\ldots,T_{j-1} の中に#が 1 つ以上存在する。
制約
- S は
.および#からなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件を全て満たす文字列 T のうち、 o の文字数が最大となるものを一つ出力せよ。
そのような文字列が複数ある場合、どれを出力しても正答となる。
入力例 1
#..#.
出力例 1
#o.#o
T= #o.#o とすると全ての条件を満たすことが確認できます。
全ての条件を満たす T であって、 o の文字数が 2 より多い文字列は存在しないので #o.#o を出力すると正答となります。
この他にも #.o#o を出力しても正答となります。
入力例 2
#
出力例 2
#
入力例 3
.....
出力例 3
..o..
この他にも o....、.o...、...o.、....o を出力しても正答となります。
入力例 4
...#..#.##.#.
出力例 4
o..#.o#o##o#o
Score : 250 points
Problem Statement
You are given a string S consisting of . and #.
Among all strings T that satisfy all of the following conditions, find one with the maximum number of os.
- The length of T is equal to the length of S.
- T consists of
.,#, oro. - T_i=
#if and only if S_i=#. - If T_i=T_j=
o(i < j), then there exists at least one#among T_{i+1},\ldots,T_{j-1}.
Constraints
- S is a string consisting of
.and#with length between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Output one string with the maximum number of os among all strings T that satisfy all conditions.
If there are multiple such strings, printing any of them will be considered correct.
Sample Input 1
#..#.
Sample Output 1
#o.#o
Setting T= #o.#o satisfies all conditions.
There is no string T that satisfies all conditions and has more than two os, so outputting #o.#o is correct.
Outputting #.o#o is also correct.
Sample Input 2
#
Sample Output 2
#
Sample Input 3
.....
Sample Output 3
..o..
Outputting o...., .o..., ...o., or ....o is also correct.
Sample Input 4
...#..#.##.#.
Sample Output 4
o..#.o#o##o#o
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
座標平面上に N 枚の長方形のシートが張られています。
各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。
1 枚以上のシートによって覆われている領域 の面積を S とすると、
S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。
制約
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
出力
1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。
入力例 1
3 0 5 1 3 1 4 0 5 2 5 2 4
出力例 1
20
3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。
入力例 2
2 0 100 0 100 0 100 0 100
出力例 2
10000
異なるシートが同じ領域を覆っている事があることに注意してください。
入力例 3
3 0 1 0 1 0 3 0 5 5 10 0 10
出力例 3
65
Score : 200 points
Problem Statement
There are N rectangular sheets spread out on a coordinate plane.
Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.
Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.
Constraints
- 2\leq N\leq 100
- 0\leq A_i<B_i\leq 100
- 0\leq C_i<D_i\leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 \vdots A_N B_N C_N D_N
Output
Print the area S of the region covered by one or more sheets as an integer.
Sample Input 1
3 0 5 1 3 1 4 0 5 2 5 2 4
Sample Output 1
20
The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.
Sample Input 2
2 0 100 0 100 0 100 0 100
Sample Output 2
10000
Note that different sheets may cover the same region.
Sample Input 3
3 0 1 0 1 0 3 0 5 5 10 0 10
Sample Output 3
65
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