Международна олимпиада по информатика 2005, Задача 2.2. RECTANGLE GAME
Уловието на задачата
може да прочетете тук.
Решение
За стратегията на игране в тази задача може да се използва
факта, че ако една позиция е от вида (2p*k+2p-1, k), то тази позиция е губеща. До този извод достигаме като имаме предвид, че
позициите от вида (k,k)са губещи, от там следва, че тези от
вида (2*k+1, k) са губещи, (2*(2*k+1)+1, k)са губещи и т.н. Когато играч е в
ситуация (m, n)различна от тези от вида (k, k)и (2p*k+2p-1, k), той е в
печеливша позиция. Можем да приемем, че m>n. Тогава трябва да се намери най-голямото число от вида 2p*n+2p-1, което е по-малко от m.
То със сигурност е
по-голямо или равно на m/2 и затова може да се направи ход,
който води до ситуация (2p*n+2p-1,
n
), която както е споменато по-горе, е
губеща. Така винаги е възможно противника да се постави в губеща ситуация.
Ако играч е в ситуация от вида (k, k), какъвто и ход да направи противника
му, може да направи ход, който да изравни двете стойности. Така противникът
винаги е поставен в ситуация, в която двете стойности са равни. След краен брой
стъпки той ще бъде поставен в ситуация (1, 1), където ще загуби.
Може да се докаже, че ситуации от вида (2*k+1, k)са губещи с индукция по k:
1)
Нека
k = 1, тогава ситуацията е (3,
1), за която лесно може да се
провери, че е губеща;
2)
Нека
за всички стойности до някакво k-1 твърдението е изпълнено;
3)
Ще
докажем, че е вярно и за k. Когато един играч е поставен в
ситуация (2*k+1, k), той може да направи ход като намали
първата стойност. След хода му тя може да приема стойности от
k+1
до 2*k.При това положение с един ход тази
стойност може да се промени до k и ситуацията, в която е поставен
противникът е (k, k), която е губеща. Ако противникът
реши да играе като променя втората стойност, в зависимост от това дали тя е
четна или нечетна минималната стойност, която може да се получи е съответно k/2 и (k+1)/2. Възможно е 2*k+1да се намали с един ход до k+1, което не е по-малко от стойностите 2*(k/2)+1 = k+1 и
2*(k+1/2)+1 = k+2 и следователно е възможно с един ход
противникът да бъде поставен в ситуация от вида (2*r+1, r), r<k,
като за тази ситуация в стъпка 2 сме приели, че е губеща;
Така с индукция по kсе
доказва, че ситуациите от вида (2*k+1, k) са губещи.
За да се докаже, че ситуации от вида (2p*k+2p-1, k)са губещи,отново може да се използва индукция
по p, като за всяко p ще трябва да се докаже, че за всяко k това е вярно. Тук само ще бъде
скицирано как ще се направи индукцията без да бъдат прилагани доказателствата.
Ако някой се интересува от тях може да пише на e-mail адреса на списанието, за да получи
по-подробна информация. Планът на индукцията е следния:
1)
Нека
p = 1,
тогава
трябва да се провери, че (2*k+1,
k)е
губеща, това беше доказано по-горе;
2)
Нека
за всички стойности до някакво p-1твърдението е вярно;
3)
Ще
докажем, че е вярно и за p. Трябва да се докаже, че (2p*k+2p-1, k)е губеща ситуация за всяко k. Това може да се направи с индукция по
k, за така фиксираното p:
1)
Нека
k=1, тогава трябва да се докаже, че (2p+1-1, 1)е губеща ситуация. Това може лесно да
се покаже;
2)
Нека
за всички стойности до някакво k-1твърдението да е вярно;
3)
Ще
докажем, че то е вярно и за k. Това доказателство няма да бъде
описано тук, но всеки, на който му е интересно може да се опита да си го изведе
сам;
Така се доказва, че ситуациите от вида (2p*k+2p-1, k) са губещи,
което дава една печеливша стратегия в тази игра. Сложността на това решение е O(n*logn).
Примерна реализация
#include <stdio.h>
#include "creclib.h"
int main ()
{
int x,y,pom;
while (1)
{
x=dimension_x();
y=dimension_y();
if (x==y) break;
if (x>y)
{
pom=y;
while (2*pom<x) pom=pom*2+1;
cut(vertical,pom);
}
if (y>x)
{
pom=x;
while (2*pom<y) pom=pom*2+1;
cut(horizontal,pom);
}
}
return 0;
}
Автор: Анализ - Антон Димитров, Реализация - Ростислав Руменов
обратно към брой 27
|