Problem : 120 - [Interactive]中間數

Problem Statistics

Solved Member: 16　　Submission: 188　　User Tried: 21

Statement:

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

一個新的太空實驗室用到 N 個物件，其代號從 1 到 N ，且 N 是奇數。每一個物件都有不同且未知的能量值，這些值為自然數。每一個能量值 Yi 都滿足 1 ≤ Yi ≤ N 的條件。你必須寫一個程式，來找出能量值為中間數的物件，換句話說，找出物件X，讓能量值小於物件 X 能量值的物件數，等於能量值大於物件 X 能量值的物件數。可惜的是，只有一種設備(device)能用來比較能量值的大小：給定三個不同的物件，該設備(device)能找出能量值為中間數的物件。

Task:

使用下面函式回答問題：
1.int GetN()：一開始就呼叫，且不含任何參數；回傳N的值。
2.int Med3(int x,int y,int z)：呼叫時需給3個不同物件的代號當參數；回傳這3個物件中能量值為中間數的物件代號。
3.void Answer(int ans)：欲結束時呼叫，有一個參數，就是能量值為中間數的物件代號；並結束程式的執行。

一些限制：
N代表物件，則N為奇數且5 ≤ N ≤ 1499。
i代表物件代號，則1 ≤ i ≤ N。
Yi代表物件能量值，則1 ≤ Yi ≤ N，且所有能量值都不同。
程式不可呼叫Med3函式多於7777次。

Input:Output:

No Input.

No Output.

HINT:

範例：
若 Y1 到 Y5 依序為{2,5,4,3,1}，則下面是一組可能的回答。

詢問	結果
GetN();	回傳5。
Med3(1, 2, 3);	回傳3。
Med3(3, 4, 1);	回傳4。
Med3(4, 2, 5);	回傳4。
Answer(4);	正確

Source:

IOI 2000

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10