第8回(OOP―第4回)
スライド
練習問題
K3 100周年にともなって, 計算技術研究会では長さ N の数列 a={a1,a2,a3,…,aN} が飾られることになった.
Nわか君は, この数列で遊んでみようと思った.
具体的には, 以下の操作をできるだけ多くの回数繰り返そうと思った.
code:rule
1≤i≤N を満たす全ての i に対して, それぞれ「ai の値を 2 で割る」「ai の値を 3 倍する」のどちらかを行う.
ただし, 全ての i に対して 3 倍することはできず, 操作後の ai の値は整数でなければならない.
最大で何回の操作が可能か, 求めなさい.
入力
code:input
a1 a2 a3 ... aN
数列がスペース区切りで与えられる。
出力例
出力例1
code:input
5 2 4
code:output
3
出力例2
code:input
631 577 243 199
code:output
0
出力例3
code:input
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776
code:output
39
発展問題
ABC洋菓子店では, N 種類のケーキを売っている.
各種類のケーキには「綺麗さ」「おいしさ」「人気度」の 3 つの値を持ち, i 種類目のケーキの綺麗さは xi, おいしさは yi, 人気度は zi である.
これらの値は 0 以下である可能性もある.
りんごさんは, ABC洋菓子店で M 個のケーキを食べることにした. 彼は次のように, 食べるケーキの組み合わせを選ぶことにした.
code:彼の選び方
同じ種類のケーキを 2 個以上食べない.
上の条件を満たしつつ, (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ.
このとき, りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を求めなさい.
code:制約
N は 1 以上 1 000 以下の整数
M は 0 以上 N 以下の整数
xi,yi,zi (1≤i≤N) は, それぞれ −10 000 000 000 以上 10 000 000 000 以下の整数.
入力は以下の形式で標準入力から与えられる.(順にinput()で打ち込まれると思えば良い。)
code:input
N M
x1 y1 z1
x2 y2 z2
: :
xN yN zN
りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を出力しなさい.
出力例
出力例1
code:input
5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
code:output
56
出力例2
code:input
5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15
code:output
54
出力例3
code:input
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
code:output
638
(出典:AtCoder Beginner Contest 100 C問題「*3 or /2」より一部改題/D問題「Patisserie ABC」)