Игра в города была ранее очень популярна, она помогала скрашивать долгое ожидание, например, в аэропорту или в пути.

Нам дан список городов, надо выстроить максимально длинную цепочку, но только чисто из данного списка.

Это и облегчает и усложняет одновременно нашу задачу.

Облегчает, ибо мы можем не придумывать какие-то новые, а основываться только на текущей базе данных.

И вот она. эта база

Я пойду таким путем: отброшу все города, которые на конце имеют буквы, невозможные для продолжения игры. Например, Анадырь. Кончается на мягкий знак, а с этой буквы названий городов нет. Это такие города:

Анадырь, Петропавловск-Камчатский, Улан-Удэ

Теперь отбросим те города, где первая буква тоже не сулит надежд на продолжение цепочки

Якутск, Южно-Сахалинск, Хабаровск, Горно-Алтайск, Иркутск, Биробиджан, Барнаул, Благовещенск, Владивосток, Томск

А вот город Чита можно оставить, его сделаем первым в цепочке.

Таким образом у меня получилась цепочка:

Чита

Абакан

Новосибирск

Красноярск

Кемерово (или Кызыл еще можно)

Посчитаем количество букв на которые начинаются города:

А - 2; Б - 3; В - 1; Г - 1; И - 1; К - 3; М - 1; Н - 1; П - 1; Т - 1; У - 1; Х - 1; Ч - 1; Ю - 1; Я - 1;

А теперь количество букв на которые заканчиваются города:

А - 1; Й - 1; К - 10; Л - 2; Н - 3; О - 1; Э - 1; Ь - 1

Теперь сопоставим пересечение одинаковых начальных и конечных букв

Получим возможные совпадения: А - 1; К - 3; Н - 1

Итого 5 пересечений, соответственно максимально возможно 6 городов в цепочке.

Попробуем построить.

Чита - Абакан - Новосибирск - Красноярск - Кемерово; и на этом цепочка обрывается. Получили только 5 городов. Больше получить невозможно.

Ответ: 5 городов

Интересное задание с учётом того, что в детстве многие играли в "города". Попробуем решить задачу в обратном порядке, то есть, сначала выберем так называемые тупиковые названия, которые вообще не дают цепочек. Нетрудно догадаться, что это названия, заканчивающиеся на букву, с которой не начинается ни одно другое. Такие города у нас Анадырь, Барнаул, Кемерово, Кызыл, Петропавловск-Камчатский и Улан-Удэ.

Теперь составим цепочки из двух городов. Это цепочки, заканчивающиеся на некоторых из приведенных выше городах:

Благовещенск-Кемерово

Благовещенск-Кызыл

Владивосток-Кемерово

Владивосток-Кызыл

Горно-Алтайск-Кемерово

Горно-Алтайск-Кызыл и так далее, со всеми городами, заканчивающимися на "к".

Теперь попробуем составить цепочки из трёх городов. В них будет входить город, начинающийся и заканчивающийся на букву "к":

Благовещенск-Красноярск-Кемерово (или Кызыл)

Владивосток-Красноярск-Кемерово (Кызыл) и так далее.

Дальше составляем цепочки из четырех городов. Их не так много:

Абакан-Новосибирск-Красноярск-Кемерово (Кызыл)

Биробиджан-Новосибирск-Красноярск-Кемерово (Кызыл)

Магадан-Новосибирск-Красноярск-Кемерово (Кызыл).

А теперь попробуем составить цепочку из пяти названий. Для этого задействуем единственный город, заканчивающийся на "а"

Чита-Абакан-Новосибирск-Красноярск-Кемерово (Кызыл). Это и будет самая длинная цепочка.

Чтобы цепочка получилась наиболее длинной, первым нам надо взять название города, которое начинается на такую букву, которой не заканчивается другой город, но при этом само это название должно оканчиваться на подходящую для продолжения цепочки букву. А последним, наоборот, нужно взять такое название, которое не даёт продолжения.

Много городов заканчиваются на "к", давайте посмотрим, какое может быть продолжение. Мы можем взять Красноярск, он тоже заканчивается на "к", а после него - Кемерово или Кызыл. Они оба тупиковые и будут заканчивать цепочку.

Теперь выбираем такой город, заканчивающийся на "к", у которого не крайнее начало. То есть нам точно не подойдут Томск, Якутск, Благовещенск, Владивосток, Горно-Алтайск, так как на их начальные буквы не заканчивается ни один город.

Подойдёт Новосибирск, есть города, заканчивающиеся на "н" - это Абакан, Магадан, Биробиджан. На "м" и на "б" ничего не заканчивается, а вот на "а" заканчивается Чита. Всё, дальше хода нет.

Получается цепочка максимальной длины из пяти городов:

Чита - Абакан - Новосибирск - Красноярск - Кызыл (или Кемерово).