Skip to content

2021 ICPC 昆明题解报告

D. Competition Against a Robot

Constraint

Input file: standard input

Output file: standard output

Time limit: 1 second

Memory limit: 256 megabytes

Description

As a tradition, the Code Village holds an annual championship, named ICPC (Intelligence Championship for Platinum Coders) to search for its most outstanding genius. The participants take part in various contests to find out who is the potential genius. The competitions include Go, Reversi, Sudoku and even Paper-Scissor-Rock, and it is fascinating to see the unpredictable result. Well... At least a few years ago. Everything changed when an AI robot came to the village - it seems weird, but as the name of the contest shows, anything related to 'intelligence' can take part freely. The robot soon won all the competitions without difficulty, and remained the defending champjon for years and years. Everyone considered it to be undefeatable. And this time, your task will be - as you have figured out - beat the robot!

You are not alone - you will have a teammate. To make the game more interesting, the organizing committee has slightly modified the rule and it will be a guessing game. The game process is as follows:

  • The judges announce two positive integers \(n, k\) to the three players - you, your teammate, and the robot.
  • The robot generates an integer sequence of length \(n\) - let's call it \(T\) - and selects a secret integer \(p \in[0, n) .\) Each element of \(T\) should fall in the range \([0, k),\) that is, each \(T_{i}(0 \leq i<n)\) should be a non-negative integer and strictly less than \(k\). Then it submits \(T\) and \(p\) to the judges. (Note that in this problem all the sequences are 0 -indexed.)
  • You receive the sequence \(T\) and the number \(p\) from the judges, and your task is to tell the exact value of \(p\) to your teammate. To achieve that, you must select exactly one index \(j \in[0, n),\) and set \(T_{j}\) to \(\left(T_{j}+1\right) \bmod k\)
  • Your teammate then receives the sequence \(T\), and has to figure out the hidden integer \(p\). Note that he doesn't have access to the original string generated by the robot; the only information he gets is the string that you write. He has only one chance to submit his answer, and if he succeeds, both of you win the game.

Some typical settings may apply here. For example, the three of you all have unlimited and accurate memory, your team can discuss strategies before the game starts (of course NOT during the game), while the robot has the access to your strategy. You can also assume that the three of you will play optimally to achieve their goals: for you two the goal is definitely to win the game, while for the robot it will do its best to prevent your victory.

Let's take some examples. For \(n=1,\) your team will definitely win by always answering \(p=0 .\) For \(n=2, k=2,\) a solution that ensures your victory works like this: your friend always answer the value of \(T_{0},\) and when you enter the room you just check if \(T_{0}\) differs from \(p:\) if so then choose \(j=0,\) otherwise choose \(j=1 .\) It is clear to see that such strategy works perfectly. However, it can be proved that for \(n=3, k=2\) your team has no chance to win at all.

There are five hours left before the competition, and you decide to do some practice by writing a program to determine that for certain pair of \((n, k),\) which side will win the game. You will have to answer \(Q\) independent queries.

Input:

The first line of input contains an integer \(Q\left(1 \leq Q \leq 10^{5}\right),\) the number of queries you have to answer. Each of the next \(Q\) lines indicates a query. The \(i\) -th among them contains two integers \(n_{i}, k_{i}\left(1 \leq n_{i}, k_{i} \leq 10^{18}\right),\) denoting the \(i\) -th situation with parameters \(n=n_{i}, k=k_{i} .\) Recall that each query is independent.

Output:

Output \(Q\) lines, the \(i\)-th of which shows the winning side of the \(i\)-th situation. If your team is going towin, print a line of \(HUMAN\); otherwise display \(ROBOT\).

standard input

3
1 10
2 2
3 2

standard output

HUMAN
HUMAN
ROBOT