Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君は N 枚の AtCoder せんべいを K 人の AtCoder 参加者になるべく公平に配ることにしました。 N 枚すべてのせんべいを配るとき、せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)の最小値を求めてください。
制約
- 1 \leq N,K \leq 100
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)の最小値を出力せよ。
入力例 1
7 3
出力例 1
1
3 人にそれぞれ 2,2,3 枚の AtCoder せんべいを配った場合、せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)は 1 です。
入力例 2
100 10
出力例 2
0
均等に配ることができます。
入力例 3
1 1
出力例 3
0
Score : 100 points
Problem Statement
Takahashi has decided to distribute N AtCoder Crackers to K users of as evenly as possible. When all the crackers are distributed, find the minimum possible (absolute) difference between the largest number of crackers received by a user and the smallest number received by a user.
Constraints
- 1 \leq N,K \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the minimum possible (absolute) difference between the largest number of crackers received by a user and the smallest number received by a user.
Sample Input 1
7 3
Sample Output 1
1
When the users receive two, two and three crackers, respectively, the (absolute) difference between the largest number of crackers received by a user and the smallest number received by a user, is 1.
Sample Input 2
100 10
Sample Output 2
0
The crackers can be distributed evenly.
Sample Input 3
1 1
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 200 点
問題文
ABC 洋菓子店では, 1 個 4 ドルのケーキと 1 個 7 ドルのドーナツが売られている.
このとき, 合計金額が N ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.
制約
- N は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N
出力
合計が N ドルとなる買い方がある場合 Yes
, そうでない場合 No
と出力せよ.
入力例 1
11
出力例 1
Yes
ケーキを 1 個, ドーナツを 1 個買えば合計 4 + 7 = 11 ドルとなる.
入力例 2
40
出力例 2
Yes
ケーキを 10 個買えば 4 \times 10 = 40 ドルとなる.
入力例 3
3
出力例 3
No
ケーキの値段は 4 ドル, ドーナツの値段は 7 ドルと, どちらも 3 ドルより高いためそのような買い方は存在しない.
Score : 200 points
Problem Statement
La Confiserie d'ABC sells cakes at 4 dollars each and doughnuts at 7 dollars each. Determine if there is a way to buy some of them for exactly N dollars. You can buy two or more doughnuts and two or more cakes, and you can also choose to buy zero doughnuts or zero cakes.
Constraints
- N is an integer between 1 and 100, inclusive.
Input
Input is given from Standard Input in the following format:
N
Output
If there is a way to buy some cakes and some doughnuts for exactly N dollars, print Yes
; otherwise, print No
.
Sample Input 1
11
Sample Output 1
Yes
If you buy one cake and one doughnut, the total will be 4 + 7 = 11 dollars.
Sample Input 2
40
Sample Output 2
Yes
If you buy ten cakes, the total will be 4 \times 10 = 40 dollars.
Sample Input 3
3
Sample Output 3
No
The prices of cakes (4 dollars) and doughnuts (7 dollars) are both higher than 3 dollars, so there is no such way.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 N が与えられるので、N の -2 進数表現を求めてください。
ここで、S が N の -2 進数表現であるとは、以下を全て満たすことです。
- S は
0
および1
のみからなる文字列である - S =
0
でなければ S の先頭の文字は1
である - S = S_k S_{k-1} ... S_0 とすると、S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N が成り立つ
なお、任意の整数 M に対して M の -2 進数表現が一意に定まることが証明できます。
制約
- 入力はすべて整数である
- -10^9 \leq N \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N の -2 進数表現を出力せよ。
入力例 1
-9
出力例 1
1011
(-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9 なので 1011
は -9 の -2 進数表現です。
入力例 2
123456789
出力例 2
11000101011001101110100010101
入力例 3
0
出力例 3
0
Score : 300 points
Problem Statement
Given an integer N, find the base -2 representation of N.
Here, S is the base -2 representation of N when the following are all satisfied:
- S is a string consisting of
0
and1
. - Unless S =
0
, the initial character of S is1
. - Let S = S_k S_{k-1} ... S_0, then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N.
It can be proved that, for any integer M, the base -2 representation of M is uniquely determined.
Constraints
- Every value in input is integer.
- -10^9 \leq N \leq 10^9
Input
Input is given from Standard Input in the following format:
N
Output
Print the base -2 representation of N.
Sample Input 1
-9
Sample Output 1
1011
As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011
is the base -2 representation of -9.
Sample Input 2
123456789
Sample Output 2
11000101011001101110100010101
Sample Input 3
0
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 個の箱が左右一列に並んでおり、左から i 番目の箱には A_i 個のお菓子が入っています。
あなたは、連続したいくつかの箱からお菓子を取り出して M 人の子供たちに均等に配りたいと考えています。
そこで、以下を満たす組 (l, r) の総数を求めてください。
- l, r はともに整数であり 1 \leq l \leq r \leq N を満たす
- A_l + A_{l+1} + ... + A_r は M の倍数である
制約
- 入力は全て整数である
- 1 \leq N \leq 10^5
- 2 \leq M \leq 10^9
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N
出力
条件を満たす組 (l, r) の総数を出力せよ。
出力の際には、出力が 32 ビットの整数型に収まらない可能性があることに注意せよ。
入力例 1
3 2 4 1 5
出力例 1
3
各組 (l, r) に対する和 A_l + A_{l+1} + ... + A_r は次のとおりであり、このうち 3 つが 2 の倍数です。
- (1, 1) に対する和: 4
- (1, 2) に対する和: 5
- (1, 3) に対する和: 10
- (2, 2) に対する和: 1
- (2, 3) に対する和: 6
- (3, 3) に対する和: 5
入力例 2
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
出力例 2
6
入力例 3
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
25
Score : 400 points
Problem Statement
There are N boxes arranged in a row from left to right. The i-th box from the left contains A_i candies.
You will take out the candies from some consecutive boxes and distribute them evenly to M children.
Such being the case, find the number of the pairs (l, r) that satisfy the following:
- l and r are both integers and satisfy 1 \leq l \leq r \leq N.
- A_l + A_{l+1} + ... + A_r is a multiple of M.
Constraints
- All values in input are integers.
- 1 \leq N \leq 10^5
- 2 \leq M \leq 10^9
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_N
Output
Print the number of the pairs (l, r) that satisfy the conditions.
Note that the number may not fit into a 32-bit integer type.
Sample Input 1
3 2 4 1 5
Sample Output 1
3
The sum A_l + A_{l+1} + ... + A_r for each pair (l, r) is as follows:
- Sum for (1, 1): 4
- Sum for (1, 2): 5
- Sum for (1, 3): 10
- Sum for (2, 2): 1
- Sum for (2, 3): 6
- Sum for (3, 3): 5
Among these, three are multiples of 2.
Sample Input 2
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
Sample Output 2
6
Sample Input 3
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
25