LA 2724

From Algorithmist
Jump to navigation Jump to search

LA 2724 - Eurodiffusion[edit]

Summary[edit]

Simulate the diffusion of various types of coins on a small grid.

Explanation[edit]

A plain simulation of the process described in the problem statement is enough.

Gotchas[edit]

  • Output exactly three spaces before the name of each country and exactly three spaces between its name and the number of days.
  • Each "diffusion step" happens at once. You may imagine it this way: Each city prepares heaps of coins it wants to send to its neighbors, and then all cities send these coins at once. If you process the cities one by one, you won't get the same result.

Notes[edit]

  • The process is always finite, there is always more then enough coins.

Optimizations[edit]

Simulate the process C times, one for each coin type. In the beginning of each simulation, count the total area of the remaining countries. Each time the coins reach a new, previously empty city, decrease this counter and update the maximal time for its country, if necessary. When the counter reaches zero, stop simulation.

Input[edit]

3
France  1 4 4 6
Spain          3 1 6 3
Portugal    1 1 2 2
1
Luxembourg  1 1 1 1
2
Netherlands 1 3 2 4
Belgium     1 1 2 2
16
A 1 1 1 1
B 2 1 10 1
C 10 2 10 2
D 1 3 10 3
E 1 4 1 4
F 1 5 10 5
G 10 6 10 10
H 9 10 9 10
I 8 7 8 10
J 7 7 7 7
K 6 7 6 10
L 5 10 5 10
M 4 7 4 10
N 1 7 3 7
O 1 8 1 9
P 1 10 1 10
0

Output[edit]

Case Number 1
   Spain   382
   Portugal   416
   France   1325
Case Number 2
   Luxembourg   0
Case Number 3
   Belgium   2
   Netherlands   2
Case Number 4
   F   60717
   E   64714
   G   64714
   H   68730
   I   86485
   J   91416
   D   112377
   K   112377
   C   118045
   L   118045
   M   141852
   N   161291
   B   175250
   O   175250
   A   182441
   P   182441