20391번 - Treasure Hunt 다국어언어 제한함수 구현

문제

Ahoy! Have you ever heard about pirates and their treasures? Bytie has found an old bottle while having a walk along the beach in Gdynia. The letter inside gives instructions on how to find a hidden treasure, but it is quite difficult to decipher. One thing Bytie knows for sure is that he needs to find two special points in the park nearby and the treasure will be in the middle of the path connecting them.

There are several trails in the park. Apart from that, the forest in the park is very dense, so only positions on the trails are reachable for human beings. The structure of the trails has an interesting property: for any two points lying on the trails there is a unique path connecting them. The path may lead along multiple trails, but it never visits any point more than once.

Bytie asked his friends for help in exploring the park. They will start the treasure hunt in some point of the park, located on one of the trails. They will explore the park in phases. In each phase, one of the friends chooses one point that was already explored and walks a number of steps from that point along a trail, visiting only points which were never reached by any of the friends before.

During the exploration, Bytie will be analysing the structure of the park carefully. From time to time, Bytie may guess the two special points which determine the location of the treasure. For each such guess, he wants to know the point located in the middle of the only path connecting them. Your task is to help Bytie in determining these middle points.

입력

출력

제한

• There will be at most 400 000 calls to the functions (init, path, and dig) and at most 1 000 000 000 points explored by Bytie’s friends.

커뮤니케이션

You should write a library which interacts with the grading program. The library should contain the following three functions which will be called by the grader (and any more functions if you like):

• init — this function will be called exactly once, in the beginning of the execution. It is for you to initialize your data structures etc.
  • C/C++: void init();
  When this function is called, you should assume that there is exactly one point already explored in the park, marked with the number 1.
• path — stating that one of the friends explored a new path in the park. This function is for you to build your data structures representing trails.
  • C/C++: void path(int a, int s);
  The path starts in the point number a (which was already explored) and takes s steps along a trail (s > 0 ). After each step, the current point is assigned a new number: the smallest positive integer not yet used for this purpose. This function will be called at least once.
• dig — asking where to dig for the treasure.
  • C/C++: int dig(int a, int b);
  It should return the number assigned to the point located in the middle of the path connecting the points marked with the numbers a and b. You can assume that the points a and b have already been explored and that a ≠ b. If the middle of the path is not a point with an assigned number (because the path has an odd length), the function should return the number assigned to one of the two middle points of the path — the one that is closer to a (see also the example on the next page). This function will be called at least once.

Your library may not read anything, neither from the standard input nor from any file, and may not write anything, neither to the standard output nor to any file. Your library may write to the standard error stream/file (stderr). You should be aware, however, that this consumes time during the execution of the program.

If you are writing in C/C++, your library may not contain the main function. If you are using Pascal, you have to provide a unit (see the sample programs on your disk).

예제

The table below shows a sample sequence of calls to the functions and the correct results of the dig calls. The structure of the trails in the park corresponding to this example run is shown in the figure.

힌트

첨부

• treinc.h