問題文

うなぎはクリスマスにサンタうさぎから数列 S=\{S_1,S_2,...,S_N\} をもらいました。

うなぎは数列に含まれる数の総和を求めてみることにしました。

数列 S は、以下のような疑似コードで生成されるものです。

input N
input X,T,A,B,C
for i = 1 ... N:
  S_i = X
  for j = 1 ... T:
    X = (A*X + B) mod C

入力例 1

5
5 2 3 2 1000

出力例 1

1281

数列は \{5,53,485,373,365\} となり、総和は 1281 となる。

入力例 2

1000000
868183950 1000000000 209366437 803988878 999999937

出力例 2

499932726887669

問題文

クリスマスの季節になった。うさぎは、クリスマスパーティをするためにクリスマスツリーを作っている。しかし、うさぎは不器用なのでまったくツリーが作成できていない。さらに悪い事に、ツリーの部品となる枝を何本か折ってしまった。もうすぐパーティが始まるため急いでクリスマスツリーを作らなければならない。

うさぎの作ろうとしているクリスマスツリーは N 頂点 N-1 辺からなる無向連結グラフである。 頂点にはそれぞれ 1 から N までの整数の番号が付いている。基本的にクリスマスツリーには任意の頂点対 (u, v) からなる辺を使って良い。 しかし、うさぎが M 本の辺を折ってしまったため、この折れた M 本の辺をクリスマスツリーに使うことはできない。

うさぎの代わりにクリスマスツリーを作ってあげて欲しい。

入力例 1

5 1
1 5

出力例 1

Yes
1 2
1 3
1 4
2 5

入力例 2

4 3
1 2
1 3
2 3

出力例 2

Yes
1 4
2 4
3 4

入力例 3

5 8
3 5
3 4
2 4
5 1
2 3
5 4
4 1
1 3

出力例 3

No

問題文

うさぎは H 行 W 列のマス目を何色かの色で塗り分けました。i (1≦i≦H) 行目 j (1≦j≦W) 列目のマスをマス (i,j) と呼ぶことにします。

うなぎはこのマス目に点対称な長方形がいくつ含まれているかが気になっています。

しかし、うさぎはマス目を見せてくれません。

うなぎは代わりに、以下のような質問をすることで点対称な長方形の個数を調べようとしています。

• 「マス (a,b) とマス (c,d) が同じ色かつ、マス (a,d) とマス (c,b) が同じ色」は正しいですか？

ただし、うさぎは気が短いので 4,500 回までしか質問に答えてくれません。

問題文

(参考: https://twitter.com/kyuridenamida/status/678495822946811904)

N 要素の整数列 A と、N 文字の英小文字からなる文字列 C を使って以下のように N+1 個の文字列 S_0, S_1, ..., S_N を生成する。

• まず S_0 を空文字列とする。
• i = 1, 2, ..., N について、文字列 S_i は文字列 S_{A_i} の末尾に C の i 番目の文字を付け加えたものである。ただし、任意の i について A_i < i が成り立つ。

このようにして作られた文字列のうち S_1, S_2, ..., S_N の N 個についてその周期を求めよ。

ただし文字列 T の周期とは、T がある文字列 X を無限回繰り返してできる文字列の接頭辞になっているような X のうち最も短いものの長さである。たとえば abcabca の周期は 3 であり、abcabd の周期は 6 である。

入力例 1

8
0 1 2 3 4 5 6 5
abcabcad

出力例 1

1
2
3
3
3
3
3
6

この例において各 S_i とその周期は次のようになる。

• S_1 は a となり、その周期は 1 である。
• S_2 は ab となり、その周期は 2 である。
• S_3 は abc となり、その周期は 3 である。
• S_4 は abca となり、その周期は 3 である。
• S_5 は abcab となり、その周期は 3 である。
• S_6 は abcabc となり、その周期は 3 である。
• S_7 は abcabca となり、その周期は 3 である。
• S_8 は abcabd となり、その周期は 6 である。

入力例 2

11
0 0 1 2 3 1 2 5 4 3 6
xmascontest

出力例 2

1
1
2
2
3
2
2
4
3
3
3

ストーリー

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

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

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

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

くろうさ「特殊な形の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 版が、このページの下部で利用可能である。

出力

出力は標準出力に行うこと(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のページを参考に作られました。

プログラム

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

入力

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, 2, ..., N) の順列 a_i と Q 個のクエリが与えられる。i 番目のクエリの内容は、x_i が与えられるので数列の x_i 番目と x_i+1 番目の要素の値を入れ替える、というクエリである。

クエリで数列が変更されるたびに、それが良い数列となっているか判定せよ。ただし良い数列は以下のように定義される数列である。

3 つのスタックを考える。それぞれを stack1、stack2、stack3 と呼ぶことにする。最初に、stack1 に a_1, a_2, ..., a_n をこの順に push する。その後、

• stack1 から pop し、pop した整数を x とする。x を stack2 に push する。
• stack2 から pop し、pop した整数を x とする。x を stack3 に push する。

という 2 種類の動作を好きなように行い、stack3 の要素を先頭から見た時 1, 2, ..., N となるように出来るとき、a_i は良い数列である。

ただし、push とはスタックの末尾に要素を追加する動作、pop はスタックの末尾から要素を取り出す動作のことを指す。

入力例 1

3
1 3 2
6
2
2
1
2
1
2

出力例 1

Yes
No
Yes
Yes
Yes
Yes

問題文

うなぎはクリスマスにサンタうさぎから数列 A=\{A_1,A_2,...,A_N\} をもらいました。

うなぎは数列 A からいくつか（0 個でもよい）の要素を消して、「良い数列」を作ることにしました。数列 x が良い数列であるとは、以下のような性質を満たすことを指します。

• すべての i (2 ≦ i ≦ |x|-1) について、x_i は x_{i-1}, x_i, x_{i+1} のうちの中央値でない。

例えば x=\{2,1,3,2\} や x=\{2,1,2\} は条件を満たしますが、x=\{1,2,3\} や x=\{1,1,3,2\} は条件を満たしません。 また、長さが 3 未満の数列も条件を満たします。

数列 x のデコボコ度を隣接する数の差の和とします。デコボコ度を数式で表すと、Σ_{1 ≦ i ≦ |x|-1} |x_i - x_{i+1}| となります。

このとき、作ることのできる良い数列のデコボコ度の最大値を求めてください。

入力例 1

5
1 1 3 2 1

出力例 1

4

例えば、1,4 番目の要素を消すと \{1,3,1\} となり、デコボコ値は 4 となります。

入力例 2

7
2 1000000000 0 1000000000 1 1000000000 5

出力例 2

5999999991

問題文

うなぎは A 問題と G 問題を作っていましたが、入力データを作るのが退屈になってしまいました。

そこでうなぎは、どちらの問題のものとしても正しい入力データを作ることにしました。

しかしそれだけで満足しなかったうなぎは、どちらの問題でも答えが Z になるような入力データを作ることができないかと考えました。

うなぎは T 個の Z の値を思いついたので、それぞれに対し、上記のような入力データを作ることにしました。

入力例 1

2
2015
1000000000

出力例 1

5
1 2 3 4 5
No

この出力例は出力形式の確認のためのものであり、実際には間違っています。