ルールや注意点

• この問題に関するルールや注意点
  • この問題においては提出した解答が CE 以外の結果だった場合, そこから $5$ 分間はこの問題に対する提出を受け付けません.
  • スコアの順位は上のタブの「スコア順」, もしくは 順位表 からご覧ください.
  • コンテスト時間内に問題の考察や解答を公開する行為は禁止します. このコンテストの終了時刻は 2022/10/15 01:20 (JST) です.
  • ビジュアライザはありません.
  • コンテスト終了後にリジャッジやシステムテストは予定していません.
  • コンテスト時間内に提出された解答のうちの最高点をスコアとし, スコアの降順で順位付けします.
• コンテストに関するルールや注意点
  • この問題は yukicoder contest 364 (Do you know Cherry Contest?) 内の1問です. 時間配分に注意してください.
  • この問題の獲得点数は次のようにして定められます.
    • 未提出またはスコアが $0$ 点 $\cdots$ $0$ 点.
    • スコアが $1$ 点以上 $\cdots$ スコアが $1$ 点以上の人の順位で $R$ 位だった場合, $\left(100+\left \lfloor 800 \exp \left(-\dfrac{R-1}{25} \right) \right \rfloor \right)$ 点.

      順位と得点の組み合わせの例

      順位	1	2	3	4	5	10	15	20	25	30	35	40	45	50	60	70	80	90	100	125	150	200	$\cdots$
      得点	900	868	838	809	781	658	556	474	406	350	305	268	237	212	175	150	133	122	115	105	102	100	$\cdots$

ストーリー

離散モデル化された単振り子を考える.

いくつかの時刻が与えられるので, この時刻において離散振り子の重りがなるべく "左右に分かれている" 状態と, なるべく "まとまっている" 状態になるように離散振り子を作ってほしい.

ただし, 空気抵抗をモデル化に組み込んだため, 時々刻々と重りの振幅は小さくなってしまうことに注意してほしい.

問題文

下図のような $N$ 個の離散振り子 (この問題だけの造語である) $P_1, \dots, P_N$ がある. 各 $P_i$ は座標軸と1つのコマからなる.

あなたは各 $P_i$ に対して, 初期振幅 $B_i$, 最小振幅 $M_i$, 減衰振幅 $E_i$ を以下を満たす範囲で自由に設定することができる.

• $B_i, M_i, E_i$ は整数.
• $1 \leq M_i \leq B_i \leq 10^9$
• $1 \leq E_i \leq 10^9$

各離散振り子 $P_i$ は以下のように動く.

• 時刻 $0$ の時点ではコマは座標 $0$ にある.
• 時刻 $0$ の時点での振幅 $A_i$ は $A_i \gets B_i$ である. また, 方向を表す整数を $D_i$ とし, $D_i \gets 1$ とする.
• 時刻 $0.5, 1.5, 2.5, \dots, n-0.5~(n$ は正の整数 $), \dots$ において以下のことが起こる.
  • コマが座標 $x$ にあるとき, コマを座標 $y:=(x+D_i)$ に移動させる.
  • $y=D_iA_i$ ならば, 以下のことを行う.
    • $D_i \gets -D_i$
    • $A_i \gets \max (M_i, A_i-E_i)$

あなたの目標はこの $N$ 個の離散振り子を時刻 $T_1, \dots, T_K, U_1, \dots, U_K$ に撮るので, なるべく以下を達成するような離散振り子を作って欲しい.

• 時刻 $T_1, \dots, T_K$ では対立の写真を撮る. この写真ではなるべくコマが左右に分かれていてほしい.
• 時刻 $U_1, \dots, U_K$ では協調の写真を撮る. この写真ではなるべくコマが1箇所にまとまっていてほしい.

なお, 撮る写真は対立の写真と協調の写真が交互である (どちらが最初かはテストケースによる). また, ある時刻に写真を撮った場合, 次の写真を撮る時刻はそこから少なくとも $\Delta$ 以上待つ.

下図に例として $B_i=10, M_i=3, E_i=2$ の離散振り子の動きを図示した表を載せておく.

制約

• $N$ は $50$ で固定.
• $K$ は $50$ で固定.
• $\Delta$ は $200$ で固定 (ただし, 入力では与えられない).
• 次の (条件 1), (条件 2) のうちどちらか (一方のみ) が成立する.
  • (条件 1)
    • $0 \leq T_1 \lt U_1 \lt T_2 \lt U_2 \lt \dots \lt T_K \lt U_K \leq 10^9$.
    • $T_i-U_{i-1} \geq \Delta \quad (i=1,2, \dots, K)$. ただし, $U_0=0$ とする.
    • $U_i-T_i \geq \Delta \quad (i=1,2, \dots, K)$.
  • (条件 2)
    • $0 \leq U_1 \lt T_1 \lt U_2 \lt T_2 \lt \dots \lt U_K \lt T_K \leq 10^9$
    • $U_i-T_{i-1} \geq \Delta \quad (i=1,2, \dots, K)$. ただし, $T_0=0$ とする.
    • $T_i-U_i \geq \Delta \quad (i=1,2, \dots, K)$.

得点

