IOI '97 P1 - Mars Explorer - Olympiads Online Judge

IOI '97 P1 - Mars Explorer

Points: 20 (partial)

Time limit: 2.5s

Memory limit: 256M

Problem type

In a future mission to Mars, a pod containing a number of Mars exploration vehicles (MEVs), will be landing on the surface of Mars. All the MEVs will be released at the pod's landing site, from which they will move towards a transmitter that has landed a short distance away. While the vehicles move towards the transmitter, they are required to gather rock samples. A rock may only be sampled once, by the first MEV to visit the rock. After that, the rock may not be sampled again, but other MEVs may pass the same position. The vehicles cannot move onto rough terrain. The design of the vehicle is such that it can only move south or east in a path that follows the grid pattern from the pod to the transmitter. More than one MEV may occupy the same position at the same time.

Warning: If a MEV gets stuck, its samples are lost and the sites sampled cannot be resampled.

Task

Calculate the individual movement of the vehicles to maximise the number of rock samples collected and the number of MEVs that reach the transmitter, using the vehicles that landed with the pod.

Input Specification

The surface of the planet between the pod and the transmitter is represented by a grid $P, Q$ ~P, Q~ with the pod position always at position $(1,1)$ ~(1,1)~ and the transmitter located at $(P, Q)$ ~(P, Q)~. The definitions of the different types of terrain are as follows:

Clear terrain: 0
Rough terrain: 1
Rock sample: 2

The input consists of:

$NumberOfVehicles$ ~NumberOfVehicles~

$P$ ~P~

$Q$ ~Q~

$\begin{matrix} (X_1Y_1) & (X_2Y_1) & (X_3Y_1) & \cdots & (X_{P-1}Y_1) & (X_PY_1) \\ (X_1Y_2) & (X_2Y_2) & (X_3Y_2) & \cdots & (X_{P-1}Y_2) & (X_PY_2) \\ (X_1Y_3) & (X_2Y_3) & (X_3Y_3) & \cdots & (X_{P-1}Y_3) & (X_PY_3) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ (X_1Y_{Q-1}) & (X_2Y_{Q-1}) & (X_3Y_{Q-1}) & \cdots & (X_{P-1}Y_{Q-1}) & (X_PY_{Q-1}) \\ (X_1Y_Q) & (X_2Y_Q) & (X_3Y_Q) & \cdots & (X_{P-1}Y_Q) & (X_PY_Q) \end{matrix}$

$P$ ~P~ and $Q$ ~Q~ are the size of the grid, and $NumberOfVehicles$ ~NumberOfVehicles~ is an integer less than $1000$ ~1000~, representing the number of vehicles released by the pod. $Q$ ~Q~ lines each represent a row in the surface representation. $P$ ~P~ and $Q$ ~Q~ will not exceed $255$ ~255~.

Sample Input

2
10
8
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 1 0 2 0 0 0 0
1 1 0 1 2 0 0 0 0 1
0 1 0 0 2 0 1 1 0 0
0 1 0 1 0 0 1 1 0 0
0 1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

Output Specification

A sequence of lines representing the movements of the MEVs towards the transmitter. Each line contains a vehicle number and a digit 0 or 1, where 0 is a move South and 1 a move East.

Sample Output

Scoring

Your solution will be deemed correct if the number of samples collected and taken to the transmitter + number of MEVs reaching the transmitter - number of MEVs not reaching the transmitter is equal to the maximum possible score. Note that an illegal move invalidates a solution set. An illegal move occurs when a MEV is moved over rough terrain, or outside the grid.

Comments

-2
1yangdan commented on Feb. 12, 2018, 2:45 a.m.
Get this dumb ass question down the problem list. It has a flaw that embarrasses even me: Try this, for those who think they had solved this retarded mess:

2 10 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 2 0 1 2 0 0 0 2 2 0 2 1 0 2 0 0 2 0 2 0 0 1 0 2 2 2 0 0 2 0 2 0 0 2 2 0 0 0 2 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

For those who can get 14 samples, you can get 16 samples in total by doing:

5 R

1 D

2 R

3 D

3 R

3 D

That's the first one.

second one:

3 D

1 R

2 D

6 R

2 D

2 R

2

aeternalis1 commented on Feb. 12, 2018, 1:33 p.m.

...so what exactly is the flaw? Stating an incorrect answer and a correct answer for a test case doesn’t really show anything.

2

Evan_Yu123 commented on Feb. 12, 2018, 2:00 p.m.

A lot of the algorithms (at least 1) that AC-ed would output 14 as the answer for this test case, but the correct answer is 16.