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


НОИ - 2 кръг, 2006 г., задача Ident

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

Решение

Идеята на решението на тази задача е да се пробват да се построят числа, които се делят на A с всички възможни цифри. За да се намери най-малкото число с еднакви цифри, което се дели на A се започва с число, което съдържа една такава цифра. Нека цифрата е x. Последователно се изпробват числа състоящи се само от тази цифра и с все по-голяма дължина. За да се пресметне остатъка при делене на A за дадено число може да се използва остатъка за числото с една цифра ‘x’ по-малко. Ако този остатък е r, то новия остатък е (r*P+x)%A, като P е основата на бройната система. По този начин постепенно се изпробват числа с все повече цифри докато или се получи такова, което се дели на A или се получи остатък, който вече е бил срещан. Ако един остатък се повтори това означава, че остатъците, които ще се получават нататък ще се повтарят и никога няма да се получи остатък 0. В този случай няма смисъл да се продължава. Различният брой остатъци при делене на A е А. От тук следва, че максималният брой цифри, до който може да се достигне е A. От всички числа, които се получават се избира това, което има най-малко цифри, защото то е най-малкото като стойност. Сложността на това решение е O(A*P), тъй като се изпробват всички видове цифри и за всяка цифра се изпробват числа с максимум A на брой цифри.

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


#include <stdio.h>

#define MAXA          1000004
#define MAXP          104

#define INF           10000000

int a,p;
// list with the remainders that we already met
int rem[MAXA];
// the length of the shortest number
int minlen;
// the digit used in the smallest number
int mindig;

int main()
{
     int i;
     int curn;
     int brdig;

     scanf("%d %d",&a,&p);

     minlen = INF;
     mindig = 0;

     // try all the possible digits
     for(i=1;i<p;i++)
     {
          // start with a one-digit number
          curn = i;
          brdig = 1;
          while(curn%a != 0)
          {
               // check if this remainder was already met
               if(rem[curn%a]==i)
                    break;
               else
                    rem[curn%a] = i;

               // add one more digit and compute the new remainder
               curn = (curn*p+i)%a;

               brdig++;
          }

          // check if this number is smaller 
          // than the smallest until now
          if(curn%a==0 && brdig<minlen)
          {
               minlen = brdig;
               mindig = i;
          }
     }

     // print the answer if such was found
     // otherwise print 0
     if(mindig!=0)
          printf("%d %d\n",minlen,mindig);
     else
          printf("0\n");

     return 0;
}

Автор: Антон Димитров

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