Problem D
---- The 2003 ACM Programming Contest World Finals ----

On January 1, 2002, twelve European countries abandoned their national currency for a new currency, the euro. No more francs, marks, lires, guldens, kroner,... only euros, all over the eurozone. The same banknotes are used in all countries. And the same coins? Well, not quite. Each country has limited freedom to create its own euro coins:

“Every euro coin carries a common European face. On the obverse, member states decorate the coins with their own motif. No matter which motif is on the coin, it can be used anywhere in the 12 Member States. For example, a French citizen is able to buy a hot dog in Berlin using a euro coin with the imprint of the King of Spain.” (source:

On January 1, 2002, the only euro coins available in Paris were French coins. Soon the first non-French coins appeared in Paris. Eventually, one may expect all types of coins to be evenly distributed over the twelve participating countries. (Actually this will not be true. All countries continue minting and distributing coins with their own motifs. So even in a stable situation, there should be an excess of German coins in Berlin.) So, how long will it be before the first Finnish or Irish coins are in circulation in the south of Italy? How long will it be before coins of each motif are available everywhere?

You must write a program to simulate the dissemination of euro coins throughout Europe, using a highly simplified model. Restrict your attention to a single euro denomination. Represent European cities as points in a rectangular grid. Each city may have up to 4 neighbors (one to the north, east, south and west). Each city belongs to a country, and a country is a rectangular part of the plane. The figure below shows a map with 3 countries and 28 cities. The graph of countries is connected, but countries may border holes that represent seas, or non-euro countries such as Switzerland or Denmark. Initially, each city has one million (1000000) coins in its country’s motif. Every day a representative portion of coins, based on the city’s beginning day balance, is transported to each neighbor of the city. A representative portion is defined as one coin for every full 1000 coins of a motif.
 「そこで、単純なモデルを使って、ユーロコイン普及のシミュレーションプログラムをつくってほしい。単一額面のコインだけを考えよう。格子状の長方形の点として都市を表す。各都市に最大4つの都市(東南西北方向)が隣り合わせする。各都市がそれぞれ一国に属し、国が長方形の一部分となる。図に3カ国と28都市が示されている。国のグラフが繋がっているが、海やスイス・デンマーク等の非ユーロ国を表す部分が国境線上にあるかもしれない。初めは、各都市が自国のコインを百万枚持っているとする。毎日、一まとめ(a representative portion) のコインを隣の都市にそれぞれ運ぶことができる。一まとめとは、ちょうど同じモチーフのコイン1000枚のこと。」

A city is complete when at least one coin of each motif is present in that city. A country is complete when all of its cities are complete. Your program must determine the time required for each country to become complete.

The input consists of several test cases. The first line of each test case is the number of countries (1<=c<=20). The next c lines describe each country. The country description has the format: name xl yl xh yh, where name is a single word with at most 25 characters; xl, yl are the lower left city coordinates of that country (most southwestward city ) and xh, yh are the upper right city coordinates of that country (most northeastward city). 1<=xl<=xh<=10 and 1<=yl<=yh<=10.
 「入力に複数のテストケースが入る。各テストケースでは国の数c (1<=c<=20) が最初に入る。つぎにつづくc行に各国に関する説明が入る。その説明のフォーマット、国名(25文字までの単語ひとつ)、xl, yl, xh, yh (xl,ylはその国の最も左下(南西)に位置する都市の座標、xh,yhは最も右上(北東)にある都市の座標。1<=xl<=xh<=10 and 1<=yl<=yh<=10.」

The last case in the input is followed by a single zero.

For each test case, print a line indicating the case number, followed by a line for each country with the country name and number of days for that country to become complete. Order the countries by days to completion. If two countries have identical days to completion, order them alphabetically by name.
 「各テストケースについて、ケース番号(case number)を表示すること。その後に国名、およびその国が流通完了までの日数を1行に表示すること。流通完了の日数順で並べること。日数の同じ国が複数ある場合には、国名のアルファベット順で並べること。」

Use the output format shown in the example.

Sample Input
France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
Luxembourg 1 1 1 1
Netherlands 1 3 2 4
Belgium 1 1 2 2

Output for the Sample Input
Case Number 1
   Spain 382
   Portugal 416
   France 1325
Case Number 2
   Luxembourg 0
Case Number 3
   Belgium 2
   Netherlands 2

Comments are closed.

Post Navigation