実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は N 日間のタスク目標を設定しました。
高橋君は i (1 \leq i \leq N) 日目に A_i 個のタスクを完了することを目標としており、実際には B_i 個のタスクを完了しました。
高橋君が目標より多くのタスクを完了した日数を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq A_i, B_i \leq 100
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
4 2 8 5 5 5 4 6 7
出力例 1
2
高橋君は 1 日目と 4 日目に目標より多くのタスクを完了しました。
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
0
入力例 3
6 1 6 2 5 3 4 4 3 5 2 6 1
出力例 3
3
Score : 100 points
Problem Statement
Takahashi set task goals for N days.
He aimed to complete A_i tasks on day i (1 \leq i \leq N), and actually completed B_i tasks.
Find the number of days when he completed more tasks than his goal.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i, B_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 A_2 B_2 \vdots A_N B_N
Output
Output the answer.
Sample Input 1
4 2 8 5 5 5 4 6 7
Sample Output 1
2
Takahashi completed more tasks than his goal on the 1st and 4th days.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
6 1 6 2 5 3 4 4 3 5 2 6 1
Sample Output 3
3
実行時間制限: 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
配点 : 200 点
問題文
-10^{18} 以上 10^{18} 以下の整数 N が与えられます。
以下の条件を満たす 0 以上 998244353 未満の整数 x を求めてください。なお、答えが一意に定まることが証明できます。
- N-x は 998244353 の倍数
制約
- N は -10^{18} 以上 10^{18} 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
998244354
出力例 1
1
998244354-1 = 998244353 は 998244353 の倍数なので条件を満たします。
入力例 2
-9982443534
出力例 2
998244349
-9982443534-998244349= -10980687883 は 998244353 の倍数なので条件を満たします。
Score : 200 points
Problem Statement
You are given an integer N between -10^{18} and 10^{18} (inclusive).
Find an integer x between 0 and 998244353 - 1 (inclusive) that satisfies the following condition. It can be proved that such an integer is unique.
- N-x is a multiple of 998244353.
Constraints
- N is an integer between -10^{18} and 10^{18} (inclusive).
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
998244354
Sample Output 1
1
998244354-1 = 998244353 is a multiple of 998244353, so the condition is satisfied.
Sample Input 2
-9982443534
Sample Output 2
998244349
-9982443534-998244349= -10980687883 is a multiple of 998244353, so the condition is satisfied.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる長さ 3 以上の文字列 S が与えられます。
S はちょうど 2 種類の文字を含み、 1 文字だけ他の文字と異なります。その 1 文字を答えてください。
例えば、 S が odd なら o と答えてください。
制約
- S は英小文字からなる長さ 3 以上 10 以下の文字列
- S はちょうど 2 種類の文字を含み、 1 文字だけ他の文字と異なる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
odd
出力例 1
o
odd のうち他の文字と異なるものは o です。
入力例 2
dad
出力例 2
a
dad のうち他の文字と異なるものは a です。
入力例 3
wwwwwwwwwv
出力例 3
v
wwwwwwwwwv のうち他の文字と異なるものは v です。
Score : 200 points
Problem Statement
You are given a string S of length at least 3 consisting of lowercase English letters.
S contains exactly two types of characters, and exactly one character is different from the others. Find that one character.
For example, if S is odd, report o.
Constraints
- S is a string of length at least 3 and at most 10 consisting of lowercase English letters.
- S contains exactly two types of characters, and exactly one character is different from the others.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
odd
Sample Output 1
o
In odd, the character different from the others is o.
Sample Input 2
dad
Sample Output 2
a
In dad, the character different from the others is a.
Sample Input 3
wwwwwwwwwv
Sample Output 3
v
In wwwwwwwwwv, the character different from the others is v.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
りんごさんは馬を縞模様に塗ってシマウマにしようとしています。
1 から N の番号がついた N 個のマスが一列に並んでいます。
最初、全てのマスは白色であり、マス i を黒く塗るためにはコストが C_i かかります。
以下の手順を一度だけ行い、いくつかのマスを黒く塗ることを考えます。
- 正整数 x を自由に選ぶ。
- 1 \leq i \leq N を満たす整数 i のうち、 (i+x) を 2W で割った余りが W より小さくなるもの全てに対し、マス i を黒く塗る。
この手順を行うためのコストの合計の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1\leq T \leq 2\times 10^5
- 1\leq N \leq 2\times 10^5
- 1\leq W \leq 2\times 10^5
- 1\leq C_i \leq 10^9
- T 個のテストケースにおける N の総和は 2\times 10^5 以下
- T 個のテストケースにおける W の総和は 2\times 10^5 以下
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 番目のテストケースを意味する。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる。
N W C_1 \dots C_N
出力
T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。
入力例 1
4 8 2 1 10 10 1 1 10 10 1 8 3 1 10 10 1 1 10 10 1 8 4 1 10 10 1 1 10 10 1 4 100 100000 100000 100000 100000
出力例 1
4 12 22 0
1 番目のテストケースにおいて、x=4 として手順を実行すると、マス 1,4,5,8 が黒く塗られ、コストの合計は 4 となります。 コストの合計を 4 未満にすることはできないため、これが最小値となります。
Score : 300 points
Problem Statement
Ringo-san is trying to paint a horse with stripes to make it a zebra.
There are N squares numbered 1 to N arranged in a line.
Initially, all squares are white, and the cost of painting square i black is C_i.
Consider performing the following procedure once to paint some squares black:
- Choose a positive integer x freely.
- Paint square i black for all integers i satisfying 1 \leq i \leq N such that the remainder when (i+x) is divided by 2W is less than W.
Find the minimum total cost to perform this procedure.
You are given T test cases; solve each of them.
Constraints
- 1\leq T \leq 2\times 10^5
- 1\leq N \leq 2\times 10^5
- 1\leq W \leq 2\times 10^5
- 1\leq C_i \leq 10^9
- The sum of N over the T test cases is at most 2\times 10^5.
- The sum of W over the T test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N W C_1 \dots C_N
Output
Output T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
4 8 2 1 10 10 1 1 10 10 1 8 3 1 10 10 1 1 10 10 1 8 4 1 10 10 1 1 10 10 1 4 100 100000 100000 100000 100000
Sample Output 1
4 12 22 0
In the first test case, if the procedure is executed with x=4, squares 1,4,5,8 are painted black, and the total cost is 4. The total cost cannot be less than 4, so this is the minimum.