E - Esolang? Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

ストーリー

くろうさ「通常言語を使用するのは甘え」

しろうさ「……嫌な予感」

くろうさ「足し算と引き算は許してあげる」

しろうさ「えっとえっと」

くろうさ「特殊な形のwhile文は使ってもいいよ。あ、他にも色々制限しちゃう」

しろうさ「条件分ｋ

くろうさ「というわけで今回もがんばってねっ」

(元ネタ:Xmas Contest 2014 Problem A: A+B Problem)

問題文

N 個のうさぎ小屋があり、M 羽のうさぎさんがいる。 各うさぎ小屋には 1 ～ N の番号が振られており、各うさぎさんには 1 ～ M の番号が振られている。

あなたの仕事は以下のようなクエリが Q 個与えられるので、順に処理することである。

  • タイプ 1 : 番号 Y のうさぎさんがうさぎ小屋 X の中に入る。
  • タイプ 2 : うさぎ小屋 X に入っているうさぎさんのうち、最初に入ったうさぎさんを 1 番目として、Y 番目にうさぎ小屋に入ったうさぎさんの番号を答える。

あなたはこのクエリの処理を次の言語概要で述べる言語で実装しなければならず、「初期化処理」「タイプ 1 のクエリの処理」「タイプ 2 のクエリの処理」の 3 種類のプログラムを作成し、そのソースコードを提出しなければならない。フォーマットは出力の項を参照すること。

ただし、ただ実装するだけでなく、言語概要で述べられている BNF 内の非終端記号 expr の評価回数が与えられる定数 L 以下でなくてはならない。

言語概要

実装に使用する言語には、以下のような特徴がある。

  • メモリは基本的に、それぞれの要素に [0,9999] の範囲の整数のみが格納できる長さ 10000 の配列 a のみである。a[i] で i 番目(0-indexed)の要素にアクセスできる。タイプ 2 のクエリでは、答えを格納する変数 A が利用できる。
  • 使用できる定数も [0,9999] の範囲の整数である。
  • 演算の途中過程で現れる数値も [0,9999] の範囲に収まっていなければならず、収まっていない場合エラーとなる。足し算と引き算は全て左結合で行われる。
  • 用いることができる主な機能は、「代入」「加算・減算」「while (式 < 式) {実行文}」のみである。while(式<式){実行文}は、"式<式" が真の間のみ実行文を実行する繰り返し文である。
  • 入力は定数を通して受け取る。
  • タイプ 2 に対する回答は、変数 A への代入という形で行う。 A へのアクセスはクエリ毎に 1 度しかできず、2 度以上アクセスした場合エラーとなる。
  • 各セクション（初期化、タイプ 1、タイプ 2 ）によって、参照・代入できる定数・変数が異なる。そのセクションで使えない定数・変数に対する操作をしようとするとエラーとなる。

各セクションで使える定数一覧は次の通りである。

  • 初期化： N,M
  • タイプ1： N,M,X,Y
  • タイプ2： N,M,X,Y

各セクションで使える変数一覧は次の通りである。

  • 初期化： a
  • タイプ1： a
  • タイプ2： a,A

言語の BNF は以下の通りである。

<program> ::= <command> | <command> "\n" <program>
<command> ::= <assign> | <repetition>
<assign> ::= <var> "=" <expr>
<expr> ::= <param> | <param> "+" <expr> | <param> "-" <expr>
<repetition> ::= "while(" <expr> "<" <expr> "){\n" <program> "\n}"
<param> ::= "(" <expr> ")" | <var> | <const>
<var> ::= "a[" <expr> "]" | "A"
<const> ::= <number> | "N" | "M" | "X" | "Y"
<number> ::= <nonzero-digit> | <number> <digit>
<digit> ::= "0" | <digit>
<nonzero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

採点方法

採点は採点プログラムを通して行う。

採点プログラムは以下のように動作する。文法が与えられた BNF に沿っていない場合や、実行時にエラーを起こした場合は不正解として扱われる。また、指定された L よりも多く expr 非終端記号を呼び出した場合は、「QLE」と表示され、不正解として扱われる。

  1. 定数 N,M を入力で与えられたものに設定する。
  2. 配列変数 a の全ての要素を 0 で初期化する。
  3. 次に、「初期化処理」に記述されているコードを一度だけ実行する。
  4. その後、クエリが与えられる。
    • タイプ 1 のクエリが来たときには、定数 X,Y をクエリで与えられたものに設定し、「タイプ 1 のクエリの処理」に記述されているコードを実行する。
    • タイプ 2 のクエリが来たときには、定数 X,Y をクエリで与えられたものに設定し、変数 A を 0 に初期化し、「タイプ 2 のクエリの処理」に記述されているコードを実行する。コード実行後、変数 A に書き込まれている値を出力する。

