歐達門特是一個地主,他擁有一塊256公尺 x 256公尺朝正北的正方形田地。
為了讓田地整齊一些,他把他的田地加上了網格,每一平方公尺劃一格,如此他的田地被分成了65536格。他把西北角的格子當作(0, 0),東南角的格子當成(255, 255),並且令東方為y軸正向,南方為x軸正向。
雖說這是一塊田地,但是歐達門特不喜歡在上面種菜,而喜歡在上面放石頭、拿石頭,或者把石頭從一格搬到另外一格。由於他對石頭的大小有獨特的偏好,一格田地中最多只能塞下15顆石頭。
由於石頭實在太重了,搬太久會很累,所以他委託機器製造商幫他製作一個可以自動搬石頭的機器。然而因為歐達門特不種作物的關係,他手邊的現金並不多,只夠機器製造商幫他做好一個能按照指令自動搬石頭的機器(以下稱之為「機器X」),而沒辦法委託人來幫他寫指令。
機器X使用一種獨特的程式語言「X語言」來運作。
歐達門特一開始會將機器X放在(0, 0),並且讓它朝向北方。
X語言的指令如下:
left
:令機器X往左轉90度,並且停在當前的格子。
right
:令機器X往右轉90度,並且停在當前的格子。
move
:如果機器X可以往前走(也就是沒有在田地的邊界並且朝向邊界),令它前進一格。
get
:如果機器X現在所在的格子有石頭,令它把一顆石頭拿掉。機器X可以攜帶無限的石頭,所以不必擔心超重的問題。
put
:如果機器X現在所在的格子還放得下石頭(不是15顆),令它在這格上放下一顆石頭。同上,不必擔心機器X沒有石頭可以放。
halt
:令機器X關機。
jump L
:令機器X從L這個標籤的位置開始繼續執行指令。
border L
:如果機器X不能往前走,則令它從L這個標籤的位置開始繼續執行指令。
pebble L
:如果機器X現在所在的格子有石頭,則令它從L這個標籤的位置開始繼續執行指令。
在X語言中,所謂「標籤」是一個有效的「標籤名稱」後面緊連著一個冒號(:
)自成一行。
一個有效的「標籤名稱」是一個包含大小寫英文字母、數字或底線(_
)且長度不超過128個字的字串。例如Meow
或者__J_J_J213
都是一個有效的標籤名稱。
X語言每一行最多只有一個指令或標籤(也就是可以有空白行),機器X會從寫好的X語言的第一行開始按照順序讀取並執行指令,直到因為執行halt指令而關機,或者因已經到X語言結尾而關機。
為了使X語言方便撰寫,在一行當中若加入#
號,則該行#
號之後的文字全部都會被忽略,可做為註解使用。
例如,考慮以下X語言的程式:
move #沒有效果
right
do:
pebble break #找到石頭
border break #走到底了
move
jump do
break:
它會停在有石頭的田地中x坐標為0且y坐標最小的格子上,且若x坐標為0的格子上都沒有石頭,停在(0, 255)。
注意第一行的move
指令不會有效果,因為當時機器X無法往前走。機器先往右轉(面向y軸正向)。如果有石頭或無法往前走則從break
標籤開始執行,也就是關機(因為break
標籤後面沒有指令了);否則往前走一格,再回到do
標籤重新判斷。
歐達門特希望讓機器X完成五個任務,但由於機器X每執行一個指令需要花1秒時間(包含halt
指令),他希望完成任務的時間不要太久;同時,他也希望寫出的X語言不要包含太多指令,不然會很難看懂。因此,他制定了每個任務的時間限制與指令限制。
以下是五個任務:
任務一、一開始,(0, 0)有x顆石頭且(0, 1)有y顆石頭,其餘的格子都沒有石頭。歐達門特希望如果x ≤ y時,執行完後機器X停在(0, 0),否則停在(0, 1)。
時間限制:1,000秒,指令限制:100個
任務二、與任務一相同,但是歐達門特希望執行完後,(0, 0)和(0, 1)兩格的石頭數量與一開始一樣。
時間限制:2,000秒,指令限制:200個
任務三、一開始,(0, x)有1顆石頭且(0, y)有1顆石頭($ x \neq y, x \equiv y \pmod{2} $),其餘的格子都沒有石頭。歐達門特希望執行完後,機器X能停在(0, (x + y) / 2),也就是一開始兩個石頭位置的中點。
時間限制:200,000秒,指令限制:100個
任務四、一開始,在田地中有n個不同的格子(0 ≤ n ≤ 15)各有1顆石頭,其餘的格子都沒有石頭。歐達門特希望執行完後,(0, 0)有n顆石頭,且其餘的格子都沒有石頭。
時間限制:200,000秒,指令限制:200個
任務五、一開始,田地中每一個格子都可能有任意數量的石頭。歐達門特希望執行完後,每一格的石頭數量都和一開始一樣,且機器X能停在一個格子M,使得沒有一個格子的石頭比M的石頭少。
時間限制:44,400,000秒,指令限制:444個
你的任務就是寫五個X語言程式,讓機器X分別完成歐達門特的五個任務。
本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。
請#include "lib1269.h"
之後實作下列函數。這個函數傳入一個1~5的整數代表任務編號,並且需要回傳你完成的X語言程式的字串。
char* GetCode(int);
如果你的函數名稱不對或者長得不像上面那行,你將會獲得一個CE。
你可以把五個任務的X語言程式分別存在sub_1.txt
, sub_2.txt
, ..., sub_5.txt
,並且以C++執行這個程式,該程式會幫你把你應該上傳的程式碼存在output.cpp
。
請務必使用C++11,14,17提交該程式碼。
任務一到五的分數分別是9, 12, 19, 32, 28分。
如果你的X語言程式超出了歐達門特的時間或指令限制,你會獲得一個WA。
如果你的X語言程式語法錯誤,你會獲得一個RE。
本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA。
如果你需要一個可以執行X語言的程式,請點這裡(須以C++11編譯)。使用方法如下。
請將一開始田地的石頭分佈情況放在grid_path
所代表的檔案,並把你的X語言程式放在code_path
所代表的檔案。
田地石頭分佈情況的檔案,每一行要有3個以空白分開的整數x, y, t,代表(x, y)有t顆石頭。
你可以自行設定地圖的大小gridN
、以及結束時要不要印出整個田地的樣子print_grid
。
IOI 2012 Day 1
Judge / Description by Yihda Yol
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 9 |
2 | 10~19 | 12 |
3 | 20~29 | 19 |
4 | 30~49 | 32 |
5 | 50~68 | 28 |