Time Limit: 2 sec / Memory Limit: 976 MB
配点: 100 点
問題文
もうすぐ E869120 君と square1001 君の 16 才の誕生日が来る.
そこで, AtCoder 王国の高橋君は, 円形のケーキ 1 個に放射状に切れ目を入れ 16 等分したものを, 彼らにプレゼントした.
E869120 君はそのうち A 切れ、square1001 君は B 切れを食べようとした.
しかし, ケーキと一緒についていた紙を見ると, 「同じ人が隣り合う 2 切れのケーキを両方取ってはならない」と書かれていた.
さて、彼らは紙に書かれたことを守って、2 人とも食べたい数のケーキを取ることができるだろうか？
制約
- A, B は 1 以上 16 以下の整数
- A+B は 16 以下である.
入力
入力は以下の形式で標準入力から与えられる.
A B
出力
紙に書かれたことを守って, E869120 君と square1001 君両方が, 食べたい数のケーキを取ることができるならば Yay!, そうでなければ :( と出力しなさい.
入力例 1
5 4
出力例 1
Yay!
下の図のようにケーキを取れば、2 人とも目標を達成することができる.
入力例 2
8 8
出力例 2
Yay!
下の図のようにケーキを取れば、2 人とも目標を達成することができる.
入力例 3
11 4
出力例 3
:(
この場合, 残念ながら目標を達成する方法は 1 つもない.
Score: 100 points
Problem Statement
E869120's and square1001's 16-th birthday is coming soon.
Takahashi from AtCoder Kingdom gave them a round cake cut into 16 equal fan-shaped pieces.
E869120 and square1001 were just about to eat A and B of those pieces, respectively,
when they found a note attached to the cake saying that "the same person should not take two adjacent pieces of cake".
Can both of them obey the instruction in the note and take desired numbers of pieces of cake?
Constraints
- A and B are integers between 1 and 16 (inclusive).
- A+B is at most 16.
Input
Input is given from Standard Input in the following format:
A B
Output
If both E869120 and square1001 can obey the instruction in the note and take desired numbers of pieces of cake, print Yay!; otherwise, print :(.
Sample Input 1
5 4
Sample Output 1
Yay!
Both of them can take desired number of pieces as follows:
Sample Input 2
8 8
Sample Output 2
Yay!
Both of them can take desired number of pieces as follows:
Sample Input 3
11 4
Sample Output 3
:(
In this case, there is no way for them to take desired number of pieces, unfortunately.
Time Limit: 2 sec / Memory Limit: 976 MB
配点: 200 点
問題文
今日は, 記念すべき AtCoder Beginner Contest 100 が開催される. そのため, 高橋君はりんごさんに, ある整数をプレゼントしようと思った.
今日のコンテストは「AtCoder Beginner Contest 100」なので, りんごさんは 100 で ちょうど D 回割りきれる正の整数をプレゼントされると喜ぶ.
さて, りんごさんがプレゼントされると喜ぶような整数のうち N 番目に小さいものを求めなさい.
制約
- D は 0, 1, 2 のいずれかである
- N は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
D N
出力
100 でちょうど D 回割りきれる正の整数の中で N 番目に小さいものを出力しなさい.
入力例 1
0 5
出力例 1
5
100 でちょうど 0 回割り切れる（すなわち, 100 で割り切れない）整数は, 1, 2, 3, 4, 5, 6, 7, ... と続く.
よって, 5 番目に小さいりんごさんが喜ぶ整数は 5 である.
入力例 2
1 11
出力例 2
1100
100 でちょうど 1 回割り切れる整数は, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1 \ 000, 1 \ 100, ... と続く.
よって, 求めたい整数は 1 \ 100 である.
入力例 3
2 85
出力例 3
850000
100 でちょうど 2 回割り切れる整数は, 10 \ 000, 20 \ 000, 30 \ 000, ... と続く.
よって, 求めたい整数は 850 \ 000 である.
Score: 200 points
Problem Statement
Today, the memorable AtCoder Beginner Contest 100 takes place. On this occasion, Takahashi would like to give an integer to Ringo.
As the name of the contest is AtCoder Beginner Contest 100, Ringo would be happy if he is given a positive integer that can be divided by 100 exactly D times.
Find the N-th smallest integer that would make Ringo happy.
Constraints
- D is 0, 1 or 2.
- N is an integer between 1 and 100 (inclusive).
Input
Input is given from Standard Input in the following format:
D N
Output
Print the N-th smallest integer that can be divided by 100 exactly D times.
Sample Input 1
0 5
Sample Output 1
5
The integers that can be divided by 100 exactly 0 times (that is, not divisible by 100) are as follows: 1, 2, 3, 4, 5, 6, 7, ...
Thus, the 5-th smallest integer that would make Ringo happy is 5.
Sample Input 2
1 11
Sample Output 2
1100
The integers that can be divided by 100 exactly once are as follows: 100, 200, 300, 400, 500, 600, 700, 800, 900, 1 \ 000, 1 \ 100, ...
Thus, the integer we are seeking is 1 \ 100.
Sample Input 3
2 85
Sample Output 3
850000
The integers that can be divided by 100 exactly twice are as follows: 10 \ 000, 20 \ 000, 30 \ 000, ...
Thus, the integer we are seeking is 850 \ 000.
Time Limit: 2 sec / Memory Limit: 976 MB
配点: 300 点
問題文
AtCoder Beginner Contest 100 の開催にともなって, AtCoder 社では長さ N の数列 a = {a_1, a_2, a_3, ..., a_N} が飾られることになった.
社員のすぬけ君は, この数列で遊んでみようと思った.
具体的には, 以下の操作をできるだけ多くの回数繰り返そうと思った.
1 \leq i \leq N を満たす全ての i に対して, それぞれ「a_i の値を 2 で割る」「a_i の値を 3 倍する」のどちらかを行う. ただし, 全ての i に対して 3 倍することはできず, 操作後の a_i の値は整数でなければならない.
最大で何回の操作が可能か, 求めなさい.
制約
- N は 1 以上 10 \ 000 以下の整数
- a_i は 1 以上 1 \ 000 \ 000 \ 000 以下の整数
入力
入力は以下の形式で標準入力から与えられる.
N a_1 a_2 a_3 ... a_N
出力
すぬけ君が行える最大の操作回数を出力しなさい.
入力例 1
3 5 2 4
出力例 1
3
最初, 数列は {5, 2, 4} であるが, 以下のように操作すれば 3 回の操作を行うことができる.
- 最初に, a_1 を 3 倍し, a_2 を 3 倍し, a_3 を 2 で割る. すると数列は {15, 6, 2} となる.
- 次に, a_1 を 3 倍し, a_2 を 2 で割り, a_3 を 3 倍する. すると数列は {45, 3, 6} となる.
- 最後に, a_1 を 3 倍し, a_2 を 3 倍し, a_3 を 2 で割る. すると数列は {135, 9, 3} となる.
入力例 2
4 631 577 243 199
出力例 2
0
全ての要素が奇数なので, 操作はできない. よって答えは 0 である.
入力例 3
10 2184 2126 1721 1800 1024 2528 3360 1945 1280 1776
出力例 3
39
Score: 300 points
Problem Statement
As AtCoder Beginner Contest 100 is taking place, the office of AtCoder, Inc. is decorated with a sequence of length N, a = {a_1, a_2, a_3, ..., a_N}.
Snuke, an employee, would like to play with this sequence.
Specifically, he would like to repeat the following operation as many times as possible:
For every i satisfying 1 \leq i \leq N, perform one of the following: "divide a_i by 2" and "multiply a_i by 3". Here, choosing "multiply a_i by 3" for every i is not allowed, and the value of a_i after the operation must be an integer.
At most how many operations can be performed?
Constraints
- N is an integer between 1 and 10 \ 000 (inclusive).
- a_i is an integer between 1 and 1 \ 000 \ 000 \ 000 (inclusive).
Input
Input is given from Standard Input in the following format:
N a_1 a_2 a_3 ... a_N
Output
Print the maximum number of operations that Snuke can perform.
Sample Input 1
3 5 2 4
Sample Output 1
3
The sequence is initially {5, 2, 4}. Three operations can be performed as follows:
- First, multiply a_1 by 3, multiply a_2 by 3 and divide a_3 by 2. The sequence is now {15, 6, 2}.
- Next, multiply a_1 by 3, divide a_2 by 2 and multiply a_3 by 3. The sequence is now {45, 3, 6}.
- Finally, multiply a_1 by 3, multiply a_2 by 3 and divide a_3 by 2. The sequence is now {135, 9, 3}.
Sample Input 2
4 631 577 243 199
Sample Output 2
0
No operation can be performed since all the elements are odd. Thus, the answer is 0.
Sample Input 3
10 2184 2126 1721 1800 1024 2528 3360 1945 1280 1776
Sample Output 3
39
Time Limit: 2 sec / Memory Limit: 976 MB
配点: 400 点
問題文
高橋君はプロのパティシエになり, AtCoder Beginner Contest 100 を記念して, 「ABC洋菓子店」というお店を開いた.
ABC洋菓子店では, N 種類のケーキを売っている.
各種類のケーキには「綺麗さ」「おいしさ」「人気度」の 3 つの値を持ち, i 種類目のケーキの綺麗さは x_i, おいしさは y_i, 人気度は z_i である.
これらの値は 0 以下である可能性もある.
りんごさんは, ABC洋菓子店で M 個のケーキを食べることにした. 彼は次のように, 食べるケーキの組み合わせを選ぶことにした.
- 同じ種類のケーキを 2 個以上食べない.
- 上の条件を満たしつつ, (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ.
このとき, りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を求めなさい.
制約
- N は 1 以上 1 \ 000 以下の整数
- M は 0 以上 N 以下の整数
- x_i, y_i, z_i \ (1 \leq i \leq N) は, それぞれ -10 \ 000 \ 000 \ 000 以上 10 \ 000 \ 000 \ 000 以下の整数.
入力
入力は以下の形式で標準入力から与えられる.
N M x_1 y_1 z_1 x_2 y_2 z_2 : : x_N y_N z_N
出力
りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を出力しなさい.
入力例 1
5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 1
56
2, 4, 5 種類目のケーキを食べることを考える. そのとき, 「綺麗さ」「おいしさ」「人気度」の合計はそれぞれ次のようになる.
- 綺麗さ：1 + 3 + 9 = 13
- おいしさ：5 + 5 + 7 = 17
- 人気度：9 + 8 + 9 = 26
このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は 13 + 17 + 26 = 56 となり, これが最大になる.
入力例 2
5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15
出力例 2
54
1, 3, 5 種類目のケーキを食べることを考える. そのとき, 「綺麗さ」「おいしさ」「人気度」の合計はそれぞれ次のようになる.
- 綺麗さ：1 + 7 + 13 = 21
- おいしさ：(-2) + (-8) + (-14) = -24
- 人気度：3 + (-9) + 15 = 9
このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は 21 + 24 + 9 = 54 となり, これが最大になる.
入力例 3
10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82
出力例 3
638
3, 4, 5, 7, 10 種類目のケーキを食べると, 綺麗さの合計は -323, おいしさの合計は 66, 人気度の合計は 249 となる.
このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は 323 + 66 + 249 = 638 となり, これが最大になる.
入力例 4
3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000
出力例 4
30000000000
ケーキの綺麗さ, おいしさ, 人気度や出力すべき値が, 32bit 整数に収まらない場合もある.
Score: 400 points
Problem Statement
Takahashi became a pastry chef and opened a shop La Confiserie d'ABC to celebrate AtCoder Beginner Contest 100.
The shop sells N kinds of cakes.
Each kind of cake has three parameters "beauty", "tastiness" and "popularity". The i-th kind of cake has the beauty of x_i, the tastiness of y_i and the popularity of z_i.
These values may be zero or negative.
Ringo has decided to have M pieces of cakes here. He will choose the set of cakes as follows:
- Do not have two or more pieces of the same kind of cake.
- Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).
Find the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.
Constraints
- N is an integer between 1 and 1 \ 000 (inclusive).
- M is an integer between 0 and N (inclusive).
- x_i, y_i, z_i \ (1 \leq i \leq N) are integers between -10 \ 000 \ 000 \ 000 and 10 \ 000 \ 000 \ 000 (inclusive).
Input
Input is given from Standard Input in the following format:
N M x_1 y_1 z_1 x_2 y_2 z_2 : : x_N y_N z_N
Output
Print the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.
Sample Input 1
5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
Sample Output 1
56
Consider having the 2-nd, 4-th and 5-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:
- Beauty: 1 + 3 + 9 = 13
- Tastiness: 5 + 5 + 7 = 17
- Popularity: 9 + 8 + 9 = 26
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 13 + 17 + 26 = 56. This is the maximum value.
Sample Input 2
5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15
Sample Output 2
54
Consider having the 1-st, 3-rd and 5-th kinds of cakes. The total beauty, tastiness and popularity will be as follows:
- Beauty: 1 + 7 + 13 = 21
- Tastiness: (-2) + (-8) + (-14) = -24
- Popularity: 3 + (-9) + 15 = 9
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 21 + 24 + 9 = 54. This is the maximum value.
Sample Input 3
10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82
Sample Output 3
638
If we have the 3-rd, 4-th, 5-th, 7-th and 10-th kinds of cakes, the total beauty, tastiness and popularity will be -323, 66 and 249, respectively.
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is 323 + 66 + 249 = 638. This is the maximum value.
Sample Input 4
3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000
Sample Output 4
30000000000
The values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers.