КилоМетровые пути

год. На рынке Нью-Йорка есть две фирмы, которые хотят начать строить метро: и . В Нью-Йорке есть только густонаселенных района. Метростроители по очереди решают, какие два района соединить, за "свой ход" метростроитель может построить только один перегон. (Перегоны метро могут соединять между собой любые два района).

К тому же, известно, что жители будут пользоваться только тем перегоном, который был построен раньше (если есть хотя бы два перегона, соединяющие два одних и тех же района). Таким образом, метростроителям не имеет смысла строить перегон между двумя районами, если между ними уже существует хотя бы один перегон.

Кольцевой веткой считается та, по которой можно проехаться от одной станции до другой и вернуться обратно, не проезжая по одному и тому же перегону два раза. Предпочтения жителей Нью-Йорка таковы, что та фирма, которая первой построила свою кольцевую ветку, выигрывает рынок всех районов полностью (люди в Нью-Йорке любят карусели). Но если такой фирмы нет – то фирмы делят рынок всего Нью-Йорка пополам. ходит первой.

Кто из фирм захватит рынок?