Вказівки щодо розв'язання завдання № 4
відбірково-тренувальних зборів
команди міста Києва

4.1. Вуличні перегони (графи)

  1. Номер старту відсутній в усіх рядках вхідного файлу.

  2. Номер фінішу такий, що відповідний рядок вхідного файлу містить лише прогалини.

  3. Пункт, який неможливо уникнути, має таку властивість: якщо вилучити всі дуги, що з нього виходять (в нього входять), то зі старту неможливо потрапити у фініш (перевіряти «пошуком вшир» зі старту).

  4. Пункт, що розбиває план, неможливо уникнути і він має таку властивість: множини пунктів, які можна досягнити з цього пункту і які можна досягнити зі старту на шляху до цього пункту мають порожній перетин (перевіряти «пошуком вшир» зі старту після вилучення всіх дуг, що виходять з даного пункту та «пошуком вшир» з розглядуваного пункту).

4.2. Криптограма (оптимізований перебір)

  1. Занумерувати літери у порядку їхньої першої появи у порядку зростання старшинства розрядів.

  2. Встановити номери тих літер, які нумеруються останніми для різних розрядів.

  3. Здійснити перебір всіх можливих варіантів розміщення без повторення цифр серед літер, занумерованих у вказаному порядку, з оптимізацією щодо підведення балансу (суми цифр) у кожному розряді.