gardendecoration
Day1 Tasks
Japanese (JPN)

European Girls'
Olympiad in Informatics
21 – 27 July 2024
The Netherlands

D. 庭の飾り付け (Garden Decorations)
問題名

庭の飾りつけ (Garden Decorations)

実⾏時間制限

7秒

メモリ制限

1 GB

Detje は，登校と下校の際に毎⽇，0 から N − 1 までの番号が付けられた N 軒の家が⼀列に並んでいる街道を歩く．現在，家 i には住⺠ i が住んでいる．さて，景観の変化のため，⼈々は互いに転居することを決めた．具体的には，住⺠ ai (現在家 ai に住んでいる住⺠) が家 i に転居することを決めた．
ここで，各家の庭には⿃の像が設置されている．⿃の像には 2 つの状態があり，これらは (⿃が⾶んでいるように) ⽻が 開いている状態 と，(⿃が地⾯に⽴っているように) ⽻が 閉じている状態 である．各住⺠は，⿃の像がどう⾒えるべきかについて極めて強い好みを持っている．住⺠ i が好きな⿃の状態は，現時点で家 i の庭にある⿃の状態である．住⺠たちは，全住⺠における転居後の家の庭にある⿃の状態が好きな状態になるまで，転居を断り続ける．そこで Detje は，⿃の像の状態を変更することで，転居を⼿伝うことにした．
転居を⼿伝うため，彼⼥は次のことを⾏う．彼⼥が街道を歩くとき (登校および下校の際)，彼⼥は通過した⿃の像を順番に観察し，いくつかの⿃の像の状態を (⽻を開いたり閉じたりすることによって) 随時変更する．しかし，彼⼥は学校と⾃宅で忙しい⽇々を過ごしているため，彼⼥は前回歩いたときの⿃の状態を覚えていない．⼀⽅，幸運なことに，彼⼥は整数 a0 , a1 , ..., aN −1 を紙に書いており，どの住⺠がどの家に転居するのかを知っている．
各住⺠の好みに合うような像の変更を⾏うために，どの像の状態を操作するかを伝える戦略を実装してDetje を⼿伝え．なお，彼⼥は街道を最⼤ 60 回歩くことができるが，⾼い得点を得るためには，より少ない回数にする必要がある．

gardendecoration (1 of 7)

実装
この問題は複数回実⾏の問題である．すなわち，あなたのプログラムは複数回実⾏される．
各実⾏では，あなたは最初に 2 つの整数 w と N を⼊⼒しなければならない．ここで，w は何回⽬の歩⾏かを指す整数であり，N は家の数である．初回の実⾏では w = 0 であり，2 回⽬の実⾏では w = 1であり，それ以降も同様である (詳細は後述)．
⼊⼒の 2 ⾏⽬には，N 個の整数 a0 , a1 , ..., aN −1 が書かれている．これは，現在家 ai に住んでいる住⺠が家 i に転居することを意味する．ここで ai は順列であり，すなわち 0 から N − 1 までの整数が 1 回ずつ出現する．なお，各住⺠は転居しないという選択をすることも可能であり，すなわち ai = i となることもある．
各住⺠は⼀度しか転居を⾏わない．すなわち，1 つのテストケースにおいて，N および ai の値はすべての実⾏で同じである．

初回の実⾏
初回の実⾏では w = 0 となる．この実⾏では，あなたのプログラムは単に， Detje が歩くべき回数を表
す整数 W (0 ≤ W ≤ 60) を出⼒しなければならない．そして出⼒の後，あなたのプログラムは実⾏を終了しなければならない．その後，あなたのプログラムは追加で W 回実⾏される．

それ以降の実⾏
次の実⾏では w = 1，その次の実⾏では w = 2 となる．以降も同様であり，最後の実⾏では w = W となる．
あなたのプログラムが整数 w, N , a0 , a1 , ..., aN −1 を⼊⼒した後，Detje は街道の歩⾏を始める．
もし w が奇数である場合，Detje は⾃宅を出発し，学校に向けて歩く．彼⼥は家 0, 1, ..., N − 1の順に通過する．
まず，あなたのプログラムは b0 を⼊⼒しなければならない．ここで，b0 は家 0 の庭の像の状態を表す整数であり，0 (閉じている状態) または 1 (開いている状態) である．そして整数 b0 を読み込んだ後，あなたは変更後の b0 の値を出⼒することで，像の状態を変更するかどうかを決めなければならない．
次に，あなたのプログラムは b1 を⼊⼒しなければならない．ここで，b1 は家 1 の庭の像の状態を表す整数である．その後，変更後の b1 の値を出⼒しなければならない．同様の⼿順は家2, 3, ..., N − 1 についても続く．Detje が最後の家を通過した後 (すなわち，bN −1 に関する⼊⼒と出⼒を⾏った後)，あなたのプログラムは終了しなければならない．

なお，あなたのプログラムは変更後の bi の値を出⼒するまで，bi+1 の値を⼊⼒することができな
い．

gardendecoration (2 of 7)

も し w が 偶 数 で あ る 場 合 ， Detje は 学 校 を 出 発 し ， ⾃ 宅 に 向 け て 歩 く ． 彼 ⼥ は 家

N − 1, N − 2, ..., 0 の順に通過する．すなわち，あなたのプログラムは bN −1 , bN −2 , ..., b0 の順に⼊出⼒を⾏う．

