Problem D
Eurodiffusion
---- 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:
 「2002年元日から、欧州12カ国が自国の通貨を新しい通貨ユーロに切り換えた。ユーロの流通地域すべてに、フランもマルクもリラもグルデンもクローネもなくなり、ユーロだけになった。すべての国々に同じ紙幣が使われている。しかしコインについては、各国が自分達のユーロコインをつくる自由が与えられている。」

“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: http://europa.eu.int/euro/html/entry.html)
 「ユーロコインは共通した欧州風デザインを共有する。コインの表に、参加国が自国の模様等のモチーフを飾ることができる。モチーフの違いに関わりなく、12参加国のすべての地域に使われる。たとえば、フランス人がスペイン国王の刻印のあるユーロコインを使って、ベルリンでホットドッグを買うことができる。」

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?
 「2002年元日に、パリで手に入れるのはフランスのユーロコインだけだった。間もなく、フランスコインでないものがパリに現われた。最終的に、異なる種類のコインすべてが12参加国に均等に流通しているかもしれない(実情は違う。すべての国が自国のコインを製造流通させているので、安定期に入っても、ベルリンにドイツコインが多いはずだ。)イタリアの南地方にフィンランドコインやアイルランドコインが最初に現われるのはいつだろう。すべての地方にすべてのコインが流通するのはいつになってからだろう。」

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.
 「最低1枚でも、すべての国のコインが入ればその都市で流通完了(complete)したという。国のすべての都市が流通完了となれば、その国も流通完了したという。各国が流通完了になるまでの時間を算出してほしい。」

Input
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.
 「入力の最後に0が入る。」

Output
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
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
0

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