e099: 皮皮搬家
標籤 :
通過比率 : 3人/5人 ( 60% ) [非即時]
評分方式:
Special

最近更新 : 2019-04-13 11:03

內容

前言

這是一題實驗性的互動題,取自 IOI 1995 P6 Wires and Swiches,基於技術上的限制,僅能使用 Python 作答。


最近皮皮搬進新公寓,屋子裡的電箱共有 n <= 90 個開關,散落各處的插座也恰巧有 n 個,不幸的是,開關上面沒有任何標籤和記號。

皮皮想請你找出各個插座對應到的電源開關(兩者的編號都是 1 ~ n),一個插座必定對應到一個開關,但是一個開關可能控制零個或多個插座。以下是你能進行的測試手段:

change(y):切換編號 y 的開關 on <=> off,一開始所有開關的狀態都是 off。

test(x):檢查編號 x 的插座是否通電,這個函式會回傳 True/False。

皮皮不希望你花太多時間,因此上面兩種測試的進行次數總和不能超過 950 次。


實作細節

你必須實作一個函式 solve(n),回傳值為長度 n 的 int 陣列 a,代表第 i + 1 個插座由第 a[i] 個開關控制。

在各測資點中,測試程式會引用若干筆測試資料來檢測你的算法是否正確,請注意,對於 change, test 的呼叫,如果參數型別並非 int 或是數值超出 1~n 的範圍將會得到 「Wrong Answer」;若是單筆測資的呼叫次數超過 950 次,測試程式將回傳 「Command Limit Exceeded」。

解答用的程式碼必須以字串方式輸出,例如以下程式碼能正確無誤的拿到 25% 的分數,其輸出即為範例輸出。

print('''
ans = [1, 1]
def foo():
    change(2)

def solve(n):
    global ans
    foo()
    if test(1): ans[0] = 2
    if test(2): ans[1] = 2
    return ans
''')

單一測資點最多有1000筆測資。

輸入說明

本題沒有輸入。

輸出說明

輸出作為解答的程式碼。

範例輸入

										
範例輸出
ans = [1, 1]
def foo():
    change(2)

def solve(n):
    global ans
    foo()
    if test(1): ans[0] = 2
    if test(2): ans[1] = 2
    return ans
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (25%): 0.5s , <1K
公開 測資點#1 (25%): 1.2s , <1K
公開 測資點#2 (25%): 0.8s , <1K
公開 測資點#3 (25%): 2.0s , <1K
提示 :

2019/04/13 修正題敘,感謝 liouzhou_101 的測試。

標籤:
出處:
[管理者:
icube (輸光光)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」