Примеры заданий
Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.
ФИПИ № 89D1F9 ↗
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
|
|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 |
|
| * | * |
|
|
| |
| 2 |
|
|
| * | * | * |
| |
| 3 | * |
|
|
|
|
| * | |
| 4 | * | * |
|
| * | * | * | |
| 5 |
| * |
| * |
|
|
| |
| 6 |
| * |
| * |
|
|
| |
| 7 |
|
| * | * |
|
|
|
Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам D и E на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
Показать ответ
Ответ: 17
Решение.
Решение.
- Граф и таблица описывают одну и ту же схему, поэтому сопоставляем вершины по степеням (числу дорог из пункта) и по соседям: у вершины графа и соответствующей строки таблицы должно быть одинаковое число дорог, а соседи — тоже соответствовать друг другу.
- Степени вершин на графе: A — 2, B — 3, C — 2, D — 2, E — 2, F — 5, G — 2.
- Число заполненных клеток (звёздочек) в строках таблицы: 1 — 2, 2 — 3, 3 — 2, 4 — 5, 5 — 2, 6 — 2, 7 — 2.
- Начинаем с вершин, степень которых встречается реже всего, и по их соседям (и степеням соседей) восстанавливаем остальные. Получаем соответствие: A = 5, B = 2, C = 6, D = 1, E = 7, F = 4, G = 3. Соответствие найдено не однозначно (вариантов: 4), но на ответ это не влияет — нужные величины во всех вариантах одинаковы.
- Пункт D — номер 1, пункт E — номер 7. Записываем номера по возрастанию.
- Проверка перебором на Python (все перестановки номеров):
from itertools import permutations graph = 'EG GD DF EF FA FB FC AB BC'.split() # рёбра схемы table = {(1, 3), (1, 4), (2, 4), (2, 5), (2, 6), (3, 7), (4, 5), (4, 6), (4, 7)} # дороги из таблицы letters = sorted(set(''.join(graph))) for p in permutations(range(1, len(letters) + 1)): m = dict(zip(letters, p)) if {frozenset((m[a], m[b])) for a, b in graph} == {frozenset(k) for k in table}: print(m) - Ответ: 17.