$2K$ 枚の写真それぞれについて以下のようにして写真に対する素点 $R$ を定める. ただし, 各写真について写っている $i$ 番目の離散振り子の座標を $X_i$ とする.

• 対立の写真の場合: $\displaystyle R:=\operatorname{round} \left(\dfrac{2 \times 10^7}{N(N-1)} \times \sum_{i=1}^{N-1} \sum_{k=i+1}^N \dfrac{\left|X_i-X_k \right|}{B_i+B_k} \right)$
• 協調の写真の場合: $\displaystyle R:=\operatorname{round} \left(\dfrac{10^7}{\displaystyle \sqrt{\left ( \dfrac{1}{20}\max_{1 \leq i \lt k \leq N} \left|X_i-X_k \right| \right ) +1}} \right)$

対立の写真 $K$ 枚に対する素点の平均を $S_{{\rm confrontation}}$, 協調の写真 $K$ 枚に対する素点の平均を $S_{{\rm cooperation}}$ としたとき (共に四捨五入で整数にする) , 積 $S_{{\rm confrontation}} \times S_{{\rm cooperation}}$ をこのテストケースの得点とする.

テストケースは全部で $50$ 個であり, 各テストケースにおける得点の総和がその提出の得点となる. ただし, $1$ 個以上のテストケースにおいて AC 以外の判定になった場合は他のテストケースに結果に関わらず, その提出の得点は $0$ 点とする. コンテスト時間中に得た最高得点で最終順位が決定され, コンテスト終了後のシステムテストは行われない. なお, 同じ得点を複数の参加者が得た場合はその得点を獲得した提出の早い方が上位とする.

入力

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

$N$ $K$
$T_1$ $T_2$ $\cdots$ $T_K$
$U_1$ $U_2$ $\cdots$ $U_K$

出力

出力は $N$ 行からなる.

$i$ 行目 $(1 \leq i \leq N)$ には $i$ 番目の離散振り子における初期振幅 $B_i$, 最小振幅 $M_i$, 減衰振幅 $E_i$ をこの順に空白区切りで出力せよ.

$N$ 行目の後にも改行を忘れないこと.

$B_1$ $M_1$ $E_1$
$B_2$ $M_2$ $E_2$
$\vdots$
$B_N$ $M_N$ $E_N$

なお, $N$ 行より多く出力した場合は最初の $N$ 行のみを用いてジャッジする.

また, この形式に従わない出力に対するジャッジの結果は不定である (WA, RE になるとも限らない).

入力生成方法

$0$ 以上 $1$ 未満の倍精度浮動小数点数を一様ランダムに生成する関数を $\operatorname{rand}()$ とする.

また, 各テストケースの作成において, テストケース番号 ${\rm id}$ ($1$ 以上 $50$ 以下 (2022/10/14 23:30 追記)) が生成時に与えられる.

$N, K, \Delta$ の生成方法

$N \gets 50, K \gets 50, \Delta \gets 200$ とする.

$T_j, U_j$ の生成方法

$2K$ 個の実数 $F_1, F_2, \dots, F_{2K}$ をそれぞれ $F_j \gets \operatorname{rand}()~(j=1,2, \dots, 2K)$ とする. ただし, $F_j=0$ であるような $j$ についてはそのような $j$ に対して $F_j$ の生成をやり直す. そして, $G_0, \dots, G_{2K}$ を以下のようにして設定する.

• $G_0=0$
• $G_j=\operatorname{round} \left(G_{j-1}+\dfrac{\Delta}{F_j} \right)$

• ${\rm id}$ が奇数のとき, $T_j \gets G_{2j-1}, U_j \gets G_{2j}$.
• ${\rm id}$ が偶数のとき, $T_j \gets G_{2j}, U_j \gets G_{2j-1}$.

例

50 50
643 2273 2952 4329 4922 7885 50581 52055 64796 65770 66449 68315 69508 70381 72692 73163 73729 81456 82537 83376 85326 86242 87664 88896 89494 90464 91043 92064 94327 99677 100710 101619 102734 103385 104377 105917 107307 107715 109032 109955 112314 112952 113540 114330 115094 121702 125533 126606 127354 128119
213 947 2499 4015 4564 5217 8137 51427 61121 65495 66213 66938 69269 70000 70597 72949 73444 75618 82172 82764 85099 85993 87137 88675 89115 89819 90683 91695 92337 96181 99895 101241 102008 103166 103609 104938 107097 107515 108155 109456 110935 112571 113152 113922 114541 115365 125327 125826 127137 127698

836 746 22
460 421 10
487 346 113
396 256 74
846 622 96
730 314 15
971 703 56
838 449 307
583 215 320
420 197 114
535 110 137
682 589 13
597 172 61
992 830 95
629 206 10
459 395 33
869 251 599
528 479 12
684 138 196
159 156 0
763 445 200
922 776 19
679 567 4
588 460 107
884 663 197
505 475 6
488 113 187
800 617 7
553 104 110
961 626 331
617 522 75
969 250 110
982 377 331
873 658 109
820 431 377
902 778 98
664 606 33
271 165 27
788 163 272
762 438 65
458 375 31
360 148 52
375 309 56
635 554 73
510 349 63
285 152 129
660 615 45
995 380 585
853 798 24
921 601 205