經由大老闆們的資金援助之後(詳見prob #18),原本貧窮的村落經濟發展迅速,也獲得了至高無上的村莊稱號「金魂」(音:kintama),村莊內原有的鐵路系統也受到了改善,增加為兩個車站,以減少無法排列出工人們所希望車廂排列方式的情況。現有的兩個火車站也分別獲得命名,左方的車站名為「佐介」,右方的車站名為「佑助」(方向為由上往下看)。現在車站及鐵路的樣子如下圖:
車廂的以$1$到$N$來編號,一開始所有的車廂都在A方向,以$1$到$N$的順序排好($1\leq N\leq 5000$),編號越小的在越前面(靠近中間車站(station)的方向)。
現在需要把這些車廂往B方向移動,但唯一的運送方法只能藉由中間的兩個車站來運輸,兩個車站都類似一個堆疊結構,先進入車站的車廂必須等後進入的車廂都離開車站後才能離開車站。車廂都是可以獨立移動的,一旦一個車廂往車站移動後就不能返回A方向;往B方向移動之後也不能再回到車站。車站的空間很大,可以容納所有車廂。
不過車廂進入車站後,可以在兩個車站間透過中間的鐵路來移動,前提是他必須是當前在車站中最後進入的車廂。
現在李老闆找上了你來寫程式使得鐵路系統能夠正常運作,為了對社會作出貢獻的你決定用你所學的知識幫忙。
工人們希望車廂能夠以特定的方式排列在B方向上,以方便作業。你的任務是寫一個程式,操控這個鐵路系統使得全部的車廂以一特定的順序排列在B方向的鐵軌上。
請在程式一開始加上 #include "lib0022.h"
,可參考底下的範例程式碼。
你所上傳的程式碼中必須包含下列的函式:
void solve(int N,int order[]);
所有的車廂都在A方向已經以$1$到$N$的順序排好了,在每筆測試資料中,主程式中會呼叫一次上述函式。在你的solve函式中,需要呼下下列四個函數來對車廂進行操作,使得車廂能夠在B方向以$order[0],order[1]\cdots order[N-1]$的方式排列($order[N-1]$車廂在最右邊,靠近車站的方向):
void push_train();
push_train:讓A方向最靠近車站1的車廂進入車站1,如果A方向已經沒有任何車廂,呼叫之後將會獲得WA。
void move_station_1_to_2();
move_station_1_to_2:讓車站1最後進入的車廂移動到車站2,如果車站1沒有任何車廂,呼叫之後將會獲得WA。
void move_station_2_to_1();
move_station_2_to_1:讓車站2最後進入的車廂移動到車站1,如果車站2沒有任何車廂,呼叫之後將會獲得WA。
void pop_train();
pop_train:讓車站2最後進入的車廂往B方向移動,如果車站2沒有任何車廂,呼叫之後將會獲得WA。
讓所有車箱移動到B方向之後,並且排列成要求的方式後,就不需要再做任何動作,讓solve函式自行結束。如果排列結果錯誤的話也會獲得WA。
如果題目給定的排列方式無法達成的話,請在solve函式呼叫下列函式:
void no_solution();
請不要在solve函式裡面使用任何I/O函式,這可能將會使你獲得WA。
你可以在你的程式碼中宣告其他函式或變數來使用。
嘗試更動order陣列內的值也可能使你獲得WA。
一個不會AC的程式碼範例:
#include "lib0022.h"
int Gintama = 197;
void solve( int N, int order[] ){
for ( int i = 0; i < N; i++ ){
push_train();
move_station_1_to_2();
pop_train();
}
}
這是 lib0022.h
的內容:
void solve(int N,int order[]);
void push_train();
void move_station_1_to_2();
void move_station_2_to_1();
void pop_train();
void no_solution();
NEOJ Problem 23
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9 | 100 |