Схема дорог и таблица — тренажёр

Что вообще происходит

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

Три хода, и никогда иначе

1. посчитать, сколько дорог выходит из каждого пункта схемы (это степень вершины), и то же самое по таблице — сколько заполненных клеток в строке. Одного этого не хватит: пункта с единственным в своём роде числом дорог здесь нет, как и на экзамене;
2. поэтому смотреть на соседей: у пункта не только своё число дорог, но и набор чисел у тех, куда эти дороги ведут. «Три дороги, и ведут они в пункты с 2, 2 и 4 дорогами» — такой столбец в таблице обычно уже один;
3. дальше опознавать по связям с уже найденными: как только один пункт опознан, его соседи находятся почти сразу.

Считать в уме нечего: выписывайте А — 3 (2,2,4), Б — 2 (3,4)… и рядом такой же список по таблице. Это дольше, чем «на глаз», но на глаз в этом задании и ошибаются. На экзамене всё это делается на компьютере — как показывает учитель.

Чем отличаются повороты

• длина дороги — ответ читается из одной клетки;
• сумма дорог из пункта — складывается вся строка;
• самая длинная или короткая — выбирается из строки;
• минимальное время в пути — прямой дороги нет вовсе, нужно перебрать пути; надпишите числа прямо на схеме;
• звёздочки — длин нет, и два пункта с одинаковыми связями различить нельзя. Это не ошибка условия: спрашивают именно оба возможных номера, и записать их надо по возрастанию, подряд, без пробелов;
• неоднозначное соотнесение — схема снова распутывается не до конца, но спрашивают про обычную дорогу. Хитрость в том, что неразличимая пара к ней не относится, и ответ один при любой из двух расстановок. Бросать задачу из-за того, что «два пункта не различаются», — самая частая потеря балла;
• буква по номеру — тот же разбор, но ответ буква.

Как записывают ответ

Целое число без единиц измерения: 34, а не «34 км». Два номера — подряд и по возрастанию: 25, а не «5 и 2». Буква — одна, заглавная и русская: Г, а не латинская «G» или «Г» с английской раскладки.

Это не придирка. ЕГЭ по информатике сдают за компьютером: ответ набирается в экзаменационной программе, и сверяет его машина — знак в знак. Привыкать надо здесь.

Откуда эти задачи

Задачи авторские, составлены в форме задания 1 ЕГЭ по информатике. Готовые условия никуда не скачивались: каждую схему строит генератор, у каждого она своя, и ответ у соседа другой. Схема каждый раз проверяется на то, что распутывается она единственным способом, — кроме звёздочек, где неоднозначность и есть вопрос.

Что делает программа

Подбирает, какая буква схемы какому номеру таблицы соответствует, и печатает строчку букв: АЕБВДЖГ — первая буква стоит на месте П1, вторая П2, и так до конца. Длину, сумму и путь по ней находишь сам: считать программа не умеет.

Как переписать условие

• graph — каждая линия схемы двумя буквами; порядок любой, 'АГ' и 'ГА' одно и то же;
• table — номера непустых клеток выше диагонали (П1—П2 и П2—П1 — одна дорога). Числа не нужны;
• letters — буквы схемы.

Пар в graph и table обязано быть поровну — программа печатает оба числа. Не сошлось: пропущена линия или клетка.

Шаблон

p[a-1] — буква на месте Пa: места считаются с нуля. Проверок две, потому что дорогу в graph можно было записать любой стороной.

Что вывелось

• одна строка — подпиши номера на схеме и решай дальше;
• две строки — у двух пунктов одинаковые связи, различить нечем. Это звёздочки и неоднозначное соотнесение: места, где строки различаются, и есть ответ про «какие номера могут соответствовать»; про дорогу мимо этой пары ответ один по любой строке;
• ни одной — опечатка при переписывании.