INFOMAN брой 21


/*
ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА - Ямбол, 2 юни 2001 г.



Задача 1 (за 11-12 клас) -  Печатна кола

Голям правоъгълен лист е разделен равномерно с хоризонтални и 
вертикални линии на по 2k клетки във всяко от двете си направления. 
Прегъваме листа първо по средната хоризонтална, а после по средната 
вертикална линии. С получения по-малък лист постъпваме по същия начин и 
т.н., докато остане лист с размери на една клетка.
Накрая разрязваме всички прегънати места отдясно, отдолу и отгоре, така 
че се получава свитък от листа, всеки с размер на една клетка. Номерираме 
последователно страниците на свитъка (всичко 2^2k+1 на брой), започвайки от 
1. Ако върху двете страни на първоначалния, непрегънат лист, се напечата текст 
във всяка от клетките поотделно, след прегъването и разрязването ще получим 
напечатана ,,книга``. 
Всички прегъвания стават ,,навън``. Когато се прегъва по хоризонтала, 
с лице към нас остава долната половина, а когато се прегъва по вертикала, 
с лице към нас остава дясната половина.

Как трябва да бъдат разположени страниците на книгата върху 2^2k+1-те клетки на 
двете страни на изходния лист? Да означим всяка клетка върху лицевата страна на 
листа с номерата на стълба и на реда, в които се намира тя: клетката в левия 
долен ъгъл ще има координати 1 1, тази вдясно от нея Ц 2 1 и т.н. По същия начин 
приписваме координати на клетките от гърба на листа, като го обърнем към себе си.

Напишете програма QUIRE.EXE, която по зададени k (0<=k<=15) и p (1<=p<=2^2k+1) 
намира координатите на клетката, в която трябва да се отпечата страницата с номер 
p от книгата.

Във входния файл QUIRE.INP на един ред са записани числата k и p. 

Резултатът от програмата е един ред, записан във файл QUIRE.OUT. 
Редът съдържа координатите на клетката за страница  p  във вида

номер-на-стълб    номер-на-ред

Ако клетката е върху гърба на листа, поставете знак - (минус) преди първата 
координата. Също, ако текстът в клетката трябва да се вижда обърнат с горната 
си част надолу върху 
изходния лист, поставете минус преди втората координата.


Примери:
 
QUIRE.INP  (4 варианта)

1 1
1 3
1 7
2 17

QUIRE.OUT  (съответните 4 отговора)

2 1
-1 Ц2
-2 1
3 Ц2



   Идеи в решението
   ~~~~~~~~~~~~~~~~

   (1) Нека за някое k-1 страниците на книгата са L на брой.
       Тогава за k страниците са 4L и на всяка клетка при k-1 от
   листа отговаря каре (2x2) от 4 клетки при k.  Да дадем на всяко
   такова каре номера на страницата от разпределението при k-1.
   Как се разпределят по карета 4L-те страници при k?
   Страниците 1,...,L в този ред попадат в карета с номера съответно
   1,...,L; същото е и за страниците 2L+1,...,3L.  Страниците
   L+1,...,2L, както и страниците 3L+1,...,4L, попадат последователно
   в карета с номера L,...,1.

   (2) Как се разполагат 4-те страници в рамките на едно каре?
       Във всяко каре от клетки номерата на страници се появяват
   в растящ ред при обикаляне в кръг.  В карето вдясно долу на листа
   (това с номер 1, което съдържа и клетката за страница 1) пътят на
   обикаляне е IV-I-II-III-ти квадрант.  Тази схема се променя
   алтернативно:
         -- вертикалносиметрично за всяка клетка в посока надясно;
         -- хоризонталносиметрично за всяка клетка в посока нагоре.
   За гърба на листа разполагането се получава от това на лицевата
   страна, симетрично обърнато спрямо десния ръб на листа.

   (3) Разпределението на поредните номера на страници по лице/гръб
       на листа става в съответствие с шаблона ЛГГ(ЛЛГГ)...Л
   (Л - лице, Г - гръб; заграденото в скоби се повтаря колкото
   трябва пъти).

   (4) Обърнати с горната си част надолу са тези страници (и само
       тези), които са в клетки на четни редове, броено отдолу
   нагоре.

	Boyko Banchev
*/

#include <stdio.h>
#include <stdlib.h>

unsigned x,y;

void xy(unsigned long k, unsigned long p)  {
        unsigned long q;
  if (k)  {
    q = p/k;
    if (p%=k,q%2)  p = k-1-p;
    xy(k/4,p);
    x = 2*x+(x%2==q<2);
    y = 2*y+(y%2==(q+1)%4<2);
  }  else  x = y = 0;
}

int main(int argc, char *argv[])  {
        unsigned k;  unsigned long p;
  k = atoi(argv[1]);  p = atol(argv[2]);
  xy((unsigned long)1<<2*k-1,p-1);
  if (p%4/2)  {putchar('-');  ++x;}
  else  x = (1<<k)-x;
  printf("%u ",x);
  if (y%2)  putchar('-');
  printf("%u\n",y+1);
  return 0;
}