Time Limit: 2 sec / Memory Limit: 256 MB
問題文
カガミズさんは息子のキュウリ君にあげるクリスマスプレゼントを考えています.
カガミズさんにはある懸念があります.キュウリ君は競技プログラミングが大好きなので,コンテストでよくある変な問題文に触発されて,プレゼントに配列が欲しいとかグラフが欲しいとか言われてしまうおそれがあるのです.
急に言われて慌てるよりは,早い内に聞いておくほうがよいと考えたカガミズさんは,クリスマスプレゼントにほしいものをキュウリ君に尋ねました.すると,キュウリ君は次のように答えました.
「今から言う問題に対する自然な問題設定がほしい!」
課題
1 次元空間上に N 個の点があり,i 番目の点 P_i の座標は X_i である.
いま,新たにいくつかの点を加えることで N 個の点がある条件を満たすようにしたい.その条件は N 要素の整数列 K, D によって次のように表される.
- 条件: i = 1, ..., N に対し,点 P_i から K_i 番目に近い点までの距離が D_i である.ただし,2 点間の距離はその座標の差の絶対値とする.
距離を考える点の対象は新たに加えた点だけではなく,元からある N 個の点も考慮する.つまり,ある点から 1 番近い点は自分自身と考えられる.
いくつかの点を加えることで上の条件を満たすことができるかどうかを判定せよ.もし可能な場合は,加える点の個数を 10^5 個以下にできるかどうかも判定し,それも可能な場合は加える点の座標の具体例を 1 つ求めよ.
ただし,X_i, D_i および加える点の座標はすべて整数であるとする.また,加える点の座標は 32 ビット符号付き整数の表現できる範囲内に収まっていなければならない.
元からある N 個の点や加える点については,同じ座標に複数の点があってもよいことに注意せよ.
制約
すべての入力データは以下の制約を満たす.
- 1 ≦ N ≦ 10^3.
- -10^9 ≦ X_i ≦ 10^9.
- 1 ≦ K_i ≦ 10^9.
- 0 ≦ D_i ≦ 10^9.
また,この問題には部分点が設定されており,2 点分の入力データは追加で以下の制約を満たす.
- N ≦ 10.
- K_i = 2.
入力
N X_1 K_1 D_1 : X_N K_N D_N
出力
どのように点を加えても問題の条件を満たせない場合は impossible
と出力せよ.
条件を満たすように点を加えることは可能だが,加える点の個数がどのようにしても 10^5 を超えてしまう場合は too many
と出力せよ.
10^5 個以下の点を加えることで条件を満たすことができる場合は,その具体例を以下のフォーマットで出力せよ.
M A_1 … A_M
ただし,M は加える点の個数で A_j は加える点の座標である.ここで,M の値は 10^5 以下であり,各 A_j の値は 32 ビット符号付き整数の表現できる範囲内に収まっていなければならない. また, 出力に際して余計な空行や空白があってはならない. (16 : 36 追記)
入力例1
2 0 2 1 2 2 1
出力例1
1 1
加える点の個数は 10^5 以下でありさえすれば最小である必要はないので,以下のような出力もこの問題では許可される.
2 -1 1
入力例2
2 0 2 1 3 2 1
出力例2
2 -1 2
入力例3
1 1 1 1
出力例3
impossible
ある点に最も近い点は自分自身であり,その距離は 0 であることに注意せよ.
入力例4
1 1 114514 1
出力例4
too many
たとえば座標 2 に 114,513 個の点を置けば条件を満たすことはできる.ただし,10^5 個以内では条件を満たすことができないため too many
を出力する.
入力例5
1 1 1 0
出力例5
0このケースに余計な空行を追加しないよう注意せよ. (16:36 追記)
Problem: japlj
Tester: kagamiz