問題一覧 > 通常問題

No.2110 012 Matching

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 160
作問者 : bayashikobayashiko / テスター : MtSakaMtSaka noiminoimi
1 ProblemId : 5519 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-28 21:08:23

問題文

$0$ が書かれたボールが $A$ 個、 $1$ が書かれたボールが $B$ 個、 $2$ が書かれたボールが $C$ 個あります。

あなたは残っているボールの個数の合計が $1$ 個以下になるまで以下の操作を繰り返します。

  • 残っているボールを $2$ つ選び、同時に食べる。食べたボールに書かれていた数字がそれぞれ $x,y$ だったとすると、 $(x+y)\bmod 3$ の満足度を得る。

ただし、 $a \bmod b$ は $a$ を $b$ で割った余りを表します。

上手く操作の手順を決めたときの、得られる満足度の総和の最大値を求めてください。

$1$ つの入力ファイルにつき $T$ 個のテストケースに答えてください。

入力

$T$
$case_1$
$case_2$
:
$case_T$
各テストケースは以下の形式で与えられます。
$A\ B\ C$

  • $1\le T \le 10^5$
  • $0\le A,B,C\le 10^{18}$
  • 入力はすべて整数

出力

答えを出力してください。 $i$ 行目には $i$ 個目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
3
1 1 2
1 1 1
1000000000000000000 1000000000000000000 1000000000000000000
出力
2
2
3000000000000000000

$1$ 個目のテストケースでは、例えば以下のように操作を行うと満足度の総和を最大化出来ます。

  • $0$ が書かれたボールと $1$ が書かれたボールを選び、食べる。 $(0+1)\bmod 3=1$ の満足度を得る。
  • $2$ が書かれたボールと $2$ が書かれたボールを選び、食べる。 $(2+2)\bmod 3=1$ の満足度を得る。

満足度の総和を $3$ 以上にすることは出来ないため、 $2$ と出力します。

$2$ 個目のテストケースでは、$0$ が書かれたボールと $2$ が書かれたボールを食べることにより、満足度の総和を $2$ に出来ます。

$1$ が書かれたボールが $1$ 個残りますが、ボールは $2$ つ同時にしか食べることが出来ないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。