Problem : 290 - [Interactive]Cave

Problem Statistics

Solved Member: 40　　Submission: 327　　User Tried: 41

Statement:

請在程式碼加入#include "interactive/290.h"回答問題。

你在從學院到UQ 中心的漫長路程中迷路了。你意外地發現了通往學校地底秘密洞穴系統的入口。這個入口被一個有連續N個門的安全系統阻隔。這個系統有N個開關，分別連接到這 N 個不同的門。

這些門依序由0, 1, …, N - 1編號，其中最接近你的那扇門編號為0。開關的編號也是0, 1, …, N - 1，但是你並不知道哪一個開關連到哪一扇門。

開關都位於洞穴的入口處。每個開關可以被設定成上或下的位置。每一個開關只有一個位置是正確的。若一個開關被設定在正確的位置，則其連接到的門便會打開；若一個開關被設定在不正確的位置，則其連接到的門便會關閉。每一個開關的正確設定位置可能不相同，現在你並不知道開關的正確設定位置。

你想要了解這套安全系統。為了達到這個目的，你可以將開關設定成任何的位置組合，並且走入這個洞穴觀察第一個未開的門。這些門都是不透明的，當你發現第一個未開的門時，你無法看到任何後方的門。

你可以嘗試最多70,000種開關的位置組合。你的任務是決定每個開關的正確設定位置，以及每個開關連接到哪一扇門。

Task:

函式庫中將提供以下的函式

　•int Initialize()：回傳數字 n。你必須要在程式一開始呼叫這個函式。

　•int tryCombination(const int S[])：這個函式允許你測驗一個開關設定組合，並得以進入洞穴來查看第一個未打開的門。假如所有的門都被打開了，這個函式會回傳 -1。
　　　•S: 長度為N的陣列，表示每個開關的設定位置。元素 S[i] 對應到開關 i，其值為0代表開關位置向上，其值為1代表開關位置向下。
　　　•回傳值：第一個未打開的門的編號。若所有的門都打開，回傳值為 -1。
　這個函式的時間複雜度是 O(N)；也就是說，最差的情況下執行時間是和N成正比。
　這個函式最多可以被呼叫 70,000次，若超過70,000次你將會得到Wrong Answer。

　•void answer(const int S[], const int D[])：當你已經找出能打開所有門的開關位置設定和開關與洞門的連結關係時，請呼叫這個函式，接著你的程式將會被結束。
　　　•S: 長度N的陣列，代表每個開關的正確設定位置。其元素代表意義請參閱 tryCombination()中的S說明。
　　　•D: 長度N的陣列，代表每個開關連結的洞門。換句話說，元素 D[i] 代表開關 i 連結到的洞門編號。

子任務	分數	額外輸入限制
1	12	已知開關 i 連到洞門 i。你只需要決定正確的開關設定位置。
2	13	正確的開關設定位置已知是 [0, 0, 0, …, 0]。你只需決定開關與洞門的連結關係。
3	21	N ≤ 100
4	30	N ≤ 2,000
5	24	N ≤ 5,000

Input:Output:

請不要做任何輸入動作，否則你會得到WA。

輸入資料格式如下。

第一行：N，表示開關與門的數量。
第二行：S[0] S[1] … S[N - 1]，表示第i個開關開門的設定位置，只會是0或1。
第三行：D[0] D[1] … D[N - 1]，表示第i個開關對應到的門(0~n-1)。

(Sample Input可以幫助你測試程式，但這不是你應該輸入的東西)

請不要做任何輸出動作，否則你會得到WA。

Sample Input:Sample Output:

4
1 1 1 0
3 1 0 2

HINT:

Sample :

Function Call	Returns	Explanation
tryCombination([1, 0, 1, 1])	1	參閱敘述中的圖片。開關0, 2 和3 的位置向下，開關1 的位置向上。函式回傳1，代表洞門編號1是第一個沒開的門。
tryCombination([0, 1, 1, 0])	3	洞門0, 1, 2打開了，洞門3 未開。
tryCombination([1, 1, 1, 0])	-1	把開關0的位置設定向下，此時回傳-1，代表所有的門都打開了。
answer([1, 1, 1, 0], [3, 1, 0, 2])	(Programexits)	我們猜測開關正確設定位置是[1, 1, 1, 0]，而且開關0, 1, 2, 3 連結到洞門3, 1, 0, 2。

註：UQ是The University of Queensland的簡稱，2013IOI在澳洲UQ辦的喔!

Source:

IOI 2013

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	32768kb
1-1	3000ms	32768kb	12
1-2	3000ms	32768kb
1-3	3000ms	32768kb
1-4	3000ms	32768kb
1-5	3000ms	32768kb
1-6	3000ms	32768kb
1-7	3000ms	32768kb
1-8	3000ms	32768kb
1-9	3000ms	32768kb
1-10	3000ms	32768kb
1-11	3000ms	32768kb
1-12	3000ms	32768kb
1-13	3000ms	32768kb
1-14	3000ms	32768kb
2-1	3000ms	32768kb	13
2-2	3000ms	32768kb
2-3	3000ms	32768kb
2-4	3000ms	32768kb
2-5	3000ms	32768kb
2-6	3000ms	32768kb
2-7	3000ms	32768kb
2-8	3000ms	32768kb
2-9	3000ms	32768kb
3-1	1000ms	32768kb	21
3-2	1000ms	32768kb
3-3	1000ms	32768kb
3-4	1000ms	32768kb
3-5	1000ms	32768kb
3-6	1000ms	32768kb
3-7	1000ms	32768kb
3-8	1000ms	32768kb
3-9	1000ms	32768kb
4-1	1500ms	32768kb	30
4-2	1500ms	32768kb
4-3	1500ms	32768kb
4-4	1500ms	32768kb
4-5	1500ms	32768kb
4-6	1500ms	32768kb
4-7	1500ms	32768kb
4-8	1500ms	32768kb
4-9	1500ms	32768kb
5-1	3000ms	32768kb	24
5-2	3000ms	32768kb
5-3	3000ms	32768kb
5-4	3000ms	32768kb
5-5	3000ms	32768kb
5-6	3000ms	32768kb
5-7	3000ms	32768kb
5-8	3000ms	32768kb
5-9	3000ms	32768kb