問題一覧 > 教育的問題

No.3520 L1 Equidistant Point

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : 👑 p-adic / テスター : 👑 binap
お気に入りにしたユーザー ProblemId : 11232 / 自分の提出
問題文最終更新日: 2025-02-05 17:00:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 498 リアクティブコンテスト (順位表) の他の問題:

Problem Statement

This is a reactive problem (your program must interact with the judge's program during execution).

 

For a point $Q$ in the $xy$-plane, the $x$-coordinate and the $y$-coordinate of $Q$ are denoted by $x(Q)$ and $y(Q)$, respectively.

The $L^1$ distance (Manhattan distance) between $2$ points $Q_0$ and $Q_1$ in the $xy$-plane, namely

$\displaystyle |x(Q_0) - x(Q_1)| + |y(Q_0) - y(Q_1)| $

is denoted by $d(Q_0,Q_1)$.

 

First, you are given a positive integer $T$ and $2$ lattice points $P_0$ and $P_T$ in the $xy$-plane.

Lattice Point Loving Bot is a bot that loves lattice points.

Lattice Point Loving Bot moves on the $xy$-plane from time $0$ to time $T$. For a non-negative real number $t$ not exceeding $T$, let $P(t)$ be the coordinates of Lattice Point Loving Bot at time $t$.

You have obtained the following information from Lattice Point Loving Bot.

  • $P(0) = P_0$ and $P(T) = P_T$. (That is, Lattice Point Loving Bot moves from $P_0$ to $P_T$.)
  • For every non-negative integer $t$ not exceeding $T$, $P(t)$ is a lattice point. (That is, $P(0), P(1), \ldots, P(T)$ are all lattice points.)
  • The movement of Lattice Point Loving Bot is a concatenation of finitely many motions, consisting of $0$ or more each of uniform linear motions at speed $1$ along segments parallel to the $x$-axis or the $y$-axis and stationary motions. (Note that the duration of each motion is not necessarily an integer.)

Based on this information, you conjectured that between time $0$ and time $T$, Lattice Point Loving Bot passes at least once through a point equidistant from $P_0$ and $P_T$ with respect to the $L^1$ distance, that is, that there exists a real number $t$ satisfying

$ 0 \leq t \leq T \land d(P(t),P_0) = d(P(t),P_T) $

Hereafter, such a $t$ is called a good time.

 

You may therefore perform the following sequence of exchanges (hereafter called a query) any number of times between $0$ and $100$, inclusive.

  1. First, you choose a non-negative integer $t$ not exceeding $T$ and ask for the coordinates $P(t)$ of Lattice Point Loving Bot at time $t$.
  2. Then, Lattice Point Loving Bot answers with the coordinates of the lattice point $P(t)$.

After that, determine whether a good time exists, and if it does, find $1$ good time.

Input and Output

First, $T, x(P_0), y(P_0), x(P_T), y(P_T)$ are given from standard input on $1$ line, separated by single spaces.

$T$ $x(P_0)$ $y(P_0)$ $x(P_T)$ $y(P_T)$

Then, ask queries any number of times between $0$ and $100$, inclusive. Each query is performed via standard input and output in the following format:

  1. First, output ? and a non-negative integer $t$ not exceeding $T$ on $1$ line, separated by a single space.
  2. ? $t$
    
  3. Then, $x(P(t)), y(P(t))$ are given on $1$ line, separated by a single space.
  4. $x(P(t))$ $y(P(t))$
    

Next, output your answer to this problem to standard output in the following format:

  • If no good time exists, output ! NaN.
  • ! NaN
    
  • Determine whether a good time exists, and if it does, output ! and, for one example $t$ of a good time, the largest integer not exceeding it, $\lfloor t \rfloor$, on $1$ line, separated by a single space.
  • ! $\lfloor t \rfloor$
    

Finally, output a newline.

Constraints

Although not given in the input, $P(t)$ satisfies the following constraints:

  • $P(t)$ for non-negative real numbers $t$ not exceeding $T$ is fixed before all queries, that is, it does not change before or after a query.
  • $P(0) = P_0$ and $P(T) = P_T$.
  • For every non-negative integer $t$ not exceeding $T$, $P(t)$ is a lattice point.
  • The movement of Lattice Point Loving Bot is a concatenation of finitely many motions, consisting of $0$ or more each of uniform linear motions at speed $1$ along segments parallel to the $x$-axis or the $y$-axis and stationary motions.

The input satisfies the following constraints:

  • $T$ is an integer satisfying $1 \leq T \leq 10^3$.
  • $x(P_0)$ is an integer satisfying $-10^3 \leq x(P_0) \leq 10^3$.
  • $y(P_0)$ is an integer satisfying $-10^3 \leq y(P_0) \leq 10^3$.
  • $x(P_T)$ is an integer.
  • $y(P_T)$ is an integer.
  • For every non-negative integer $t$ not exceeding $T$, the input $x(P(t)), y(P(t))$ given in response to asking for the coordinates of Lattice Point Loving Bot at time $t$ satisfies the following.
    • $x(P(t))$ is an integer satisfying $- 2 \times 10^3 \leq x(P(t)) \leq 2 \times 10^3$.
    • $y(P(t))$ is an integer satisfying $- 2 \times 10^3 \leq y(P(t)) \leq 2 \times 10^3$.

Notes

If you are not familiar with reactive problems, please also refer to the summary on reactive problems.

In this problem, the judge result is not guaranteed for submissions that do not follow the instructions below:

  • Strictly follow the specified output format. For example, do not insert extra spaces.
  • Each time you output, end it with a newline and flush standard output.
  • Terminate your program immediately after outputting your answer to this problem.

Sample

The following is an example of an interaction in a situation where $T = 3$ and

$\displaystyle P(t) = \left\{ \begin{array}{ll} (t,0) & (0 \leq t \leq 2) \\ (2,t-2) & (2 < t \leq 3) \end{array} \right. $

hold.

Input Output Explanation
3 0 0 2 1
$T = 3$, $P_0 = (0,0)$, $P_T = (2,1)$.
? 1
You asked for the coordinates of $P(1)$.
1 0
Lattice Point Loving Bot answered that $P(1) = (1,0)$.
? 2
You asked for the coordinates of $P(2)$.
2 0
Lattice Point Loving Bot answered that $P(2) = (2,0)$.
! 1
You answered that there exists a good time $t$ satisfying $\lfloor t \rfloor = 1$. Indeed, since $d(P(1.5),P_0) = 1.5 = d(P(1.5),P(1))$, $1.5$ is $1$ of the good times, and since $\lfloor 1.5 \rfloor = 1$, this answer is correct.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。