A - Cleaning Up

Contest Duration: 2025-03-16(Sun) 10:00 - 2025-03-16(Sun) 14:00 (local time) (240 minutes) Back to Home

A - Cleaning Up Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

ストーリー

ある会社では、現在働きやすい環境づくりを目指している。そこで新入社員が入社する 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)$ と表すとき、入力生成方法は次のようになる。

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

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

Web版: ローカル版より高性能でアニメーション表示が可能です。
ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。

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

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:

For each $i$ $(0 \leq i \leq N-2)$ , generate $T_i$ with $\mathrm{rand}(0, 10000)$ .
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)

Web version: This is more powerful than the local version providing animations.
Local version: You need a compilation environment of Rust language.
- Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.

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