A - Apple Incremental Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

APPLE ARTIS社（通称 AA社）は、りんごの大量生産を生業とする企業である。このたび、長年の研究の成果により、無からりんごを生み出す革新的な機械の開発に成功した。

しかし、この機械を用いてりんごを本格的に大量生産するには、機械そのものを大量に生産する必要がある。そこでAA社は、りんご生産機を生産するための機械生産機、さらにその機械生産機を生産するための機械生産機生産機、というように階層的に機械を生み出す仕組みを構築した。

AA社のエンジニアであるあなたは、これらの階層的な機械群を活用し、できるだけ多くのりんごを生産するための生産計画アルゴリズムを構築する任務を任された。

問題文

N 種類のIDと L 種類のLevelからなる N \times L 種類の機械が存在し、Levelが i、IDが j の機械を機械 j^i と呼ぶ（0 \leq i < L,\ 0 \leq j < N）。

機械 j^0 の生産能力は A_j である。また、機械 j^i の初期コストは C_{i,j} である。

以下の生産計画の手順に従い、全 T ターン終了時点でのりんごの総数を最大化することが目的である。

生産計画の手順

機械 j^i の個数を B_{i,j} とし、計画開始時点ではすべて 1 である。 また、機械 j^i のパワーを P_{i,j} とし、開始時点ではすべて 0 である。

計画開始時点でのりんごの数は K である。 各ターンは以下の手順で進行する。

  1. あなたは以下の2つの行動のうちいずれか1つを選択する。
    • 機械 j^i を強化する：りんごを C_{i,j} \times (P_{i,j} + 1) 消費し、P_{i,j} を1増やす。ただし、りんごの数が負になるような強化は行えない。
    • 何もしない。
  2. Level 0, 1, 2, 3 の順に、すべての機械 j^i について以下の処理を行う。
    • Level 0 の機械（i = 0）の場合：
      • りんごを A_j \times B_{i,j} \times P_{i,j} 増加させる。
    • Level 1 以上の機械（i \geq 1）の場合：
      • B_{i-1,j} を B_{i,j} \times P_{i,j} 増加させる。

上手に行動を選択し、T ターン終了時点でのりんごの数をできるだけ多くしてほしい。

得点

T ターン後の時点におけるりんごの数を S としたとき、\mathrm{round}(10^5 \times \log_2 S) の得点が得られる。 得点は大きいほど良い。

以下の場合、WAとなる。

  • りんごの数が 0 未満になるような強化を行った場合
  • 存在しない機械のLevelまたはIDを指定した場合
  • 行動回数が T 未満の場合

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

入力

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

N L T K
A_0 A_1 \cdots A_{N-1}
C_{0,0} C_{0,1} \cdots C_{0,N-1}
C_{1,0} C_{1,1} \cdots C_{1,N-1}
\vdots
C_{L-1,0} C_{L-1,1} \cdots C_{L-1,N-1}
  • 1行目には、4つの整数 N, L, T, K が与えられる。
    • N は機械のIDの種類数であり、N = 10 を満たす。
    • L は機械のLevelの種類数であり、L = 4 を満たす。
    • T は総ターン数であり、T = 500 を満たす。
    • K は計画開始時点のりんごの数であり、K = 1 を満たす。
  • 2行目には、Level 0 の機械の生産能力を表す N 個の整数 A_0, A_1, \dots, A_{N-1} が空白区切りで与えられる。
    • A_j は機械 j^0 の生産能力であり、1 \leq A_j \leq 100 を満たす。
    • A は昇順にソートされている（A_0 \leq A_1 \leq \cdots \leq A_{N-1}）。
  • 続く L 行には、それぞれ N 個の整数 C_{i,j} が空白区切りで与えられる。
    • C_{i,j} は機械 j^i の初期コストであり、1 \leq C_{i,j} \leq 1.25 \times 10^{12} を満たす。

出力

ちょうど T 行出力せよ。 各行には、t ターン目（0 \leq t < T）に行う行動を、0 ターン目から順に以下の形式で出力すること。

  • 機械 j^i を強化する場合
i j
  • 何もしない場合
-1

解答プログラムは、# から始まるコメント行を出力に含めても良い。

例を見る

入力生成方法

L 以上 U 以下の実数値を一様ランダムに生成する関数を \mathrm{rand\_double}(L,U) で表す。

A_j の生成

  • j=0 のとき：A_0=1
  • j \neq 0 のとき：A_j=\mathrm{round}(10^{\mathrm{rand\_double}(0,2)})
  • 生成後、A 配列を昇順にソートする

