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


Първо контролно след НОИ, 2006 г., задача Traverse

Уловието на задачата може да прочетете тук.

Решение

Решението на тази задача се базира на няколко наблюдения:

1.       Първото задраскано число за 1-вото обхождане в права посока е 2N-1.

2.       След като го задраскаме, интервала [0, 2N]се разбива на 2 по-малки съответно: [0, 2N-1]и [2N-1,2N]

3.       Обхождането на масива се разбива на две равни части и важат следните твърдения:

a.       При j-то обхождане на интервала [0, 2N-1]в права посока се задраскват толкова числа, колкото при (j-1)-то обхождане на интервала [2N-1, 2N]в обратна посока.

b.       При j-то обхождане на интервала [0, 2N-1]в обратна посока се задраскват толкова числа, колкото при j-то обхождане на интервала [2N-1, 2N] в права посока.

 

Твърденията 3а и 3b могат лесно да се докажат като се използва индукция.

Тези наблюдения водят до следните зависимости за броя числа задраскани при j-то обхождане на интервал с дължина 2i в права или обратна посока (0 – обозначава права посока, 1 – обратна посока):

 

Ако j е равно на 0, opt[i][j][0] = 1 + opt[i-1][j][0],

в противен случай opt[i][j][0]= opt[i-1][j-1][1] + opt[i-1][j][0]

opt[i][j][1] = opt[i-1][j][1] + opt[i-1][j][0]

 

След като се изчисли масива opt[][][] по показания начин, ще може за всяка позиция да се каже числото, което стои на тази позиция в списъка и посоката на обхождане, при която то е задраскано. Остава да се разбере кое точно е числото. Функцията f(int i, int j, int k, num s) прави точно това, като единственото, което решава е дали числото е преди средата или след средата, като това става с малка проверка в масива opt[][][] (използва се правило 3). След като се провери това се модифицира числото s (вади се първата половина от обхождането ако търсеното число е във втората) и се извиква функцията за съответната част. Върнатата стойност се модифицира, за да се получи верният отговор за голямата редица.

 

Забележка: налага се използването на дълги числа (използва се структура num).


Примерна реализация


/*
FROM: 2006 K1
PROB: traverse
KEYW: decoding, dynamical programming
*/

#include <cstdio>
#include <cassert>
#include <cstring>

const int MAXN = 1 << 10;
const int MAXT = 1 << 9;

const int MAX = 1 << 5;
const int BASE = 1000000000;

struct num {
     int a[MAX];
     num () {for (int i = 0; i < MAX; ++i) a[i] = 0;}
     num (const num &b) {for (int i = 0; i < MAX; ++i) a[i] = b.a[i];}
     num (int b) {for (int i = 0; i < MAX; ++i) a[i] = 0; a[0] = b;}

     num& operator = (const num &b) {
          for (int i = 0; i < MAX; ++i) a[i] = b.a[i]; 
          return *this;
     }

     bool operator <= (const num &b) {
          int i; 
          for (i = MAX-1; i > 0 && a[i] == b.a[i]; --i); 
          return a[i] <= b.a[i];
     }

     bool operator == (const num &b) {
          int i; 
          for (i = 0; i < MAX && a[i] == b.a[i]; ++i); 
          return i == MAX;
     }

     num& operator += (const num &b) {
          int pr = 0;
          for (int i = 0; i < MAX; ++i) {
               a[i] += b.a[i] + pr;
               pr = a[i] / BASE;
               a[i] %= BASE;
          }
          assert (!pr);
          return *this;
     }

     num operator + (const num &b) const {
          num ret (*this);
          ret += b;
          return ret;
     }

     num& operator -= (const num &b) {
          for (int i = 0; i < MAX - 1; ++i) {
               if (a[i] < b.a[i]) {
                    a[i] += BASE;
                    --a[i+1];
               }
               a[i] -= b.a[i];
          }
          assert (a[MAX-1] >= 0);
          return *this;
     }

     num operator - (const num &b) const {
          num ret (*this);
          ret -= b;
          return ret;
     }

     void scan () {
          char buf[MAX*9];
          fgets (buf, sizeof (buf), stdin);
          int len = strlen (buf) - 1;
          int fid = len / 9;
          for (int i = 0; i < MAX; ++i) a[i] = 0;
          for (int i = 0; i < len; ++i) {
               if (!((len - i) % 9)) --fid;
               a[fid] *= 10;
               a[fid] += buf[i] - '0';
          }
     }

     void prnt (bool b = 1) const {
          int i;
          for (i = MAX-1; i > 0 && !a[i]; --i);
          printf ("%d", a[i]);
          for (--i; i >= 0; --i) printf ("%09d", a[i]);
          if (b) printf ("\n");
     }
};

int N, K;

num pow2[MAXN];
num opt[MAXN][MAXT][2];

num f (int i, int j, int k, num s) {
     if (j == 0 && k == 0 && s == 0) return pow2[i-1];

     if (j == 0 && k == 0)
          return pow2[i-1] + f (i - 1, j, k, s - 1);

     if (k == 0) {
          if (opt[i-1][j-1][1] <= s) {
               s -= opt[i-1][j-1][1];
               return pow2[i-1] + f (i - 1, j, 0, s);
          } else
               return pow2[i-1] - f (i - 1, j - 1, 1, s);
     } else {
          if (opt[i-1][j][1] <= s) {
               s -= opt[i-1][j][1];
               return pow2[i-1] - f (i - 1, j, 0, s);
          } else
               return pow2[i-1] + f (i - 1, j, 1, s);
     }
}

int main () {
     scanf ("%d", &N);

     int i, j, k;
     pow2[0] = 1;
     for (i = 1; i <= N; ++i) pow2[i] = pow2[i-1] + pow2[i-1];

     for (i = 1; i <= N; ++i)
          for (j = 0;; ++j) {
               opt[i][j][0] = (j ? opt[i-1][j-1][1] : 1) + opt[i-1][j][0];
               opt[i][j][1] = opt[i-1][j][1] + opt[i-1][j][0];
               if (opt[i][j][1] == 0) break;
          }

     num crnt;
     scanf ("%d\n", &K);
     for (i = 0; i < K; ++i) {
          crnt.scan ();
          crnt -= 1;
          for (j = 0;; ++j)
               for (k = 0; k < 2; ++k)
                    if (opt[N][j][k] <= crnt)
                         crnt -= opt[N][j][k];
                    else {
                         f (N, j, k, crnt).prnt ();
                         goto nxti;
                    }
          nxti:;
     }

     return 0;
}

Автор: Искрен Чернев

обратно към текущ брой