w = 1 を満たす実⾏では，⼊⼒される値 b0 , b1 , ..., bN −1 は「⿃の像の最初の状態」である (各住⺠の好きな状態でもある)．w > 1 を満たす実⾏では，⼊⼒される値 b0 , b1 , ..., bN −1 は「前回の実⾏で出⼒された値」である．
最終的に，プログラムの最後の実⾏が終わった時点で，すべての i について bi の値が bai の初期値と等しくなければならない．さもなくば，Wrong Answer と判定される．

詳細もし W + 1 回の実⾏における実⾏時間の 総和 が実⾏時間制限を超過した場合，Time Limit Exceededと判定される．
各⾏の出⼒の最後には，必ず標準出⼒を ﬂush せよ．さもなくば，Time Limit Exceeded と判定される．Python の場合，input() によって⾃動的に ﬂush される．C++ の場合，cout << endl; によって，改⾏されるとともに⾃動的に ﬂush される．もし printf を使⽤する場合，fflush(stdout) を⽤いよ．

制約‧採点形式
2 ≤ N ≤ 500.
W ≤ 60 回の歩⾏しか⾏うことができない．
あなたの解答は各⼩課題ごとに評価され，⼩課題にはそれぞれ配点が割り当てられている．各⼩課題は複数のテストケースからなる．各⼩課題について得点を得るためには，その⼩課題に含まれるすべてのテストケースに正解する必要がある．
⼩課題

配点

制約

110N =2224N ≤ 15

39ai = N − 1 − i413ai = (i + 1) mod N

513ai = (i − 1) mod N

631

追加の制約はない

正解した各⼩課題について，次式に基づく得点が与えられる．

gardendecoration (3 of 7)

score = Sg ⋅ (1 − 12 log10 (max(Wg , 3)/3)) ,ここで，Sg は各⼩課題の配点であり，Wg はこの⼩課題を満たすテストケースで指定された W の最⼤値を表す．各⼩課題におけるあなたの得点は，最も近い整数に四捨五⼊される．
以下のグラフは，すべての⼩課題について同じ整数 W を指定した場合における，整数 W と得点の関係を⽰している．特に，この問題で 100 点を得るためには，すべてのテストケースについて W ≤ 3 で解く必要がある．

テストのためのツール
あなたが解法をテストすることを容易にするため，簡単なツールがダウンロードできるようになっている．Kattis 問題ページの下部の attachments の項を⾒よ．ここで，本ツールを必ずしも使う必要はな
い．なお，Kattis で使⽤される実際の採点プログラムは，本ツールとは異なる．
本ツールを使うには，まず sample1.in のような⼊⼒ファイルを作成しなければならない．この⼊⼒
ファイルでは，最初の⾏に整数 N ，次の⾏に順列を表す N 個の整数，その次の⾏に⿃の像の初期状態 (0 または 1) を N ビット指定しなければならない．具体例を以下に⽰す:
61 2 0 4 3 5
1 1 0 0 1 0
Python の場合，例えば solution.py の場合，(通常は pypy3 solution.py とすれば実⾏されるが)以下を実⾏しなければならない．
python3 testing_tool.py pypy3 solution.py < sample1.in
C++ の場合，まずコンパイルを⾏い (例: g++ -g -O2 -std=gnu++20 -static solution.cpp -osolution.out)，その後以下を実⾏しなければならない．

gardendecoration (4 of 7)

python3 testing_tool.py ./solution.out < sample1.in

例
サンプルテストケースでは，家の住⺠に関する順列として以下が⼊⼒される．

サンプルプログラムの初回の実⾏ (w = 0) では，W = 2 が出⼒される．これは，Detje が 2 回の歩⾏を⾏う (すなわち，プログラムは追加で 2 回実⾏される) ことを意味する．最初の歩⾏の前の時点において，庭の⿃の状態は下図のようになっている．

その後，プログラムは w = 1 で実⾏される (Detje の 1 回⽬の歩⾏を意味する)．彼⼥は⿃の像を左から順に通過し，状態を随時変更する．サンプルプログラムは，家 i + 1 の⿃に関する情報を⼊⼒する前に，家 i の⿃の変更後の状態を出⼒しなければならない．
Detje が学校に到着した後の時点で，⿃の状態は下図のようになっている．

プログラムの最後の実⾏ (w = 2) では，Detje は学校から出発して家に戻る．この実⾏では，彼⼥は⿃の像を右から順に通過し，つまり逆順に処理が⾏われる！

すなわち，彼⼥は家 i − 1 の⿃の状態を⾒る前に，家 i の⿃の変更後の状態を決めなければならない．
彼⼥が最後の歩⾏を終えた後の時点で，⿃の状態は下図のようになっている．

これは正しい状態になっている．たとえば，家 3 の⿃の像 (左から 4 番⽬) は開いている状態であるが(現在 b3 = 1 である)，住⺠ 4 がこの家に転居する予定であり (a3 = 4)，この家の庭には最初の時点において，開いた状態の⿃の像がある (最初 b4 = 1 である)．

gardendecoration (5 of 7)

採点プログラムの出⼒

あなたのプログラムの出⼒

061204352採点プログラムの出⼒

あなたのプログラムの出⼒

16120435
101100011101

gardendecoration (6 of 7)

採点プログラムの出⼒

あなたのプログラムの出⼒

26120435
10101101100
1

gardendecoration (7 of 7)