Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
3 個の整数 A_1, A_2, A_3 が与えられます。
A_1+A_2+A_3 が 22 以上なら bust、21 以下なら win を出力してください。
制約
- 1 \leq A_i \leq 13 \ \ (i=1,2,3)
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
A_1 A_2 A_3
出力
A_1+A_2+A_3 が 22 以上なら bust、21 以下なら win を出力せよ。
入力例 1
5 7 9
出力例 1
win
5+7+9=21 なので win を出力します。
入力例 2
13 7 2
出力例 2
bust
13+7+2=22 なので bust を出力します。
Score : 100 points
Problem Statement
Given are three integers A_1, A_2, and A_3.
If A_1+A_2+A_3 is greater than or equal to 22, print bust; otherwise, print win.
Constraints
- 1 \leq A_i \leq 13 \ \ (i=1,2,3)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A_1 A_2 A_3
Output
If A_1+A_2+A_3 is greater than or equal to 22, print bust; otherwise, print win.
Sample Input 1
5 7 9
Sample Output 1
win
5+7+9=21, so print win.
Sample Input 2
13 7 2
Sample Output 2
bust
13+7+2=22, so print bust.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高八士君は回文が大好きで、回文でない文字列が許せません。高八士君は文字列を 1 回ハグするごとに、文字列から 1 文字を選んで任意の文字に変えることができます。
文字列 S が与えられます。S を回文にするために必要なハグの最小回数を答えてください。
制約
- S は半角英小文字のみから成る文字列
- S の長さは 1 以上 100 以下
入力
入力は以下の形式で標準入力から与えられます。
S
出力
S を回文にするために必要なハグの最小回数を出力してください。
入力例 1
redcoder
出力例 1
1
たとえば、4 文字目を o に変えて redooder にすることで回文になります。
入力例 2
vvvvvv
出力例 2
0
一度も文字を変えなくてよい場合もあります。
入力例 3
abcdabc
出力例 3
2
Score : 200 points
Problem Statement
Takahashi loves palindromes. Non-palindromic strings are unacceptable to him. Each time he hugs a string, he can change one of its characters to any character of his choice.
Given is a string S. Find the minimum number of hugs needed to make S palindromic.
Constraints
- S is a string consisting of lowercase English letters.
- The length of S is between 1 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print the minimum number of hugs needed to make S palindromic.
Sample Input 1
redcoder
Sample Output 1
1
For example, we can change the fourth character to o and get a palindrome redooder.
Sample Input 2
vvvvvv
Sample Output 2
0
We might need no hugs at all.
Sample Input 3
abcdabc
Sample Output 3
2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
1 から N までの番号がついた N 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。
人 i は A_i 個の証言を行っています。人 i の j 個目の証言は 2 つの整数 x_{ij} , y_{ij} で表され、y_{ij} = 1 のときは「人 x_{ij} は正直者である」という証言であり、y_{ij} = 0 のときは「人 x_{ij} は不親切な人である」という証言です。
この N 人の中には最大で何人の正直者が存在し得るでしょうか？
制約
- 入力は全て整数
- 1 ≤ N ≤ 15
- 0 \leq A_i \leq N - 1
- 1 \leq x_{ij} \leq N
- x_{ij} \neq i
- x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)
- y_{ij} = 0, 1
入力
入力は以下の形式で標準入力から与えられる。
N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}
出力
存在し得る正直者の最大人数を出力せよ。
入力例 1
3 1 2 1 1 1 1 1 2 0
出力例 1
2
人 1 と人 2 が正直者であり、人 3 が不親切な人であると仮定すると、正直者は 2 人であり、矛盾が生じません。これが存在し得る正直者の最大人数です。
入力例 2
3 2 2 1 3 0 2 3 1 1 0 2 1 1 2 0
出力例 2
0
1 人でも正直者が存在すると仮定すると、直ちに矛盾します。
入力例 3
2 1 2 0 1 1 0
出力例 3
1
Score : 300 points
Problem Statement
There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.
Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.
How many honest persons can be among those N people at most?
Constraints
- All values in input are integers.
- 1 \leq N \leq 15
- 0 \leq A_i \leq N - 1
- 1 \leq x_{ij} \leq N
- x_{ij} \neq i
- x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)
- y_{ij} = 0, 1
Input
Input is given from Standard Input in the following format:
N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}
Output
Print the maximum possible number of honest persons among the N people.
Sample Input 1
3 1 2 1 1 1 1 1 2 0
Sample Output 1
2
If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.
Sample Input 2
3 2 2 1 3 0 2 3 1 1 0 2 1 1 2 0
Sample Output 2
0
Assuming that one or more of them are honest immediately leads to a contradiction.
Sample Input 3
2 1 2 0 1 1 0
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の整数があり、i 番目の整数は A_i です。
\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j) を 10^9+7 で割った余りを求めてください。
\text{ XOR } とは
整数 A, B のビットごとの排他的論理和 a \text{ XOR } b は、以下のように定義されます。
- a \text{ XOR } b を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
制約
- 2 \leq N \leq 3 \times 10^5
- 0 \leq A_i < 2^{60}
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j) を 10^9+7 で割った余りを出力せよ。
入力例 1
3 1 2 3
出力例 1
6
(1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6 となります。
入力例 2
10 3 1 4 1 5 9 2 6 5 3
出力例 2
237
入力例 3
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
出力例 3
103715602
和を 10^9+7 で割った余りを出力してください。
Score : 400 points
Problem Statement
We have N integers. The i-th integer is A_i.
Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j), modulo (10^9+7).
What is \text{ XOR }?
The XOR of integers A and B, A \text{ XOR } B, is defined as follows:
- When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 0 \leq A_i < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j), modulo (10^9+7).
Sample Input 1
3 1 2 3
Sample Output 1
6
We have (1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6.
Sample Input 2
10 3 1 4 1 5 9 2 6 5 3
Sample Output 2
237
Sample Input 3
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
Sample Output 3
103715602
Print the sum modulo (10^9+7).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と呼びます。
マス (i,j) には 2 つの数 A_{ij}, B_{ij} が書かれています。
高橋君はまず各マスについて、2 つの数の一方を赤く、もう一方を青く塗ります。
そのあと、マス (1,1) からマス (H,W) まで移動します。高橋君は 1 回の行動でマス (i,j) からマス (i+1,j) またはマス (i,j+1) に動くことができます。グリッドからはみ出すような移動はできません。
このときの移動経路 (マス (1,1) とマス (H,W) を含む) について、「経路上のマスの赤く塗られた数の和」と「経路上のマスの青く塗られた数の和」の差の絶対値を 偏り と呼ぶことにします。
高橋君は、色の塗り方と移動経路を適切に選ぶことで偏りを小さくしたいです。
偏りの最小値を求めてください。
制約
- 2 \leq H \leq 80
- 2 \leq W \leq 80
- 0 \leq A_{ij} \leq 80
- 0 \leq B_{ij} \leq 80
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}
出力
偏りの最小値を求めよ。
入力例 1
2 2 1 2 3 4 3 4 2 1
出力例 1
0
次のような塗り分けと移動経路を選択すると、経路上のマスの赤く塗られた数の和は 3+3+1=7、経路上のマスの青く塗られた数の和は 1+2+4=7 となり、偏りを 0 にできます。
入力例 2
2 3 1 10 80 80 10 1 1 2 3 4 5 6
出力例 2
2
Score : 500 points
Problem Statement
We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
The square (i, j) has two numbers A_{ij} and B_{ij} written on it.
First, for each square, Takahashi paints one of the written numbers red and the other blue.
Then, he travels from the square (1, 1) to the square (H, W). In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1). He must not leave the grid.
Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W).
Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.
Find the minimum unbalancedness possible.
Constraints
- 2 \leq H \leq 80
- 2 \leq W \leq 80
- 0 \leq A_{ij} \leq 80
- 0 \leq B_{ij} \leq 80
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
H W
A_{11} A_{12} \ldots A_{1W}
:
A_{H1} A_{H2} \ldots A_{HW}
B_{11} B_{12} \ldots B_{1W}
:
B_{H1} B_{H2} \ldots B_{HW}
Output
Print the minimum unbalancedness possible.
Sample Input 1
2 2 1 2 3 4 3 4 2 1
Sample Output 1
0
By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7, respectively, for the unbalancedness of 0.
Sample Input 2
2 3 1 10 80 80 10 1 1 2 3 4 5 6
Sample Output 2
2
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さ N の整数列 A があり、A_1 = X, A_{i+1} = A_i + D (1 \leq i < N ) が成り立っています。
高橋君はこの整数列の要素をいくつか選んで取り、残り全てを青木君が取ります。2 人のどちらかが全てを取ることになっても構いません。
高橋君の取った数の和を S, 青木君の取った数の和を T としたとき、S - T として考えられる値は何通りあるでしょうか。
制約
- -10^8 \leq X, D \leq 10^8
- 1 \leq N \leq 2 \times 10^5
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X D
出力
S - T として考えられる値の種類数を出力せよ。
入力例 1
3 4 2
出力例 1
8
A は (4, 6, 8) です。
(高橋君, 青木君) の取り方は、 ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), ((4, 6, 8), ())
の 8 通りあります。
S - T はそれぞれ -18, -10, -6, -2, 2, 6, 10, 18 であるので、値の種類数は 8 です。
入力例 2
2 3 -3
出力例 2
2
A は (3, 0) であり、S - T として考えられる値は -3, 3 で、種類数は 2 です。
入力例 3
100 14 20
出力例 3
49805
Score : 600 points
Problem Statement
We have an integer sequence A of length N, where A_1 = X, A_{i+1} = A_i + D (1 \leq i < N ) holds.
Takahashi will take some (possibly all or none) of the elements in this sequence, and Aoki will take all of the others.
Let S and T be the sum of the numbers taken by Takahashi and Aoki, respectively. How many possible values of S - T are there?
Constraints
- -10^8 \leq X, D \leq 10^8
- 1 \leq N \leq 2 \times 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X D
Output
Print the number of possible values of S - T.
Sample Input 1
3 4 2
Sample Output 1
8
A is (4, 6, 8).
There are eight ways for (Takahashi, Aoki) to take the elements: ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), and ((4, 6, 8), ()).
The values of S - T in these ways are -18, -10, -6, -2, 2, 6, 10, and 18, respectively, so there are eight possible values of S - T.
Sample Input 2
2 3 -3
Sample Output 2
2
A is (3, 0). There are two possible values of S - T: -3 and 3.
Sample Input 3
100 14 20
Sample Output 3
49805