TopCoder

User's AC Ratio

95.8% (23/24)

Submission's AC Ratio

33.3% (52/156)

Tags

Description

馬可(Mirko)是一個麥田神祕圓圈迷,麥田神祕圓圈是由疑似被外星人壓平的穀物株幹形成的幾何造型。

在夏天的晚上,馬可決定在祖母的麥田中做他的麥田造型。
馬可是克羅埃西亞愛國人士,因此決定使用克國軍服的西洋棋盤造型,此造型為一個5x5西洋棋盤包含13個紅格子和12個白格子。


克國軍服的西洋棋盤造型

馬可祖母的麥田為由NxN細格所構成的正方形。

設麥田左下角細格的座標為(1,1),而麥田右上角細格的座標為(N,N)。

馬可決定只將西洋棋盤內的紅格子內的麥株壓平,而不動其餘區域。
他取一個奇數 M >= 3 做為紅格子的邊長,並以M x M的細格來構成一個紅格子,且每一個紅格子都在麥田的範圍內。
以形成如下圖所示的克國軍服的西洋棋盤造型:

馬可完成的麥田西洋棋盤造型範例,其中N=19且M=3。
麥株被壓平的細格以灰色顯示西洋棋盤造型的中心點在 (12, 9) 上,以黑色圓點表示。

在馬可去就寢之後,他獨特的創作引起真正外星人的興趣!

外星人用一個簡單裝置在麥田上空檢查馬可的造型。

此裝置只能判斷某個細格內的麥株是直立還是被壓平

外星人已經發現一個麥株被壓平的細格

現在需要找到馬可的西洋棋盤造型傑作的中心點,讓他們可以體會其美感。

外星人並不知道馬可的西洋棋盤造型內每一個紅格子的大小 M

請寫一個程式,
給定麥田的大小N (15 <= N <= 2000000000),和一個麥株被壓平細格的座標(X0, Y0),此程式能和外星人的裝置互動。

請找出馬可所做西洋棋盤造型的中心點的座標。

每次都會有唯一的正確答案,此答案不會因你的程式所問的問題而改變。

限制:此裝置最多只能使用300次。

本題無須input,

本題為互動題,請在開頭引入 #include "lib1341.h"

void Init(int *N, int *X0, int *Y0)
你的程式一開始應呼叫 Init() 得到三個整數N, X0, Y0。
整數N為麥田的邊長,而(X0,Y0)為已知是麥株被壓平細格的座標值。

bool Examine(int X, int Y)
以外星人裝置來檢查麥田的一個(X,Y)細格。
若麥株是被壓平的,即回傳true,若麥株直立則回傳false。

void Solution(int X, int Y);X, Y代表你認為的中心點位置。

若座標(X,Y)不在麥田的範圍內(亦即不滿足1 <= X <= N且1 <= Y <= N的條件),
或你的程式使用外星人裝置已經超過300次,
你將會得到一個WA。

Input Format

提供範例程式和範例標頭檔下載

範例標頭檔會提供你的程式執行時的詳細記錄,包括以下錯誤訊息:
N不滿足限制條件 (N doesn’t satisfy the constraints)
M不是3以上的奇數 (M is not an odd integer greater than or equal to 3)
西洋棋盤造型未能填入麥田的範圍內 (The crop formation doesn't fit in the meadow)
在細格(X0,Y0)內的麥株並非被壓平 (The grass in cell (X0, Y0) is not flattened)

使用範例標頭檔,需要給定合法的Input。
合法的Input有三行,
第一行包括麥田的邊長N和西洋棋盤內紅格子的邊長M。
第二行包括你的程式所需的已知是麥株被壓平細格的座標值(X0,Y0)。
第三行包括西洋棋盤的中心點座標值(Xc,Yc)

Sample Input 可對應到本題敘述的圖形。

Output Format

Sample Input 1

19 3
7 4
12 9

Sample Output 1

Hints

佔總分40分的測試資料中,M <= 100。

Problem Source

原TIOJ1341 / IOI 2007, Day 1
special thanks : yuscvscv

Subtasks

No. Testdata Range Score
1 0 4
2 1 4
3 2 4
4 3 4
5 4 4
6 5 4
7 6 4
8 7 4
9 8 4
10 9 4
11 10 4
12 11 4
13 12 4
14 13 4
15 14 4
16 15 4
17 16 4
18 17 4
19 18 4
20 19 4
21 20 4
22 21 4
23 22 4
24 23 8

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
11 1000 65536 262144 12
12 1000 65536 262144 13
13 1000 65536 262144 14
14 1000 65536 262144 15
15 1000 65536 262144 16
16 1000 65536 262144 17
17 1000 65536 262144 18
18 1000 65536 262144 19
19 1000 65536 262144 20
20 1000 65536 262144 21
21 1000 65536 262144 22
22 1000 65536 262144 23
23 1000 65536 262144 24