TopCoder

8e7
$\huge X語言專家 $(TIOJ 1269)

User's AC Ratio

36.4% (4/11)

Submission's AC Ratio

6.6% (4/61)

Tags

Description

歐達門特是一個地主,他擁有一塊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分別完成歐達門特的五個任務。

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#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

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Hints

如果你需要一個可以執行X語言的程式,請點這裡(須以C++11編譯)。使用方法如下。
請將一開始田地的石頭分佈情況放在grid_path所代表的檔案,並把你的X語言程式放在code_path所代表的檔案。
田地石頭分佈情況的檔案,每一行要有3個以空白分開的整數x, y, t,代表(x, y)有t顆石頭。

你可以自行設定地圖的大小gridN、以及結束時要不要印出整個田地的樣子print_grid

Problem Source

IOI 2012 Day 1
Judge / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~9 9
2 10~19 12
3 20~29 19
4 30~49 32
5 50~68 28

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 2
11 1000 65536 262144 2
12 1000 65536 262144 2
13 1000 65536 262144 2
14 1000 65536 262144 2
15 1000 65536 262144 2
16 1000 65536 262144 2
17 1000 65536 262144 2
18 1000 65536 262144 2
19 1000 65536 262144 2
20 1000 65536 262144 3
21 1000 65536 262144 3
22 1000 65536 262144 3
23 1000 65536 262144 3
24 1000 65536 262144 3
25 1000 65536 262144 3
26 1000 65536 262144 3
27 1000 65536 262144 3
28 1000 65536 262144 3
29 1000 65536 262144 3
30 1000 65536 262144 4
31 1000 65536 262144 4
32 1000 65536 262144 4
33 1000 65536 262144 4
34 1000 65536 262144 4
35 1000 65536 262144 4
36 1000 65536 262144 4
37 1000 65536 262144 4
38 1000 65536 262144 4
39 1000 65536 262144 4
40 1000 65536 262144 4
41 1000 65536 262144 4
42 1000 65536 262144 4
43 1000 65536 262144 4
44 1000 65536 262144 4
45 1000 65536 262144 4
46 1000 65536 262144 4
47 1000 65536 262144 4
48 1000 65536 262144 4
49 1000 65536 262144 4
50 1000 65536 262144 5
51 1000 65536 262144 5
52 1000 65536 262144 5
53 1000 65536 262144 5
54 1000 65536 262144 5
55 1000 65536 262144 5
56 1000 65536 262144 5
57 1000 65536 262144 5
58 1000 65536 262144 5
59 1000 65536 262144 5
60 1000 65536 262144 5
61 1000 65536 262144 5
62 1000 65536 262144 5
63 1000 65536 262144 5
64 1000 65536 262144 5
65 1000 65536 262144 5
66 1000 65536 262144 5
67 1000 65536 262144 5
68 1000 65536 262144 5