A - Banned X 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ 9 の非負整数列 A=(A_1,A_2,\dots,A_9) が与えられます。ここで、2\leq \sum_{i=1}^{9}A_i が保証されます。

あなたは、A の要素を 1 つ選び 1 加算する操作を 0 回以上好きな回数行うことができます。

以下の条件をすべて満たす正整数列 S が存在するようにするために、最小で何回の操作が必要ですか。

  • S の要素はすべて 1 以上 9 以下である。
  • 1\leq i\leq 9 なる整数 i について、S に i がちょうど A_i 個含まれる。（したがって、S の長さは \sum_{i=1}^{9}A_i である。）
  • どの隣接する 2 要素の和も 10 にならない。

ただし、有限回の操作で目標を達成できることが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1\leq T\leq 10^3
  • 0\leq A_i\leq 10^9 (1\leq i\leq 9)
  • 2\leq \sum_{i=1}^{9}A_i
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

A_1 A_2 \dots A_9

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、答えを出力せよ。

入力例 1

2
0 0 0 1 0 1 0 0 0
2 1 1 0 0 0 0 0 0

出力例 1

1
0

1 番目のテストケースについて、はじめの状態では、最後の条件以外を満たす S としてあり得るものは (4,6) または (6,4) で、いずれも最後の条件を満たしません。A_8 を選び 1 加算することで、S=(6,8,4) がすべての条件を満たすようになります。

2 番目のテストケースについて、操作をするまでもなく S=(1,2,3,1) が条件を満たしています。

Score : 500 points

Problem Statement

You are given a length-9 sequence of non-negative integers A=(A_1,A_2,\dots,A_9). It is guaranteed that 2\leq \sum_{i=1}^{9}A_i.

You can perform the following operation any number of times (possibly zero): choose one element of A and add 1 to it.

What is the minimum number of operations required so that there exists a sequence of positive integers S satisfying all of the following conditions?

  • All elements of S are between 1 and 9, inclusive.
  • S contains exactly A_i occurrences of i for each integer i such that 1\leq i\leq 9. (Thus, the length of S is \sum_{i=1}^{9}A_i.)
  • No two adjacent elements sum to 10.

It can be proved that the goal can be achieved in a finite number of operations.

You are given T test cases; solve each of them.

Constraints

  • 1\leq T\leq 10^3
  • 0\leq A_i\leq 10^9 (1\leq i\leq 9)
  • 2\leq \sum_{i=1}^{9}A_i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

A_1 A_2 \dots A_9

Output

Output T lines.

The i-th line should contain the answer for the i-th test case.

Sample Input 1

2
0 0 0 1 0 1 0 0 0
2 1 1 0 0 0 0 0 0

Sample Output 1

1
0

For the first test case, initially, the possible values of S satisfying all conditions except the last one are (4,6) and (6,4), neither of which satisfies the last condition. By choosing A_8 and adding 1 to it, S=(6,8,4) satisfies all conditions.

For the second test case, S=(1,2,3,1) satisfies the conditions without any operations.