C - Count Close Pairs 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

この問題は インタラクティブな問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

数直線上に、点 1, 2, \ldots, N が この順に 左から右に並んでいます。

最初、あなたには整数 N のみが与えられます。

その後、あなたはジャッジに以下の質問を \bm{2N} 回まで行うことができます。

  • 1 \leq i < j \leq N を満たす整数 i,j を選び、点 i と点 j の距離が 1 以下であるか質問する。

距離が 1 以下の 2 点組の個数、すなわち 1\leq i<j\leq N をみたす整数の組 (i,j) であって、点 i と点 j の距離が 1 以下であるようなものの個数を出力してください。

制約

  • 2 \leq N \leq 10^3
  • N は整数

入出力

最初に、点の個数を表す整数 N を標準入力から受け取ってください。

N

次に、あなたはジャッジに対して問題文中の質問を 2N 回まで繰り返すことができます。

質問は、以下の形式で標準出力に出力してください。 ここで、i,j は 1 \leq i<j \leq N を満たす整数である必要があります。

? i j

これに対する応答として、以下のどちらかが標準入力から与えられます。

Yes

No

ここで、Yes ならば点 i と点 j の距離が 1 以下であることを、No ならば点 i と点 j の距離が 1 より大きいことを表します。

問題の答え X が求まったら、解答を以下の形式で出力してください。 その後、ただちにプログラムを終了してください。

! X

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
  • 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
  • 点の配置および答えはあなたとジャッジの対話の開始時に固定され、あなたが行った質問などに応じて変更されることはありません。

入出力例

以下は、N = 3、点 1,2,3 の座標がそれぞれ 0,0.7,1.5 の場合の入出力例です。（点 1,2,3 の座標は入力として与えられません。）

入力 出力 説明
3 N が与えられます。
? 1 2 点 1,2 の間の距離が 1 以下かをジャッジに質問します。
Yes ジャッジから、点 1,2 の間の距離が 1 以下であるという返答を得ます。
? 1 3 点 1,3 の間の距離が 1 以下かをジャッジに質問します。
No ジャッジから、点 1,3 の間の距離が 1 以下でないという返答を得ます。
? 2 3 点 2,3 の間の距離が 1 以下かをジャッジに質問します。
Yes ジャッジから、点 2,3 の間の距離が 1 以下であるという返答を得ます。
! 2 条件をみたす組の数として 2 を解答します。

質問回数は 3 回であり、特に 2N=6 回以下です。
解答した組の数も正しいため、この後ただちにプログラムを終了することで、正解と判定されます。

Score : 300 points

Problem Statement

This is an interactive problem (in which your program and the judge program communicate via Standard Input and Output).

On a number line, points 1, 2, \ldots, N are arranged from left to right in that order.

Initially, you are given only the integer N.

Then, you can ask the judge the following question at most \bm{2N} times.

  • Choose integers i and j satisfying 1 \leq i < j \leq N, and ask whether the distance between points i and j is at most 1.

Output the number of pairs of points whose distance is at most 1, that is, the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that the distance between points i and j is at most 1.

Constraints

  • 2 \leq N \leq 10^3
  • N is an integer.

Interaction

First, receive the integer N representing the number of points from Standard Input:

N

Then, you can repeat the question described in the problem statement to the judge at most 2N times.

Output the question to Standard Output in the following format, where i and j must be integers satisfying 1 \leq i<j \leq N:

? i j

As a response to this, one of the following will be given from Standard Input:

Yes

No

Here, Yes indicates that the distance between points i and j is at most 1, and No indicates that the distance between points i and j is greater than 1.

Once you have found the answer X to the problem, output your answer in the following format, and then terminate the program immediately:

! X

Notes

  • Each time you output something, insert a newline at the end and flush Standard Output. Otherwise, the judge result may be TLE.
  • The judge result is indeterminate if you output something invalid during the interaction, or if the program terminates prematurely.
  • Terminate the program immediately after outputting your answer. Otherwise, the judge result is indeterminate.
  • The arrangement of the points and the answer are fixed at the start of the interaction between you and the judge, and do not change depending on, for example, the questions you make.

Sample Interaction

Below is an example of interaction where N = 3 and the coordinates of points 1,2,3 are 0, 0.7, 1.5, respectively. (The coordinates of points 1,2,3 are not given as input.)

Input Output Explanation
3 N is given.
? 1 2 Ask the judge whether the distance between points 1 and 2 is at most 1.
Yes Obtain the response from the judge that the distance between points 1 and 2 is at most 1.
? 1 3 Ask the judge whether the distance between points 1 and 3 is at most 1.
No Obtain the response from the judge that the distance between points 1 and 3 is not at most 1.
? 2 3 Ask the judge whether the distance between points 2 and 3 is at most 1.
Yes Obtain the response from the judge that the distance between points 2 and 3 is at most 1.
! 2 Answer 2 as the number of pairs satisfying the condition.

The number of questions is 3, which is in particular at most 2N=6.
Since the answered number of pairs is also correct, the program will be judged as correct if it terminates immediately after this.