問題一覧 > 教育的問題

No.3525 Pseudo-Odd-Square Numbers

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : 👑 p-adic / テスター : 👑 binap hotman78
お気に入りにしたユーザー ProblemId : 11243 / 自分の提出
問題文最終更新日: 2026-04-18 09:35:14
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 run interactively with the judge's program).

 

As a term used only in this problem, a positive integer $n$ is called a pseudo-odd-square number if it satisfies both of the following $2$ conditions.

  • $n$ is odd.
  • There exists a divisor $d$ of $n$ satisfying $\sqrt{n} - \sqrt[3]{n} \leq d \leq \sqrt{n} + \sqrt[3]{n}$.

Pseudo-Odd-Square-Number-Loving Bot is a bot that loves pseudo-odd-square numbers.

Pseudo-Odd-Square-Number-Loving Bot is hiding an odd number $N$ and wants to know whether $N$ is a pseudo-odd-square number.

 

Initially, $A$ is given as a sequence of positive integers of length $1$ whose only element is $N$.

For a positive integer $i$ not exceeding the length of $A$, $A_i$ denotes the $i$-th element of $A$. ($A = (A_1, A_2, \ldots)$)

First, you update $A$ by performing the following sequence of exchanges (hereafter called an order) any number of times between $0$ and $10^3$, inclusive.

  1. First, you choose positive integers $i$ and $j$ not exceeding the length of $A$, choose one of $A_i + A_j$, $A_i - A_j$, $A_i \times A_j$, or, only if $A_i > 0$, the largest integer not exceeding the $A_i$-th root of $A_j$, $\sqrt[A_i]{A_j}$, that is, $\lfloor \sqrt[A_i]{A_j} \rfloor$, and call it $x$. Then you request that $x$ be inserted at the end of $A$. Here, $0 \leq x < 2^{64}$ must be satisfied.
  2. Next, Pseudo-Odd-Square-Number-Loving Bot inserts $x$ at the end of $A$.

Next, you perform the following sequence of exchanges (hereafter called a question) any number of times between $0$ and $10^2$, inclusive.

  1. First, you choose positive integers $i$ and $j$ not exceeding the length of $A$ and ask whether $A_i < A_j$ is true.
  2. Next, Pseudo-Odd-Square-Number-Loving Bot answers whether $A_i < A_j$ is true.

Finally, determine whether $N$ is a pseudo-odd-square number and tell Pseudo-Odd-Square-Number-Loving Bot the result (hereafter called the answer).

Note that orders, questions, and the answer can only be performed in this sequence. That is, after asking a question even $1$ time, you can no longer place orders.

Input and Output

First, place orders any number of times between $0$ and $10^3$, inclusive. Each order is performed through standard input and output in the following format:

  1. First, choose positive integers $i$ and $j$ not exceeding the length of $A$ and a character $\textrm{op}$ that is one of +-*r, and print a, $i$, $\textrm{op}$, and $j$ separated by single-byte spaces on $1$ line. Output for which $x$, described below, does not satisfy $0 \leq x < 2^{64}$ is invalid.
  2. a $i$ $\textrm{op}$ $j$
    
  3. Next, the integer $x$ is determined as follows.
    • If $\textrm{op}$ is +, then $x = A_i + A_j$.
    • If $\textrm{op}$ is -, then $x = A_i - A_j$.
    • If $\textrm{op}$ is *, then $x = A_i \times A_j$.
    • If $\textrm{op}$ is r, then $x = \lfloor \sqrt[A_i]{A_j} \rfloor$. Here, $A_i > 0$ must hold.
  4. Finally, $x$ is inserted at the end of $A$. There is no response to an order; in particular, the value of $x$ is not given in the input.

Next, ask questions any number of times between $0$ and $10^2$, inclusive. Each question is performed through standard input and output in the following format:

  1. First, choose positive integers $i$ and $j$ not exceeding the length of $A$, and print ?, $i$, <, and $j$ separated by single-byte spaces on $1$ line.
  2. ? $i$ < $j$
    
  3. Then, information on whether $A_i < A_j$ is true is given as follows.
    • If $A_i < A_j$, T is given.
    • T
      
    • If $A_i \geq A_j$, F is given.
    • F
      

Finally, print your answer to standard output in the following format:

  • If $N$ is a pseudo-odd-square number, print ! Yes.
  • ! Yes
    
  • If $N$ is not a pseudo-odd-square number, print ! No.
  • ! No
    

Finally, print a newline.

Constraints

Although not given in the input, $N$ satisfies the following constraints:

  • $N$ is fixed before all exchanges; that is, the value of $N$ does not change before or after the exchanges.
  • $N$ is an odd number satisfying $1 \leq N < 10^6$.

The input satisfies the following constraints:

  • The input given in response to each question is one of the characters T or F.

Notes

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

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

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

Sample

The following is an example of an interaction in which Pseudo-Odd-Square-Number-Loving Bot is hiding $N = 1$.

Initially, $A = (N) = (1)$.

Input Output Explanation
a 1 + 1 You requested that $A_1 + A_1$ be inserted at the end of $A$.
Pseudo-Odd-Square-Number-Loving Bot inserted $A_1 + A_1 = 1 + 1 = 2$ at the end of $A$, resulting in $A = (1,2)$.
a 1 - 1 You requested that $A_1 - A_1$ be inserted at the end of $A$.
Pseudo-Odd-Square-Number-Loving Bot inserted $A_1 - A_1 = 1 - 1 = 0$ at the end of $A$, resulting in $A = (1,2,0)$.
a 2 * 2 You requested that $A_2 \times A_2$ be inserted at the end of $A$.
Pseudo-Odd-Square-Number-Loving Bot inserted $A_2 \times A_2 = 2 \times 2 = 4$ at the end of $A$, resulting in $A = (1,2,0,4)$.
a 2 r 2 You requested that $\lfloor \sqrt[A_2]{A_2} \rfloor$ be inserted at the end of $A$.
Pseudo-Odd-Square-Number-Loving Bot inserted $\lfloor \sqrt[A_2]{A_2} \rfloor = \lfloor \sqrt{2} \rfloor = \lfloor 1.41421 \cdots \rfloor = 1$ at the end of $A$, resulting in $A = (1,2,0,4,1)$.
? 5 < 4 You asked whether $A_5 < A_4$.
T Pseudo-Odd-Square-Number-Loving Bot answered that $A_5 = 1 < 4 = A_4$ is true.
? 1 < 5 You asked whether $A_1 < A_5$.
F Pseudo-Odd-Square-Number-Loving Bot answered that $A_1 = 1 < 1 = A_5$ is false.
! Yes You answered that $N$ is a pseudo-odd-square number. Indeed, the divisor $1$ of the odd number $N = 1$ satisfies $\sqrt{N} - \sqrt[3]{N} = 0 \leq 1 \leq 2 = \sqrt{N} + \sqrt[3]{N}$, so this is correct.

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