asyan.org
добавить свой файл
1
1. Сновида­–2.

У задачі вимагається знайти кількість коренів з відомої перестановки α, тобто, кількість таких перестановок β, що



Розглянемо циклічне подання перестановки β:

,

де в окремих дужках записані цикли перестановки (всього k циклів):



Розглянемо, що станеться з циклом при подвійному застосу­ванні перестановки:

  1. Якщо цикл має непарну довжину (кількість елементів), то він перетвориться на цикл такої самої довжини з тими самими еле­мен­тами:

.

  1. Якщо цикл має парну довжину, то квадрат перестановки місти­тиме два цикли однакової довжини:

.

Отже, при подвійному застосуванні перестановки, кожен її цикл непар­ної довжини перетворюється на цикл такої самої довжини, а кожен цикл парної довжини розпадається на два цикли однакової довжини. Звідси випливає критерій існування кореня у перестановки: якщо перестановка має цикли однакової парної довжини 2t, то кількість таких циклів має бути парною.

Алгоритм побудови кореня з перестановки такий:

  1. Всі цикли парної довжини розбити на пари однакової довжини й об’єднати кожну пару в один цикл.

  2. Деякі з циклів непарної довжини розбити на пари однакової довжини і об’єднати кожну пару в один цикл. В інших циклах лише змінити порядок елементів.

Для обчислення кількості коренів, необхідно врахувати такі моменти:

  1. Якщо ми маємо N циклів однакової парної довжини, то розбити їх на пари можна  способами.

  2. Якщо ми маємо N циклів однакової непарної довжини, то роз­би­ти деякі з них на пари можна такою кількістю способів:



  1. Об’єднати два цикли однакової довжини L можна L різними способами.

Алгоритм розв’язання задачі такий:

  1. Знайти всі цикли перестановки і кількість циклів кожної довжини.

  2. Якщо для деякої парної довжини кількість циклів непарна, відпо­відь: 0.

  3. Для кожної довжини t, для якої кількість циклів Nt > 0 обчислити таке число:



  1. Відповіддю є добуток всіх тих At , для яких Nt > 0.

Наприклад, для перестановки (1 2 4 3 6 5):

  • перестановка складається з 4-х циклів: (1)(2)(3,4)(5,6). Є два цикли довжини 1, і два цикли довжини 2;

  • циклів однакової парної довжини парна кількість, тому корінь існує;

  • , ;

  •  ;

  • дана перестановка має 4 корені: (1 2 5 6 4 3), (1 2 6 5 3 4), (2 1 5 6 4 3) і (2 1 6 5 3 4).

2. Карти

Давайте з’ясуємо, де знаходилась карта, що після виконання однієї ітерації опинилась на місці p. Якщо pN − 1, то це число було на непарному місці, а якщо ≥ N, то це число було на парному місці. Справді, дія 1 розбиває колоду на «парні» та «непарні» карти, а дія 3 (склеювання) «парні» карти ставить попереду «непарних». Зауважимо, що на місце p стане карта, яка до виконання дій 1–­3 була на місці:

  • 2p − 1 при p < 1 + [Na / b];

  • 2+ 1 при 1 + [Na / b] ≤ p < N;

  • 2(− (− 1)) при N ≤ p < N + [Na / b];

  • 2(− (− 1)) + 2 при N + [Na / b] ≤ p < 2N − 1.

У розв’язанні реалізуємо функцію prev( pN ), що повертатиме номер місця, де знаходилась карта, що після виконання ітерації опинилася на місці p.

Для того, щоб визначити кінцевий стан колоди, будемо відстежувати розташування останніх двох карт „з кінця”:

  • при N = 1 маємо (1, 2);

  • при N = 2 маємо (prev(1, 2), prev(2, 2));

  • при N = 3 маємо (prev(prev(1, 2), 3), prev(prev(2, 2), 3)) і т.і. .


3. Гра

Елементарною позицією гри, яку позначатимемо четвіркою невід’­єм­них цілих чисел (i0 ; i1 ; j0 ; j1) при справдженні нерівностей

0 ≤ i0i1 < M, (1)

0 ≤ j0j1 < N, (2)

назвемо фрагмент з початкового поля, отриманого вилученням з першої групи точок усіх, окрім точок з номерами i0 , i0 + 1 , … , i1 та вилученням з другої групи точок усіх, окрім точок із номерами j0 , j0 + 1 , … , j1 . Інакше кажучи, елементарна позиція (i0 ; i1 ; j0 ; j1) є множиною точок двох типів:

  • або (0; i) при справдженні нерівностей (1);

  • або (1; j) при справдженні нерівностей (2).

Порожнє поле також вважатимемо элементарною позицією.

Довільним дозволеним ходом ми переходимо від такої елементарної позиції або до іншої елементарної позиції, або до комбінації (об’єднання) двох незалежних елементарних позицій. Незалежних у тому розумінні, що кожним наступним ходом можна з’єднати або пару точок з першої позиції, або пару точок з другої, але не можна з’єднати точку з першої позиції із точкою з другої (адже їх розділяє відрізок, що його щойно провели). Саме тому можемо без­по­середньо застосувати метод Шпраґе-Ґранді:

  1. індекс позиції (так зване число Шпраґе-Ґранді) дорівнює наймен­шому з індексів позицій, які неможливо отримати ходом з даної позиції;

  2. індекс комбінації двох незалежних позицій дорівнює побітовій сумі (див. операцію xor у мові Паскаль) індексів цих позицій.

Детальний виклад теорії див. у публікації від 18 грудня 2007 року на сайті http://kievoi.narod.ru/ → Зміст → Програма спеціального курсу «Прикладна мате­ма­­тика», у Післямові «для студентів вищих навчаль­них закладів».

Переберемо всі можливі позиції (i0; i1; j0; j1) у лексико­графічному порядку, і для кожної такої позиції обчислимо її індекс, викорис­тову­ючи попередньо підраховані індекси.

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

Наприклад, нехай M = 4, N = 10, і нас цікавить, чи є виграшним перший хід 2 5 (за умови, що точка 2 першої групи та точка 5 другої мають однаковий колір). Нехай id[][][][] — масив обрахованих індексів позицій. Тоді індекс позиції, що утворюється після першого ходу 2 5, дорівнює id[0][1][0][4] xor id[3][3][6][9] (відповідно до другого пункту означення індексу). Рівність цього числа нулю означає виграшність ходу 2 5, відмінність цього числа від нуля — програшність.

50% балів можна набрати без використання вказаного методу, по­будувавши в оперативній пам’яті граф гри та провівши аналіз його позицій «з кінця гри» згідно з означенням виграшних і програшних позицій.