の格子の各マスにリンゴが一つずつある。行は上から下へ、列は左から右へ から まで番号が付いている。
個のリンゴを好きな順番で一つずつ食べられる。初め、すべてのリンゴのおいしさは100である。リンゴを食べると、その時点のおいしさと同じ点数を得る。その後、まだ食べていないリンゴのうち、今食べたリンゴとのマンハッタン距離が2以下のものすべてのおいしさが、それぞれ0.9倍になる。
と のマンハッタン距離は である。おいしさの更新時に丸めや切り捨ては行わない。
得点の合計ができるだけ大きくなる順序を求めたい。すべてのマスをちょうど一回ずつ含む順序を出力した場合、リンゴから得た点数の合計がそのまま採点点数となる。基準となる満点は 点だが、得点に上限はなく、これを超える点数もそのまま獲得できる。 点以上なら AC と判定される。判定には表示用に丸めた値ではなく、正確な合計を使う。不正な順序は 点となる。
実際の採点データはすべて である。 は例にのみ使い、例では合計点が最大の順序を示す。 点の AC 基準は実際の採点データに適用する。
最初の行に整数 が与えられる。
リンゴを食べる順序を 行で出力せよ。 行目には、 番目に食べるリンゴの行番号 と列番号 を空白区切りで出力する。
この順序の合計点は で、 格子の最大値である。実際の採点データは のみである。
すべてのマスをちょうど一回ずつ出力すること。できるだけ合計点の高い順序を求めよ。点数そのものは出力しない。