시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 14 | 7 | 6 | 46.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:
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:
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;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.
$2 \le N \le 500$. Each pair of corners will be connected by exactly one path of alleys.
$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.
$2 \le N \le 100$.
$2 \le N \le 500$.
Your solution should fulfill two requirements:
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)