実行時間制限: 2 sec / メモリ制限: 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
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N 個の文字列 S_1,S_2,\ldots,S_N がこの順番で与えられます。
S_N,S_{N-1},\ldots,S_1 の順番で出力してください。
制約
- 1\leq N \leq 10
- N は整数
- S_i は英小文字、英大文字、数字からなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
N 行出力せよ。 i\ (1\leq i \leq N) 行目には、S_{N+1-i} を出力せよ。
入力例 1
3 Takahashi Aoki Snuke
出力例 1
Snuke Aoki Takahashi
N=3、S_1= Takahashi、S_2= Aoki、S_3= Snuke です。
よって、Snuke、Aoki、Takahashi の順で出力します。
入力例 2
4 2023 Year New Happy
出力例 2
Happy New Year 2023
与えられる文字列が数字を含むこともあります。
Score : 100 points
Problem Statement
You are given N strings S_1,S_2,\ldots,S_N in this order.
Print S_N,S_{N-1},\ldots,S_1 in this order.
Constraints
- 1\leq N \leq 10
- N is an integer.
- S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print N lines. The i-th (1\leq i \leq N) line should contain S_{N+1-i}.
Sample Input 1
3 Takahashi Aoki Snuke
Sample Output 1
Snuke Aoki Takahashi
We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.
Thus, you should print Snuke, Aoki, and Takahashi in this order.
Sample Input 2
4 2023 Year New Happy
Sample Output 2
Happy New Year 2023
The given strings may contain digits.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
整数 1, 2, \dots, N が書かれたカードが 4 枚ずつ、合計 4N 枚あります。
高橋君は、これらのカードをシャッフルしたのち 1 枚のカードを選んで抜き取り、残りの 4N - 1 枚を束にしてあなたに渡しました。渡された束の i \, (1 \leq i \leq 4N - 1) 枚目のカードには、整数 A_i が書かれています。
高橋君が抜き取ったカードに書かれていた整数を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
- 各 k \, (1 \leq k \leq N) に対し、A_i = k となる i は 4 個以下である。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{4N - 1}
出力
答えを出力せよ。
入力例 1
3 1 3 2 3 3 2 2 1 1 1 2
出力例 1
3
高橋君が抜き取ったカードには 3 が書かれています。
入力例 2
1 1 1 1
出力例 2
1
入力例 3
4 3 2 1 1 2 4 4 4 4 3 1 3 2 1 3
出力例 3
2
Score : 200 points
Problem Statement
We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.
Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.
Find the integer written on the card removed by Takahashi.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
- For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{4N - 1}
Output
Print the answer.
Sample Input 1
3 1 3 2 3 3 2 2 1 1 1 2
Sample Output 1
3
Takahashi removed a card with 3 written on it.
Sample Input 2
1 1 1 1
Sample Output 2
1
Sample Input 3
4 3 2 1 1 2 4 4 4 4 3 1 3 2 1 3
Sample Output 3
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
おもり 1, おもり 2, \dots, おもり N の N 個のおもりがあります。おもり i の重さは A_i です。
以下の条件を満たす正整数 n を 良い整数 と呼びます。
- \bf{3} 個以下 の異なるおもりを自由に選んで、選んだおもりの重さの和を n にすることができる。
W 以下の正整数のうち、良い整数は何個ありますか？
制約
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
2 10 1 3
出力例 1
3
おもり 1 のみを選ぶと重さの和は 1 になります。よって 1 は良い整数です。
おもり 2 のみを選ぶと重さの和は 3 になります。よって 3 は良い整数です。
おもり 1 とおもり 2 を選ぶと重さの和は 4 になります。よって 4 は良い整数です。
これら以外に良い整数は存在しません。また、1,3,4 のいずれも W 以下の整数です。よって答えは 3 個になります。
入力例 2
2 1 2 3
出力例 2
0
W 以下の良い整数は存在しません。
入力例 3
4 12 3 3 3 3
出力例 3
3
良い整数は 3,6,9 の 3 個です。
たとえばおもり 1, おもり 2, おもり 3 を選ぶと重さの和は 9 になるので、9 は良い整数です。
12 は良い整数 ではない ことに注意してください。
入力例 4
7 251 202 20 5 1 4 2 100
出力例 4
48
Score : 200 points
Problem Statement
There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:
- We can choose at most 3 different weights so that they have a total mass of n.
How many positive integers less than or equal to W are good integers?
Constraints
- 1 \leq N \leq 300
- 1 \leq W \leq 10^6
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N W A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
2 10 1 3
Sample Output 1
3
If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.
Sample Input 2
2 1 2 3
Sample Output 2
0
There are no good integers less than or equal to W.
Sample Input 3
4 12 3 3 3 3
Sample Output 3
3
There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.
Sample Input 4
7 251 202 20 5 1 4 2 100
Sample Output 4
48
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の正整数のみからなる数列 A=(A_1,\dots,A_N) があります。
A を 10^{100} 回連結した数列を数列 B とします。
B の項を前から順に足したとき、和が初めて X を超えるのは何項目まで足したときですか？
すなわち、以下の式を満たす最小の整数 k を求めてください。
\displaystyle{\sum_{i=1}^{k} B_i \gt X}
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N X
出力
答えを出力せよ。
入力例 1
3 3 5 2 26
出力例 1
8
B=(3,5,2,3,5,2,3,5,2,\dots) です。
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} であり、k が 7 以下のとき条件を満たさないので、8 が答えです。
入力例 2
4 12 34 56 78 1000
出力例 2
23
Score : 300 points
Problem Statement
We have a sequence of N positive integers: A=(A_1,\dots,A_N).
Let B be the concatenation of 10^{100} copies of A.
Consider summing up the terms of B from left to right. When does the sum exceed X for the first time?
In other words, find the minimum integer k such that:
\displaystyle{\sum_{i=1}^{k} B_i \gt X}.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N X
Output
Print the answer.
Sample Input 1
3 3 5 2 26
Sample Output 1
8
We have B=(3,5,2,3,5,2,3,5,2,\dots).
\displaystyle{\sum_{i=1}^{8} B_i = 28 \gt 26} holds, but the condition is not satisfied when k is 7 or less, so the answer is 8.
Sample Input 2
4 12 34 56 78 1000
Sample Output 2
23