e-olymp 8651. Браслети (Bangles)

Задача

Шпигунам-конкурентам вдалося потрапити на склад запасних частин фірми «Magic & Stupidity», яка виготовляла магічні браслети. Стало зрозуміло, що всі браслети складалися з чотирьох різних деталей, кожна з яких мала на кінцях замки різних типів (розрізнялися за номерами). Вони з’єднувалися по колу, причому у сусідніх частин замки повинні мати однаковий номер. Знайшлося $N$ різних типів замків (позначимо їх номерами від $1$ до $N$) і $М$ типів деталей, які визначаються парою номерів замків (порядок несуттєвий). Напишіть програму, яка б підраховувала скільки існує різних наборів з чотирьох деталей для виготовлення браслетів фірмою «Magic & Stupidity».

Вхідні дані

Програма читає з першого рядка числа $N$ (кількість типів замків) та $M$ (кількість типів деталей). $(4 ≤ N ≤ 300)$. У $M$ наступних рядках наведені параметри деталей (пара номерів замків). Всі пари різні.

Вихідні дані

Програма визначає кількість варіантів браслетів.

Объяснение:

Існує два варіанти з’єднання: $(3,4) – (4,2) – (2,5) – (5,3)$ та $(1,4) – (4,5) – (5,3) – (3,1)$ У сусідніх деталях існують однакові замки. Це також справедливо для першої та останньої(четвертої) деталі.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5 7
1 3
1 4
2 4
2 5
3 4
3 5
4 5
2
2 5 8
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
5

Код программы

Решение задачи

В ячейке $x[u-1][v-1]$ стоит единица тогда и только тогда, когда у нас есть звено, имеющее на одном конце замок номер $u$, а на другом $- v$. Теперь построим таблицу, где будет записано в ячейке $y[u-1][v-1]$ количество их общих пар замков, где $u$ и $v$ это пара замков. Потом в первой таблице будем проходить по каждой строке и искать все возможные пары единиц в столбиках, пусть $u$ и $v$ это индекс выбранных столбиков. И если ячейка $y[u-1][v-1]$ больше единицы, то будем отнимать единицу в этой ячейке, чтобы отбросить случай, когда в браслете первый и четвёртый замок одинаковой. Полученное число в этой ячейке будем добавлять к ответу. А запоминать в эту же ячейку на единицу меньше, чтобы потом при подсчёте результата не посчитать один и тот же браслет два раза. Рассмотрим для наглядности пример: когда дано $5$ типов замков и $7$ типов деталей: $1-3, 1-4, 2-4, 2-5, 3-4, 3-5, 4-5$. То есть для каждой пары запомним количество общих замков, так как нам нужно, чтобы количество общих замков для пар было больше единицы, выпишем для наглядности нужные: $1-5$ имеет $2$, $2-3$ имеет $2$, $3-4$ имеет $2$, $4-5$ имеет $2$ общих замка. В первой строке в первой таблице единственная пара это $3-4$, так как общих замков этой пары больше единицы, то пара нам подходит. То есть варианты браслета $1-3-4-1$ и $1-3-4-5$, поэтому отнимем единицу и получим количество нужных браслетов, то есть один браслет уже есть, это $1-3-4-5$. Смотрим дальше, во второй строке тоже одна пара $4-5$. Варианты получаемый браслетов $2-4-5-2$ и $2-4-5-3$, опять отнимем один вариант и остальные браслеты запомним, то есть браслет $2-4-5-3$. В третей строке получится пара $4-5$, но там один вариант $3-4-5-3$, что не подходит, если бы мы ранее не запоминали на единицу меньше, то сейчас мы бы посчитали второй раз тот же браслет $3-4-5-2$, который уже есть. В итоге мы получили $2$ браслета, то есть $1-3-4-5$ и $2-4-5-3$, что есть верным ответом.

Ссылки

One thought on “e-olymp 8651. Браслети (Bangles)

  1. Хорошо, но мне нравится более лаконичное решение от Олега Петрова (я его немного ухудшил, чтобы Олег не узнал):

Добавить комментарий