Задача Bitris
Є комплект із 2N кубиків. На кожному кубику написано одне натуральне число від1 до N. Кожне із чисел написано рівно на двох кубиках. Кубики виставлені в одну колонку. Якщо два кубика з однаковими числами опиняються поруч, то вони анігілюють: обидва кубики зникають, а кубики, які стоять над ними, опускаються на звільнене місце. Потрібно розібрати стовпчик – знищити усі кубики. Для цього дозволяється переставляти місцями будь-які два поруч розташованих кубика. Перестановку можна робити тільки тоді, коли закінчаться всі можливі в даній ситуації анігіляції.
Наприклад, якщо N=4, а кубики спочатку стоять так:
|
2 |
|
4 |
|
1 |
|
3 |
|
3 |
|
4 |
|
1 |
|
2 |
то необхідно виконати одну перестановку. Кубики з міткою 3 анігілюють одразу;
|
2 |
|
4 |
|
1 |
|
4 |
|
1 |
|
2 |
переставимо місцями четвертий знизу кубик (з міткою 1) і п’ятий знизу кубик (з міткою 4);
|
2 |
|
1 |
|
4 |
|
4 |
|
1 |
|
2 |
після цього анігілюють послідовно кубики з міткою 4, з міткою 1 і з міткою 2. Можна, звичайно, переставити третій і четвертий знизу кубики (в цьому випадку кубики з міткою 1 і з міткою 4 анігілюють одночасно, а вслід за ними анігілюють кубики з міткою 2), можна другий і третій.Задача полягає в тому, щоб знищити усі кубики, виконавши найменш можливу кількість перестановок. Точніше, знайти найменшу необхідну для цього кількість перестановок.
Технічні умови. Програма Bitris читає з клавіатури натуральне число N(2≤N≤100000), а далі 2N чисел - мітки кубиків від нижнього до верхнього. Всі числа розділені одним пробілом. Програма виводить на екран одне ціле невід’ємне число M – найменшу кількість перестановок, необхідну для знищення усього стовпчика.
Приклади:
|
Введення |
Виведення |
|
4 2 1 4 3 3 1 4 2 |
1 |
|
3 1 3 2 1 3 2 |
3 |
|
3 1 3 2 2 3 1 |
0 |