시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 256 MB147646.154%

문제

In the city of Bytemore crime level is hitting an all– time high. Among other misdemeanours, robberies are happening every day. And when the crime is committed, it is always up to a lone patrolling police officer to chase down the robber through the narrow alleys that connect street corners (commonly referred to simply as corners). Unfortunately, more often than not, robbers escape their pursuers, because they know the city much better than the police.

The Bytemore City Police Department (BCPD) is organising a summit to reduce crime. One of the initiatives is to use computer aid when pursuing the robbers. For this purpose, the BCPD has made a precise map of the city. Now they need computer software to find chasing strategies.

The pursuit problem of one officer chasing one robber is modelled as follows:

  1. The police officer chooses a corner on which to patrol.
  2. The robber then chooses a corner for the robbery (he knows where the officer is). From this moment on it is always assumed that both the officer and the robber know where each other is.
  3. The police officer’s move consists of him moving to a neighbouring corner (i.e. one that is connected to the current one by an alley) or waiting (i.e. not moving).
  4. The robber’s move consists of him moving to a neighbouring corner. Note that, unlike the police, robbers cannot wait. It is in their instinct to keep running.
  5. The police officer and the robber keep making moves one after another (starting with the officer) until one of the following happens:
    1. situation repeats itself (situation is defined by the positions of both agents and the side whose turn it is to move next). This corresponds to the robber being able to avoid the police officer indefinitely, so the robber escapes;
    2. the police officer and the robber meet on the same corner after a move of either of them. In this case the police officer catches the robber.

You have to write a program which, given the map of the city, would determine whether catching the robber is possible, and if it is, would catch him by making moves on behalf of the police officer.

Your program must assume that the robber moves optimally.

구현

You need to implement two functions:

  • start(N, A) which takes the following parameters:
    • $N$ — the number of corners (corners are labelled from $0$ to $N - 1$);
    • $A$ — a two–dimensional array that describes the alleys: for $0 \le i, j \le N - 1$, $$ A[i,j] \text{ is } \begin{cases} \text{false}  & \text{if }i \text{ and } j \text { are not joined by any alley} \\ \text{true}   & \text{if }i \text{ and } j \text { are joined by an alley} \end{cases} $$ All alleys will be bidirectional (i.e. $A[i, j] = A[j, i]$ for all values of $i$ and $j$) and there will be no alleys connecting a corner to itself (i.e. $A[i, i]$ will be false for all values of $i$). Also, you may assume that it will always be possible to reach any corner from any other corner by moving along the alleys.
    If it is possible to catch the robber on the map described by the parameters, function start should return the label of the corner on which the police officer chooses to patrol. Otherwise, it should return -1.
  • nextMove(R) which takes as a parameter the label $R$ of the current corner of the robber and must return the label of the corner where the officer will be after his move.

Function start will be called exactly once before any calls to nextMove are made. If start returns -1, then nextMove will not be called. Otherwise, nextMove will be called repeatedly until the pursuit ends. More precisely, the program will terminate as soon as one of the following happens:

  • nextMove returns an invalid move;
  • the situation repeats itself;
  • the robber is caught.

예제

Let’s take a look at the example illustrated on the right. In this case any corner is a good starting position for the police officer. If he starts in the corner 0, he can wait in his first move and the robber will run into him. On the other hand, if he starts on any other corner, he can wait until the robber moves to corner 0, and then move there.

Here’s how a sample session could look like:

Function call Returns
start(4, [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]) 3
nextMove(1) 3
nextMove(0) 0

Note: in the call to start above 0 denotes false and 1 denotes true for brevity.

서브태스크 1 (16점)

$2 \le N \le 500$. Each pair of corners will be connected by exactly one path of alleys.

서브태스크 2 (14점)

$2 \le N \le 500$. The network of corners and alleys will form a gridshaped structure. The grid will have at least two rows and columns and the street corner labelling will follow the pattern illustrated below.

서브태스크 3 (30점)

$2 \le N \le 100$.

서브태스크 4 (40점)

$2 \le N \le 500$.

점수

Your solution should fulfill two requirements:

  • correctly determine whether the police officer can catch the robber;
  • successfully catch the robber by making moves on behalf of the police officer, if that is possible.

In subtasks 1 and 2, your solution must implement both requirements to score any points. In subtasks 3 and 4, solutions that only implement the first requirement will score 30% of subtask’s points. If your solution only aims for partial score, you can terminate the program by outputting any invalid move (e.g. return -1 in nextMove).

Note that the standard requirements (time and memory limits, no runtime errors) must be satisfied to score any points.

샘플 그레이더

The sample grader on your computer will read data from the standard input. The first line of the input should contain integer $N$ — the number of corners. The following $N$ lines should contain the adjacency matrix $A$. Each of these lines should contain $N$ numbers, where each one is 0 or 1. The matrix must be symmetric and the main diagonal values must all be zeroes.

The next line should contain number $1$, if police can catch the robber, and $0$ otherwise.

Finally, if police officer can catch the robber, $N$ lines should follow, describing the strategy of the robber. Each of these lines should contain $N + 1$ integers between $0$ and $N - 1$. The value at row $r$ and column $c$, where $c < N$, corresponds to a situation where it’s robber’s turn, the police officer is at corner $r$ and the robber is at corner $c$, and represents the corner, which the robber has to move to. The main diagonal values will be ignored, as they correspond to situations where the robber and the police officer are at the same corner. The last value at row $r$ defines robber’s starting corner if the police officer’s starting corner is $r$.

Here is an example input to the sample grader which represents three corners that are connected together:

3
0 1 1
1 0 1
1 1 0
1
0 2 1 2
2 0 0 2
1 0 0 1

And here is the input which matches the example given in the task statement above:

4
0 1 1 1
1 0 0 0
1 0 0 0
1 0 0 0
1
0 0 0 0 1
2 0 0 0 2
3 0 0 0 3
1 0 0 0 1

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.