Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
ストーリー
くろうさ「足し算は甘え」
しろうさ「あっこれって」
くろうさ「ビット演算は許してあげる」
しろうさ「えっとえっと」
くろうさ「ほんとにちょっとだけなら足し算してもいいよ」
しろうさ「何回ぐr
くろうさ「というわけでまたまたがんばってねっ」
(元ネタ: Xmas Contest 2015 Problem E: Esolang?, 元ネタの元ネタ: Xmas Contest 2014 Problem A: A+B Problem)
入力
この問題では入力は与えられない。
出力
0 以上 255 以下の整数をインクリメントする (値を 1 増やす、ただし 255 は 0 にする) プログラムを以下の仕様に従って作成し提出せよ。ジャッジ方法の項で詳細を記述するが、プログラム中で加算操作を行った回数が少ないほど高得点が得られる。
プログラムの動作
プログラム中では a, b, c, ..., z の 26 個の変数を扱うことができる。各変数は 0 以上 255 以下の整数を保持することができる。プログラム開始時に a の値がある整数値に設定されており、そのほかの 25 個の変数はすべて 0 に設定されている。
提出するプログラムは各行に「操作」が 1 つずつ記述される形式をとる。すべての操作は Z = X op Y
という書式に従う。ここで、X
, Y
, Z
は変数名を表す英小文字であり、op
は演算を表す文字列 (後述) でなければならない。各操作は X
と Y
の示す変数の保持する値に対し op
で示される演算を行った結果を Z
に格納するという動作をする。
演算として使うことができるのは 16 種のビットごとの論理演算と、加算の計 17 種類である:
- ビットごとの論理演算を行うとき、
op
は0
と1
のみからなる 4 文字の文字列である。この文字列は、各ビットに対して行われる論理演算の真理値表を表しており、入力が (0, 0), (0, 1), (1, 0), (1, 1) の場合に対応する出力を順に並べたものである。- たとえば、ビットごとの論理和 (OR) 演算を表す文字列は
0111
であり、論理包含 (→) を表す文字列は1101
となる。
- たとえば、ビットごとの論理和 (OR) 演算を表す文字列は
- 加算を行うとき、
op
は+
である。加算の結果が 256 以上になる場合、その和を 256 で割った余りが変数Z
に格納される。
以下に示すのはプログラムの記述例である (内容には特に意味がない)。
b = a + a c = b 0101 a a = a 1101 b
ジャッジ方法
ジャッジは以下のように行われます。
- 提出されたプログラムの形式が正しくない場合 (各行に「操作」を表す正しい書式の文字列が 1 つずつ書かれていない場合)、ジャッジ結果は
WA
となる。 - 提出されたプログラムが 1\,000 個以上の「操作」を含む場合、ジャッジ結果は
WA
となる。 - 0 以上 255 以下のすべての整数 A に対し、プログラム実行開始時の a の値を A に設定したうえで、提出されたプログラムを実行する。プログラムの実行が終了した時点で、変数 a の値が A+1 (ただし A=255 の場合は 0) になっていないような A が存在すれば、ジャッジ結果は
WA
となる。
以上のプロセスで WA
と判定されなかったプログラムは AC
と判定されますが、その得点は以下のように決まります。
- プログラム中に存在する加算操作の回数 を P とする。また、上述の条件を満たしたプログラムのうち、P としてありうる値の最小値 (加算操作の最小の必要回数) を P_0 とする。このとき、得点は
- P = P_0 ならば 100 点
- P_0 < P \leq 2P_0 ならば 30 点
- 2P_0 < P ならば 0 点