TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

12.5% (1/8)

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

Sample Input

本題沒有輸入。

Sample Output

本題沒有輸出。

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

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