IOI '97 P1 - Mars Explorer

View as PDF
Submit solution
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.

0000000000
0000011000
0001020000
1101200001
0100201100
0101001100
0120000100
0000000000

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 with the pod position always at position (1,1) and the transmitter located at (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

P

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 and Q are the size of the grid, and NumberOfVehicles is an integer less than 1000, representing the number of vehicles released by the pod. Q lines each represent a row in the surface representation. P and Q will not exceed 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

1 1
1 0
2 1
2 0
1 1
1 1
2 0
2 1
2 0
2 0
2 0
2 0
1 1
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1

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. ← edited

    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. ← edited

      ...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.