C_{i,j} の生成

  • i=0 かつ j=0 のとき：C_{0,0}=1
  • それ以外のとき：C_{i,j}=\mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)})

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

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

Story

APPLE ARTIS Corporation (commonly known as AA Corporation) is a company engaged in the mass production of apples. Recently, after many years of research, they have successfully developed an innovative machine capable of generating apples from nothing.

However, to begin full-scale mass production of apples using this machine, it is necessary to mass-produce the machines themselves. To achieve this, AA Corporation has established a hierarchical system in which machines are created to produce apple-generating machines, and machines are created to produce those machine-producing machines, and so on.

As an engineer at AA Corporation, you have been tasked with developing a production planning algorithm that utilizes this hierarchy of machines to produce as many apples as possible.

Problem Statement

There are N \times L types of machines, composed of N types of IDs and L types of Levels. A machine with Level i and ID j is referred to as machine j^i (0 \leq i < L,\ 0 \leq j < N).

The production capacity of machine j^0 is A_j. The initial cost of machine j^i is C_{i,j}.

Your objective is to maximize the total number of apples at the end of T turns, following the procedure of the production plan below.

Procedure of the Production Plan

Let B_{i,j} be the number of machines j^i, and initially all B_{i,j} are set to 1. Also, let P_{i,j} be the power of machine j^i, and initially all P_{i,j} are set to 0.

The initial number of apples at the start of the plan is K. Each turn proceeds according to the following steps:

  1. You choose one of the following two actions:
    • Strengthen machine j^i: Consume C_{i,j} \times (P_{i,j} + 1) apples to increase P_{i,j} by 1. However, you cannot strengthen if it would result in a negative number of apples.
    • Do nothing.
  2. For all machines j^i, perform the following in the order of Level 0, 1, 2, 3:
    • For Level 0 machines (i = 0):
      • Increase the number of apples by A_j \times B_{i,j} \times P_{i,j}.
    • For machines of Level 1 or higher (i \geq 1):
      • Increase B_{i-1,j} by B_{i,j} \times P_{i,j}.

Choose your actions wisely to maximize the number of apples at the end of T turns.

Scoring

Let S be the number of apples at the end of T turns. Your score is calculated as \mathrm{round}(10^5 \times \log_2 S). The higher the score, the better.

The following cases will result in a WA:

  • Performing a strengthening action that results in the number of apples becoming less than 0
  • Specifying a non-existent machine Level or ID
  • Taking fewer than T actions

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, 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 K
A_0 A_1 \cdots A_{N-1}
C_{0,0} C_{0,1} \cdots C_{0,N-1}
C_{1,0} C_{1,1} \cdots C_{1,N-1}
\vdots
C_{L-1,0} C_{L-1,1} \cdots C_{L-1,N-1}
  • The first line contains four integers N, L, T, K:
    • N is the number of machine IDs, and N = 10.
    • L is the number of machine Levels, and L = 4.
    • T is the total number of turns, and T = 500.
    • K is the number of apples at the start of the plan, and K = 1.
  • The second line contains N space-separated integers A_0, A_1, \dots, A_{N-1} representing the production capacities of Level 0 machines:
    • A_j is the production capacity of machine j^0, satisfying 1 \leq A_j \leq 100.
    • A is sorted in ascending order (A_0 \leq A_1 \leq \cdots \leq A_{N-1}).
  • The following L lines each contain N space-separated integers C_{i,j}:
    • C_{i,j} is the initial cost of machine j^i, satisfying 1 \leq C_{i,j} \leq 1.25 \times 10^{12}.

Output

Output exactly T lines. Each line should describe the action taken on turn t (0 \leq t < T), in order from turn 0, using the following format:

  • To strengthen machine j^i:
i j
  • To do nothing:
-1

Your program may include comment lines in the output that start with #.

Show example

Input Generation

The function \mathrm{rand\_double}(L, U) represents generating a real number uniformly at random between L and U.

Generation of A_j

  • When j = 0: set A_0 = 1
  • When j \neq 0: set A_j = \mathrm{round}(10^{\mathrm{rand\_double}(0,2)})
  • After generating all values, sort the array A in ascending order

Generation of C_{i,j}

  • When i = 0 and j = 0: set C_{0,0} = 1
  • Otherwise: set C_{i,j} = \mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)})

Tools (Input generator and visualizer)

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