問題一覧 > 通常問題

No.814 ジジ抜き

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 64 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 53
作問者 : Lepton_sLepton_s / テスター : 37zigen37zigen
2 ProblemId : 2097 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-04-12 21:53:45

問題文

イルカちゃんは、動画を投稿するためにジジ抜きで遊ぼうとしています。 イルカちゃんはエコロケーションでカードに書かれている数を知ることができるため、ゲームが始まる前に「ジジ」となる数を計算しようとしています。

イルカちゃんは、$N$ 人でジジ抜きを始めようとしています。 手札は既に配られていて、対になっていた手札は全て捨てられています。
プレイヤー $i$ は手札を$K_i$枚持っていて、書かれている整数は、$\{L_i, L_i+2^{D_i}, L_i+2\times 2^{D_i}, \cdots, L_i+(K_i-1)\times 2^{D_i}\}$ となっています。
ある整数 $x$ が存在していて、「$x$ が書かれているカードを所持しているプレイヤーは奇数人で、$x$ 以外のすべての整数 $y$ について、$y$ が書かれているカードを所持しているプレイヤーは偶数人」です。 $x$ を求めてください。

補足 (読まなくても大丈夫です):
この問題のジジ抜きでは、現実のトランプとは異なり、カードに書かれている数は、$0$ 以上 $10^{18}$ 以下であり、それぞれの種類のカードは $10^{100}$ 枚ずつあります。
$x$ が書かれたカードを 1 枚だけ取り除いてから、残りのすべてのカードを $N$ 人のプレイヤーに配ります。それぞれのプレイヤー毎に配られるカードの枚数は均等である必要はありません。
それぞれのプレイヤーは手札が配られたあと、「同じ数が書かれた手札のペアを見つけて、そのペアを両方とも捨てる」という操作を、操作が行えなくなるまで繰り返します。

入力

$N$
$K_1$ $L_1$ $D_1$
$\dots$
$K_N$ $L_N$ $D_N$

$1$ $\le$ $N$ $\le$ $3 \times 10^5$
$K_i$ $\ge$ $1$
$0$ $\le$ $D_i$ $\le$ $59$
$0$ $\le$ $L_i$ $\le$ $L_i+(K_i-1)*2^{D_i}$ $\le$ $10^{18}$
全て整数
1 行目に $N$ が与えられ、
続く $N$ 行にプレイヤー $i$ の手札の情報が与えられる。
問題文に書かれている $x$ がただ一つ存在する。

出力

答えを 1 行で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
1 1 50
出力
1

一人しかいない場合もあります。 $\{1\}$ のカードを持っています。

サンプル2
入力
2
5 1 0
6 0 0
出力
0

1 人目は、$\{1, 2, 3, 4, 5\}$ のカードを持っていて、
2 人目は、$\{0, 1, 2, 3, 4, 5\}$ のカードを持っています。

サンプル3
入力
3
6 1 0
3 1 1
2 2 2
出力
4

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