← 返回题目列表

Codeforces · 2052/H

H. 在霍格沃茨狩猎疣猪兽

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Hunting Hoglins in Hogwarts - 原题 PDF 第 1 页
原题PDF第9页
Hunting Hoglins in Hogwarts - 原题 PDF 第 2 页
原题PDF第10页
可复制的 PDF 提取文本
ICPC 2024–2025, NERC – Northern Eurasia Finals
                        St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024
Problem H. Hunting Hoglins in Hogwarts

    Time limit:        6 seconds
    Memory limit:     1024 megabytes

This is an interactive problem.

Harry and Hermione are trying to hunt down hoglins which are haunting Hogwarts. There is a long hallway
in Hogwarts, consisting of n individual cells, numbered from 1 to n from the left to the right.

Hermione can cast a spell that would block any cell of the hallway of her choosing. After the spell is cast,
the blocked cell will remain blocked while she casts other spells.

Hoglins are simple creatures; all they do is randomly move around and bump into stuff. To be more
precise, every hoglin has a range which it considers to be accessible. Initially, when the hoglin appears, it
is a range from the cell 1 to the cell n.

Initially, a single hoglin appears in a cell of the hallway chosen uniformly at random. Then, until this
hoglin is caught, the following happens on every round of the hunt:


   • Hermione can cast a spell to block any single cell of her choosing, or do nothing.

   •  If the cell she is trying to block is the cell with a hoglin in it, the hoglin is caught. After that,
       all the blocked cells become free again, and, if there are more hoglins to be caught, a new hoglin
     immediately appears in a random location, and the hunt begins again.

   • Otherwise, the hoglin chooses a cell uniformly at random from its accessible range and tries to move
      to that cell, moving one cell at a time towards a chosen cell. Regardless of the distance, all the steps
      of the movement, as described below, happen in the same round.

   •  If the chosen cell is to the right of the hoglin, it moves to the right; if the chosen cell is to the left
      of the hoglin, it moves to the left. If the chosen cell is the same as where the hoglin is now, it does
      nothing.

   •  If at any point during the movement towards the chosen cell a hoglin is trying to move to the right
      or to the left from an unblocked cell at position i to the neighbouring blocked cell at position i ± 1,
     the hoglin updates the right or left boundary of its accessible range correspondingly to be i.

   •  If on the way to the chosen cell, the hoglin tries to move to a blocked cell, Harry and Hermione
     hear a loud sound, as the hoglin bumps into the blocked cell. In this case, the hoglin returns to the
      position it has originally started from at the beginning of this round.

   • Otherwise, if the hoglin does not bump into any blocked cells on its way, it does not change its
      accessible range and stays at the new position. In that case, Harry and Hermione hear nothing.


To free Hogwarts from hoglins, Harry and Hermione should catch k of them, but they don’t have much
time. They can only afford to hunt hoglins for at most 200 000 rounds. Please help them find an efficient
strategy to do that.

Interaction Protocol

First, the testing system will write two integers n and k (1 ≤n ≤1018; 1 ≤k ≤800) — the number of
cells in Hogwarts’ hallway and the number of hoglins that should be caught. Then the catching process
begins.

The following interaction proceeds in rounds as described in the problem statement.

At the start of each round, your program should output Hermione’s action — an integer p (0 ≤p ≤n)
representing the position of the cell Hermione is going to block. If p = 0 or the cell at position p is already
blocked, she does nothing in this round.


                                         Page 9 of 19

ICPC 2024–2025, NERC – Northern Eurasia Finals
                        St. Petersburg, Novosibirsk, Astana, Tbilisi, December 15th, 2024

Then, if the current position of the hoglin is at the newly blocked cell p, the hoglin is caught; the testing
system outputs 2, all the blocked cells become free, and interaction rounds start again. In case you caught
the k-th hoglin, the testing system outputs 3 instead of 2, and your program should immediately stop
execution.

Otherwise, the hoglin attempts to move according to the rules described in the problem statement. If in
the process it bumps into any blocked cell, the testing system outputs 1; otherwise, it outputs 0.

If your 200 000-th action does not catch the k-th hoglin, the testing system outputs -1 instead of its usual
answer, and your program should immediately stop execution to guarantee the “Wrong Answer” verdict.

The interactor in this problem is not adaptive. It is guaranteed that the hoglins follow the rules described
in the problem statement. The starting cell for each hoglin is chosen uniformly at random and their moves
are chosen uniformly at random from the range of cells that they consider accessible.

The problem has at most 15 tests.

Here is the summary of all possible interactor answers:
   • -1 — too many actions;
   • 0 — hoglin moved successfully, did not bump;
   • 1 — hoglin attempted to move, bumped into blocked cell;
   • 2 — hoglin is caught, interaction starts again;
   • 3 — hoglin is caught, stop.
Example

   standard input     standard output                   Illustration
 9 2                                                   1  2  3  4  5  6  7  8  9
                     3                                                            start at 8
 0                                                                              block 3
                     7                                            move to 4, success
 1                                                                              block 7
                     5                                            move to 9, bumped
 1                                                                              block 5
                     1                                            move to 3, bumped
 0                                                                              block 1
                     9                                            move to 4, success
 1                                                                              block 9
                     4                                            move to 5, bumped
 2                                                                              block 4, caught
                     5                                                            start at 3
 1                                                                              block 5
                                                                  move to 9, bumped                     7
                                                                                 block 7 0
                                                                  move to 1, success
                     0
                                                                       do nothing
 0
                                                                  move to 2, success
                     2
                                                                                 block 2, caught
 3

Note

We show the sample from the point of view of the hoglins.

The black dot shows the current position of the hoglin.

Crosses mark blocked cells.

White cells mark the range which the hoglin considers to be accessible; other cells are marked gray.

On the right is the action that was performed by either Hermione or the hoglin to get to this state from
the previous one.


                                        Page 10 of 19