Текущ брой на Списание ИнфоМан
 


Международна олимпиада по информатика 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