User's AC Ratio

73.3% (11/15)

Submission's AC Ratio

22.8% (13/57)

Description

本題為互動題,僅限使用 C/C++ 作答

小鳥紳士是一位非常會射箭的人,因此你決定向他發起挑戰,
你們決定舉辦 $T$ 場比賽,每場比賽把 $N$ 個氣球排成一排,
兩人依回合制輪流射氣球,一開始由你先射,
並且使用一種特殊箭矢,這種箭矢最多可以一次射破 $K$ 顆氣球。

因為你跟他的技術都很好,所以可以控制自己要射幾顆氣球,
換句話說,你可以控制自己要射的氣球數量為 $1\sim K$ 的任意數量,
而射破最後一顆氣球的人就輸了。

當然小鳥紳士也是一位高手,因此會採用對他最好的策略進行遊戲,
如果你一開始就覺得你不管如何一定會輸,則應該直接向小鳥紳士投降,
如果不是必輸的情況下投降或是必輸情況下沒有投降,
則他會嘲笑你,然後你就會得到一個 WA

小鳥紳士也很聰明,如果你把必贏的局面玩輸了,
他還是會嘲笑你,然後你也會得到一個 WA

你可以用你的智謀與策略跟小鳥紳士比賽嗎?

Input Format

本題沒有輸入,若你輸入了任何東西,可能會導致各種不可預期的結果。

請記得 #include "lib0085.h",以下幾個是你可以使用的函式:

int Lets_shoot():請在程式一開始呼叫這個函數,這個函數會回傳給你總共要進行 $T$ 場比賽。

void Game(int *N, int *K):每場比賽開始時請呼叫這個函數,這個函數會告訴你這場比賽的 $N$ 及 $K$。

int Shooting(int x):傳入一個變數 $x$,該變數需介於 $1\sim K$,代表你要射多少顆氣球。這個函數會回傳給你一個數字,若你射完氣球後只剩一顆氣球,該函數會回傳 $0$,代表小鳥紳士投降了,則該場比賽立即結束;否則將回傳一個介於 $1\sim K$ 的值,代表在你射完氣球之後,小鳥紳士射了幾顆氣球。如果你傳入這個函數的變數 $x$ 不是介於 $1\sim K$,你就會得到一個 WA

void Surrender():如果你覺得你會輸,則呼叫此函數向小鳥紳士投降,你在呼叫這個函數後這場比賽會立即結束。

當一場比賽結束後,如果還有其他比賽,則應該呼叫 void Game(int *N, int *K) 進入下場比賽,否則可能會導致各種不可預期的結果。

在最後一場比賽結束當下,會立即幫你結束程式並判斷是否正確。

  • $1\leq T\leq 5000$
  • $1\leq N,K\leq 5000$

Output Format

本題沒有輸出,若你輸出了任何東西,你將會得到一個 WA

Sample Input 1

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

1
2 2

Sample Output 1

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

This is a good game

一開始只射一顆,留下最後一顆。

Sample Input 2

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

2
3 1
5 2

Sample Output 2

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

This is a good game

第一場比賽必輸,因此要選擇投降。
第二場比賽一開始先射一顆,接著分成下面兩種情況:

  • 小鳥紳士射一顆:則你可以射兩顆留下最後一顆
  • 小鳥紳士射兩顆:則你可以射一顆留下最後一顆

Hints

這裡提供一份範例標頭檔與可以 AC 子任務一的範例程式碼可以使用。
這份範例標頭檔中,小鳥紳士可能不會以最佳策略進行遊戲,且程式僅能判斷當剩餘氣球數介於 $2\sim K+1$ 為亂投降,其餘部分無法判斷,因此僅能呈現本題部分效果。

若在本機使用這份標頭檔與這份程式碼執行時,輸入格式如下:

第一行會有一個數字 $T$,代表進行的比賽場數。
接下來 $T$ 行,每行會有兩個數字 $N,K$,分別如題目所述。

如果你的程式被評為 WA,範例評分程式會輸出 "Wrong Answer: MSG",其中 MSG 格式與意義如下:

  • you should surrender:代表你射破最後一顆氣球而沒有投降
  • continue the game:代表你亂投降,明明不是必輸的局面卻投降了
  • break the rule:代表你違規射氣球,你可能射小於 $1$ 顆或大於 $K$ 顆
  • bad game:你在投降後又繼續射氣球或是還沒開始比賽就射氣球,也可能是比賽還沒結束就開始新的比賽

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 $T\leq4,N\leq2$ 12
2 5~21 小鳥紳士不一定會採用最好的策略,且遇到必輸的局面時可以在最後一刻,也就是剩一顆氣球時投降。
如果把必勝的局面玩輸也不會被嘲笑
60
3 0~4, 22~38 無特別限制 28

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 65536 1 3
1 1500 65536 65536 1 3
2 1500 65536 65536 1 3
3 1500 65536 65536 1 3
4 1500 65536 65536 1 3
5 1500 65536 65536 2
6 1500 65536 65536 2
7 1500 65536 65536 2
8 1500 65536 65536 2
9 1500 65536 65536 2
10 1500 65536 65536 2
11 1500 65536 65536 2
12 1500 65536 65536 2
13 1500 65536 65536 2
14 1500 65536 65536 2
15 1500 65536 65536 2
16 1500 65536 65536 2
17 1500 65536 65536 2
18 1500 65536 65536 2
19 1500 65536 65536 2
20 1500 65536 65536 2
21 1500 65536 65536 2
22 1500 65536 65536 3
23 1500 65536 65536 3
24 1500 65536 65536 3
25 1500 65536 65536 3
26 1500 65536 65536 3
27 1500 65536 65536 3
28 1500 65536 65536 3
29 1500 65536 65536 3
30 1500 65536 65536 3
31 1500 65536 65536 3
32 1500 65536 65536 3
33 1500 65536 65536 3
34 1500 65536 65536 3
35 1500 65536 65536 3
36 1500 65536 65536 3
37 1500 65536 65536 3
38 1500 65536 65536 3