実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 300 点
問題文
3 つの整数 A,B,C が与えられます。以下の 2 種類の操作を好きな順で繰り返して A,B,C をすべて等しくするために必要な操作の最小回数を求めてください。
- A,B,C のうち 2 つを選んで、その両方を 1 増やす
- A,B,C のうち 1 つを選んで、その整数を 2 増やす
なお、これらの操作を繰り返して A,B,C をすべて等しくできることは証明できます。
制約
- 0 \leq A,B,C \leq 50
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
A,B,C をすべて等しくするために必要な操作の最小回数を出力せよ。
入力例 1
2 5 4
出力例 1
2
以下の操作で、A,B,C をすべて等しくできます。
- A,C を 1 増やす。A,B,C はそれぞれ 3,5,5 となる。
- A を 2 増やす。A,B,C はそれぞれ 5,5,5 となる。
入力例 2
2 6 3
出力例 2
5
入力例 3
31 41 5
出力例 3
23
Score : 300 points
Problem Statement
You are given three integers A, B and C. Find the minimum number of operations required to make A, B and C all equal by repeatedly performing the following two kinds of operations in any order:
- Choose two among A, B and C, then increase both by 1.
- Choose one among A, B and C, then increase it by 2.
It can be proved that we can always make A, B and C all equal by repeatedly performing these operations.
Constraints
- 0 \leq A,B,C \leq 50
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the minimum number of operations required to make A, B and C all equal.
Sample Input 1
2 5 4
Sample Output 1
2
We can make A, B and C all equal by the following operations:
- Increase A and C by 1. Now, A, B, C are 3, 5, 5, respectively.
- Increase A by 2. Now, A, B, C are 5, 5, 5, respectively.
Sample Input 2
2 6 3
Sample Output 2
5
Sample Input 3
31 41 5
Sample Output 3
23
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
高橋君を含めた 10^{10^{10}} 人の参加者が 2 回のプログラミングコンテストに参加しました。 各コンテストでは全員に 1 位から 10^{10^{10}} 位までの相異なる順位がつきました。
参加者のスコアとは、2 回のコンテストでの順位を掛け合わせた値です。
次のクエリ Q 個に答えてください。
- i 個目のクエリでは、2 つの正の整数 A_i,B_i が与えられる。高橋君が 1 回目のコンテストで A_i 位、2 回目のコンテストで B_i 位を取ったと仮定して、高橋君よりスコアの小さい参加者の人数の最大値を求めよ。
制約
- 1 \leq Q \leq 100
- 1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
Q A_1 B_1 : A_Q B_Q
出力
クエリごとに、高橋君よりスコアの小さい参加者の人数の最大値を出力せよ。
入力例 1
8 1 4 10 5 3 3 4 11 8 9 22 40 8 36 314159265 358979323
出力例 1
1 12 4 11 14 57 31 671644785
1 回目のコンテストで x 位を、2 回目のコンテストで y 位を取った参加者を (x,y) で表すことにします。
1 つめのクエリでは、高橋君よりスコアの小さい参加者として (2,1) が考えられます。2 人以上のスコアが高橋君のスコアより小さくなることはないため、1 を出力します。
Score : 700 points
Problem Statement
10^{10^{10}} participants, including Takahashi, competed in two programming contests. In each contest, all participants had distinct ranks from first through 10^{10^{10}}-th.
The score of a participant is the product of his/her ranks in the two contests.
Process the following Q queries:
- In the i-th query, you are given two positive integers A_i and B_i. Assuming that Takahashi was ranked A_i-th in the first contest and B_i-th in the second contest, find the maximum possible number of participants whose scores are smaller than Takahashi's.
Constraints
- 1 \leq Q \leq 100
- 1\leq A_i,B_i\leq 10^9(1\leq i\leq Q)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Q A_1 B_1 : A_Q B_Q
Output
For each query, print the maximum possible number of participants whose scores are smaller than Takahashi's.
Sample Input 1
8 1 4 10 5 3 3 4 11 8 9 22 40 8 36 314159265 358979323
Sample Output 1
1 12 4 11 14 57 31 671644785
Let us denote a participant who was ranked x-th in the first contest and y-th in the second contest as (x,y).
In the first query, (2,1) is a possible candidate of a participant whose score is smaller than Takahashi's. There are never two or more participants whose scores are smaller than Takahashi's, so we should print 1.
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
非負整数からなる数列 A,B が与えられます。 A,B の長さはともに N であり、A の値の総和と B の値の総和は等しいです。 A の i 項目は A_i であり、B の i 項目は B_i です。
とざん君とげざん君は、以下の操作を繰り返します。
- もし A,B が列として等しいなら、繰り返しを終了する
- そうでない場合、まずとざん君が A の正の要素を 1 つ選び、1 減らす
- その後、げざん君が B の正の要素を 1 つ選び、1 減らす
- その後、ペットの高橋君に飴を 1 つ食べさせる
とざん君は繰り返しが終了するまでに高橋君に食べさせる飴の個数を最大に、げざん君は最小にしたいです。 両者最適に操作を行ったとき、高橋君に食べさせる飴の個数を求めてください。
制約
- 1 \leq N \leq 2 × 10^5
- 0 \leq A_i,B_i \leq 10^9(1\leq i\leq N)
- A,B の値の総和は等しい
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 : A_N B_N
出力
両者最適に操作を行ったとき、高橋君に食べさせる飴の個数を出力せよ。
入力例 1
2 1 2 3 2
出力例 1
2
両者最適に操作を行ったとき、操作は以下のように進みます。
- とざん君は A_1 を 1 減らす。
- げざん君は B_1 を 1 減らす。
- 高橋君に飴を 1 つ食べさせる。
- とざん君は A_2 を 1 減らす。
- げざん君は B_1 を 1 減らす。
- 高橋君に飴を 1 つ食べさせる。
- A,B が等しくなったので終了する。
入力例 2
3 8 3 0 1 4 8
出力例 2
9
入力例 3
1 1 1
出力例 3
0
Score : 700 points
Problem Statement
You are given sequences A and B consisting of non-negative integers. The lengths of both A and B are N, and the sums of the elements in A and B are equal. The i-th element in A is A_i, and the i-th element in B is B_i.
Tozan and Gezan repeats the following sequence of operations:
- If A and B are equal sequences, terminate the process.
- Otherwise, first Tozan chooses a positive element in A and decrease it by 1.
- Then, Gezan chooses a positive element in B and decrease it by 1.
- Then, give one candy to Takahashi, their pet.
Tozan wants the number of candies given to Takahashi until the process is terminated to be as large as possible, while Gezan wants it to be as small as possible. Find the number of candies given to Takahashi when both of them perform the operations optimally.
Constraints
- 1 \leq N \leq 2 × 10^5
- 0 \leq A_i,B_i \leq 10^9(1\leq i\leq N)
- The sums of the elements in A and B are equal.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 : A_N B_N
Output
Print the number of candies given to Takahashi when both Tozan and Gezan perform the operations optimally.
Sample Input 1
2 1 2 3 2
Sample Output 1
2
When both Tozan and Gezan perform the operations optimally, the process will proceed as follows:
- Tozan decreases A_1 by 1.
- Gezan decreases B_1 by 1.
- One candy is given to Takahashi.
- Tozan decreases A_2 by 1.
- Gezan decreases B_1 by 1.
- One candy is given to Takahashi.
- As A and B are equal, the process is terminated.
Sample Input 2
3 8 3 0 1 4 8
Sample Output 2
9
Sample Input 3
1 1 1
Sample Output 3
0
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
a,b,c からなる文字列 S が与えられます。次の操作を 0 回以上繰り返して作ることのできる文字列としてありうるものの個数を
998244353 で割ったあまりを求めてください。
- 1\leq i\leq |S|-1 かつ S の i 文字目と i+1 文字目が異なるような整数 i を選ぶ。S の i 文字目と i+1 文字目を両方、(
a,b,cのうち)そのどちらとも異なる文字で置き換える。
制約
- 2 \leq |S| \leq 2 × 10^5
- S は
a,b,cからなる
入力
入力は以下の形式で標準入力から与えられる。
S
出力
操作を繰り返して作ることのできる文字列としてありうるものの個数を 998244353 で割ったあまりを出力せよ。
入力例 1
abc
出力例 1
3
abc,aaa,ccc を作ることができます。
入力例 2
abbac
出力例 2
65
入力例 3
babacabac
出力例 3
6310
入力例 4
ababacbcacbacacbcbbcbbacbaccacbacbacba
出力例 4
148010497
Score : 700 points
Problem Statement
You are given a string S consisting of a,b and c. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:
- Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among
a,bandc).
Constraints
- 2 \leq |S| \leq 2 × 10^5
- S consists of
a,bandc.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.
Sample Input 1
abc
Sample Output 1
3
abc, aaa and ccc can be obtained.
Sample Input 2
abbac
Sample Output 2
65
Sample Input 3
babacabac
Sample Output 3
6310
Sample Input 4
ababacbcacbacacbcbbcbbacbaccacbacbacba
Sample Output 4
148010497