ただし、採点プログラム(インタプリタ)は、構文解析を行う前に以下のような前処理を行う。

  • 空白・タブ・リターンコード・空行は予め削除する。そのような仕様なので、例えば "A = 1 0" という記述は内部的に "A=10" として扱われることに注意。
  • 各行の最初に現れる ";" 以降の文字列はコメントとして判断し、構文解析を行う前に削除する。

採点プログラムのインタプリタの javascript 版が、このページの下部で利用可能である。

入力

入力は以下の形式で記述されているが、採点プログラムがあなたの記述したプログラムに定数として与えるので、あなたは意識する必要がない。 インタプリタを利用したテストの際は参考にすること。

N M Q L
T_1 X_1 Y_1
T_2 X_2 Y_2
:
T_Q X_Q Y_Q
  • 1 行目には、うさぎ小屋の数 N、うさぎさんの数 M、クエリの数 Q、非終端記号exprの呼び出し上限回数 Lが書かれている。N,M,Q,L の制約は部分点の項を参照せよ。
  • 2 行目からの Q 行のうち i (1≦i≦Q) 行目には、i 番目のクエリの情報が与えられる。これは i 番目に、タイプ T_i(1≦T_i≦2) のクエリを (X,Y)=(X_i,Y_i) として呼び出すことを意味する。
  • タイプ 1 のクエリにおいて、一羽のうさぎさんが複数のうさぎ小屋に入るようなクエリは与えられない。
  • タイプ 2 のクエリにおいて、答えが存在しないようなクエリは与えられない。

部分点

この問題には部分点が設定されている。

  • N=400,1≦M≦500,1≦Q≦1000,L=4000000 という制約を満たすデータセットに正解した場合は、 30 点が与えられる。
  • N=400,1≦M≦4000,1≦Q≦8000,L=1500000 という制約を満たすデータセットに正解した場合は、上記とは別に 70 点が与えられる。

出力

出力は標準出力に行うこと(catを用いることを推奨する)。

あなたは指定された言語で書かれたプログラムソース自体を出力しなければならない。また、

初期化処理
----
タイプ 1 のクエリの処理
----
タイプ 2 のクエリの処理

のように"----"で区切られた形式でならなければならない。各処理は空であってはならず、必ず 1 つ以上の命令を含まなければならない。

コメントも含めマルチバイト文字を含んでいる場合、javascript 版で動作したとしても、ジャッジ側で正しく動作しない可能性があるので含まないこと。

末尾の改行はあっても無くても採点プログラムの動作に影響はない。

あまりにも長すぎるコード(数MB規模)は正しく採点されない可能性が高い。その場合 IE(内部エラー) となる。また、プログラムの実行時間に、採点プログラムの動作時間は含まれない。

入力例1

10 5 8 54
1 1 5
2 1 1
1 10 4
1 10 2
1 10 3
2 10 1
2 10 2
2 10 3

出力例1

a[0] = 1 ; This is a comment

a[1] = 5 ; Don't include any multibyte character in your program
a[2] = 4
a[3] = 2
a[4] = 3
----
a[2015] = X ; no meaning
a[2016] = Y ; no meaning too
----
A = a[a[0]];
a[0] = a[0] + 1
  • 1 番目のクエリでは、うさぎ小屋 1 に番号 5 のうさぎさんが入る。
  • 2 番目のクエリでは、うさぎ小屋 1 に 1 番目に入ったうさぎさんの番号を求められている。 5 が答えである。
  • 3 番目のクエリでは、うさぎ小屋 10 に番号 4 のうさぎさんが入る。
  • 4 番目のクエリでは、うさぎ小屋 10 に番号 2 のうさぎさんが入る。
  • 5 番目のクエリでは、うさぎ小屋 10 に番号 3 のうさぎさんが入る。
  • 6 番目のクエリでは、うさぎ小屋 10 に 1 番目に入ったうさぎさんの番号を求められている。4 が答えである。
  • 7 番目のクエリでは、うさぎ小屋 10 に 2 番目に入ったうさぎさんの番号を求められている。2 が答えである。
  • 8 番目のクエリでは、うさぎ小屋 10 に 3 番目に入ったうさぎさんの番号を求められている。3 が答えである。

出力例1のプログラムは入力例1の答えを埋め込んでおり、expr 非終端記号の評価回数はちょうど 54 回なので、このテストケースに対して正答を得ることができる。 ただし、当然ながらこのプログラムを提出しても点数を得ることはできない。

入力はあなたの出力したプログラムに対して採点プログラムを通して与えられるものであり、標準入力には何も与えられないことに注意せよ。すなわち、埋め込みソースを自動生成するような解き方は困難である。

また、この入出力例は L=54 のケースであり、どの部分点の制約も満たさないため、採点データに含まれていない。

言語のインタプリタ

  • このインタプリタのソースコードを利用して問題を解く道具を作成しても構いません。
  • 何か変な挙動を見つけたら clar お願いします。ただし、「入力」の部分についてはフォーマットチェックしていません。
  • 去年のhosさんのコンテスト(Xmas Contest 2014)のA+B Problemのページを参考に作られました。

プログラム

入力

結果