A - Cleaning Up 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

ストーリー

ある会社では、現在働きやすい環境づくりを目指している。そこで新入社員が入社する 4 月から、社内の掃除を毎週行うことにした。 しかしながら、掃除当番は簡単に決められるものではない。 たとえば 1 人に負担をかけすぎてはならないことや、まだ仕事に慣れていない新入社員の負担は特に少なくしなければならないことなど、様々な制約がある。 また、掃除当番の決め方は「X さんの次は Y さんか Z さん」のように覚えやすいものでなければならない。 できるだけ制約通りになるように、掃除当番の決め方を最適化せよ。

問題文

ある会社には N 人の社員がおり、それぞれ 0 から N-1 までの番号が付けられている。 あなたは、各社員 i (0 \leq i \leq N-1) について整数 a_i と b_i を決め (a_i=b_i でも構わない)、以下の規則で各週の掃除当番を割り当てることにした。

  • 最初の週は、社員 0 が掃除当番となる。
  • それ以降の週については、前週の掃除当番を社員 x とし、前週が終わった時点で社員 x が掃除当番に t 回割り当てられたとして、今週の掃除当番は次のように決まる。
    • t が奇数の場合: 社員 a_x
    • t が偶数の場合: 社員 b_x

各 i (0 \leq i \leq N-1) について、今後 L = 500\,000 週間に社員 i に掃除当番を割り当てる回数の目標値 T_i が与えられる。 実際に社員 i に割り当てられる掃除当番の回数を t_i とするとき、誤差 \left|t_0 - T_0\right| + \left|t_1 - T_1\right| + \cdots + \left|t_{N-1} - T_{N-1}\right| をできるだけ小さくせよ。

得点

出力した掃除当番の決め方における誤差を E とするとき、10^6-E 点が得られる。 ここで、得点が負の値にならないことが保証される。

合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のケースで不正な出力や制限時間超過をした場合、提出全体の判定が WA や TLE となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

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

N L
T_0 T_1 \cdots T_{N-1}
  • 全てのテストケースで、社員の数 N は 100 で固定である。
  • 全てのテストケースで、週数 L は 500\,000 で固定である。
  • 0 \leq T_i \leq 10\,000 を満たす。
  • T_0 + T_1 + \cdots + T_{N-1} = L を満たす。
  • 入力はすべて整数である。

出力

以下の形式で標準出力に出力せよ。

a_0 b_0
a_1 b_1
\vdots
a_{N-1} b_{N-1}

ここで 0 \leq a_i \leq N-1 および 0 \leq b_i \leq N-1 を満たさない i (0 \leq i \leq N-1) が存在する場合、WA と判定される。

例を見る

入力生成方法

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L, U) と表すとき、入力生成方法は次のようになる。

  1. 各 0 \leq i \leq N-2 について、T_i の値を T_i = \mathrm{rand}(0, 10000) により生成する。
  2. 総和 S=T_0+\cdots+T_{N-2} が 0\leq L-S\leq 10000 を満たすならば T_{N-1}=L-S として入力を確定させる。そうでなければ、1. に戻って生成をやり直す。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

Story

A company is currently aiming to create a comfortable working environment. It has decided to clean the office every week starting this April, when new employees join the company. However, assigning cleaning duties is not easy. There are various constraints, for example, the duty should not be concentrated on one person, and the burden on new employees, who are not yet accustomed to the work, should be especially low. Also, the assignment should be easy to remember, like "after employee X, the next must be employee Y or Z." Create a cleaning plan that follows the constraints as closely as possible.

Problem Statement

There are N employees in a company, numbered from 0 to N-1. For each employee i (0 \leq i \leq N-1), you must determine two integers a_i and b_i (a_i and b_i may be equal). Then, the cleaning plan for each week is created in the following way:

  • In the first week, employee 0 will do the cleaning.
  • From the second week onward, let employee x be the one who did the cleaning last week, and let t be the number of weeks in which employee x had been assigned as the cleaner by the end of last week. Then, this week's cleaning duty is determined as follows:
    • When t is odd: employee a_x
    • When t is even: employee b_x

For each i (0 \leq i \leq N-1), a target number of times T_i is given as the number of times employee i should be assigned cleaning duty in the next L = 500\,000 weeks. Let t_i be the actual number of times employee i is assigned cleaning duty. Create a cleaning plan that makes the error defined by \left|t_0 - T_0\right| + \left|t_1 - T_1\right| + \cdots + \left|t_{N-1} - T_{N-1}\right| as small as possible.

Scoring

Let E be the error in the output cleaning plan. You will obtain the score of 10^6 - E, which is guaranteed to be non-negative.

There are 150 testcases, and the score of a submission is the total score for each testcase. If your submission produces an illegal output or exceeds the time limit for some testcases, the submission itself will be judged as WA or TLE, and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

N L
T_0 T_1 \cdots T_{N-1}
  • The number of employees N is fixed to 100 across all testcases.
  • The number of weeks L is fixed to 500\,000 across all testcases.
  • 0 \leq T_i \leq 10\,000.
  • T_0 + T_1 + \cdots + T_{N-1} = L.
  • Given values are all integers.

Output

Output to Standard Output in the following format:

a_0 b_0
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Here, if there exists an i (0 \leq i \leq N-1) that does not satisfy 0 \leq a_i \leq N-1 or 0 \leq b_i \leq N-1, the output will be judged as WA.

Show example

Input Generation

Let \mathrm{rand}(L, U) be the function that generates a uniform random integer between L and U, inclusive. The input will be generated in the following algorithm:

  1. For each i (0 \leq i \leq N-2), generate T_i with \mathrm{rand}(0, 10000).
  2. If the sum S = T_0 + \cdots + T_{N-2} satisfies 0 \leq L - S \leq 10000, set T_{N-1} = L - S and finalize the input. Otherwise, retry step 1.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.