C - Eat 4x
Ceylon
2
s
1024
MB
300
点
問題文
$T$ 個のテストケースについて、以下の問題を解いてください。
問題
カードの山があります。それぞれのカードには非負整数が $1$ つ書かれています。山にあるカードに書かれた非負整数は全部で $N$ 種類で、非負整数 $A_{i}$ が書かれたカードは $B_{i}$ 枚あります。このとき、次の操作を最大で何回行えるでしょうか。
- カードの山から、書かれた非負整数の和が $4$ の倍数になるように $1$ 枚以上のカードを選んで印をつける。そして、印をつけたすべてのカードを食べる。
制約
- 入力はすべて整数
- $1 \le T \le 2 \times 10^{5}$
- $1 \le N \le 2 \times 10^{5}$
- $0 \le A_{i} \le 10^{9}$
- $1 \le B_{i} \le 10^{12}$
- $A_{i} \neq A_{j} (i \neq j)$
- $1$ つの入力に含まれるテストケースについて、それらの $N$ の総和は $2 \times 10^{5}$ を超えない
入力
入力は標準入力から与えられる。入力の $1$ 行目は以下の形式である。
$T$
その後、 $T$ 個のテストケースが続く。各テストケースは以下の形式で与えられる。
$N$
$A_{1}$ $A_{2}$ $\ldots$ $A_{N}$
$B_{1}$ $B_{2}$ $\ldots$ $B_{N}$
出力
$T$ 行出力せよ。
$i (1 \le i \le T)$ 行目には、 $i$ 番目に入力されたテストケースに対する答えを出力せよ。
入力例 1
3
5
1 2 6 4 7
1 1 1 2 1
2
0 1
100 100
10
1 5 35 9 100 29 83 62 92834 233
30000000000 129832322130 39324933422 923 102930291 842981394 9439249833 287218322 92753024 999821738
出力例 1
4
125
77284834951
$1$ 番目のテストケースでは、食べるカードを $(4) \rightarrow (4) \rightarrow (2,6) \rightarrow (1,7)$ のようにすることで $4$ 回の操作を行うことができます。操作を $5$ 回以上行うことはできないため、これは最適な操作の一例です。
$2$ 番目のテストケースでは、例えば $0$ が書かれたカードを $1$ 枚ずつ食べたのちに $1$ が書かれたカードを $4$ 枚ずつまとめて食べることで、合計 $125$ 回の操作を行えます。
$3$ 番目のテストケースのように、入力や答えが $32$ bit整数に収まらないことがあるので注意してください。