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


Есенен турнир - Шумен 2005, Задача A2.Цифри

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

Решение

За простота на записа и разсъжденията е използвана десетична бройна система за описание на решението.

Решението на задачата се основава най-вече на следния факт: ако се изпишат всички числа с даден брой цифри (позволено е да имат и водещи нули – числата са от 00..000 до 99..999), всяка цифра ще бъде използвана еднакъв брой пъти. Това твърдение може да се докаже по индукция – за една цифра е вярно, защото всяка се използва по веднъж; ако приемем, че за k цифри е вярно, когато се добави още една цифра, тя може да е 0, 1, ... 7, 8 или 9 и всяка от тези цифри се използва толкова пъти колкото са k-цифрените числа => всяка от новите цифри е добавена равен брой пъти и твърдението е вярно и за k+1.

Нека се търси броят на срещанията на дадена цифра m в числата от в интервала [X000..000; Xy00..000), където X е число с C(X) цифри m в записа си, y е цифра, различна от 0, а броят на оставащите цифри е k. Броят на тези числа е y.10k. Във всяко от тях участва X и следователно и търсената цифра участва толкова пъти, колкото е в числото X. Следователно броят на срещанията на цифрата в началото на числата е C(X).y.10k. Всички числа съдържат по k цифри в края, което прави общо k.10k цифри, но всяка се среща по равен брой пъти, т.е. това число трябва да се раздели на броят на цифрите – 10, за да се намери броят на срещанията на дадената цифра в края на числата – k.10k-1. ако търсената цифра m е по-малка от y, тогава тя се среща във всички числа от Xm00..000 до Xm99..999, а те са 10k на брой.

Нека Ni е i-тата цифра на числото N, като N0 е цифрата на единиците, N1 – на десетиците, N2 на стотиците и т.н. Нека Ci е броят на срещанията на търсената цифра в позициите след i-тата . Следният алгоритъм намира броят на срещанията на цифрата m(≠0) в числата от 1 до N-1:

За всяка позиция k от числото:

1) Към отговора се добавя k.10k-1.Nk

2) Към отговора се добавя Ck.Nk.10k

3) Ако Nk > m към отговора се добавя 10k

Нека е дадено някакво число, например 25206, и търсената цифра е различна от 0. Алгоритъмът разделя числата от 00000 до 25206 на групи, за които директно се намира търсеният брой чрез изведените формули: от 00000 до 19999, от 20000 до 24999, от 25000 до 25199, от 25200 до 25205. Понеже формулите са за отворен отдясно интервал, алгоритъмът на практика намира търсеният брой за числото N-1. За да се вземе предвид и N, алгоритъмът трябва да се пусне за N+1.

Ако цифрата, за която трябва да се реши задачата е 0, настъпват известни промени, защото алгоритъмът ще брои и водещите нули, а не трябва. За всички позиции, освен последната, е сигурно, че нулите не са водещи, защото N не започва с 0. За цифрата на последната позиция към отговора се добавя (k-1).10k-1.Nk (а не k.10k-1.Nk), защото варианта с 0 в началото не се брои. Поради същата причина се пропуска и точка 3 от алгоритъма. Освен това трябва да се прибави и броят на нулите в числата с по-малко цифри: от 10 до 99 са 9.1, от 100 до 999 са 9.20, от 1000 до 9999 са 9.300 и т.н. (от логиката на стъпка 1 от алгоритъма)

 

Забележки:

1) същите разсъждения важат и за бройна система с основа p, като единствената разлика е, че навсякъде 10 се замества с p и цифрите са от 0 до p-1.

2) в примерната реализация по-долу отговорът се пази в масив, като на нулевата позиция се пазят единиците, на първата – десетиците (p-иците) и т.н. Затова, ако трябва да се добави a.pb, на позиция b в масива се добавя a.

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

								
#include <stdio.h>
#include <math.h>
#define MAX_R 1000001
#define MAX_PREN 20

//adds a*(k^b) to the sum
void add(long a, long b);

long r;
int m, k;
char str[MAX_R];
int N[MAX_R];
long C[MAX_R];
long sum[MAX_R+MAX_PREN];

int main()
{
    long i,p,power,pren;
    
    scanf("%ld%d%d%s",&r,&m,&k,str);

    //transfer the input string into array
    //fill the array C with data
    C[r-1] = 0;
    for(i=0; i<r; i++)
    {
        if(i>0) C[r-i-1] = C[r-i];
        if(str[i]>='0' && str[i]<='9') N[r-i-1] = str[i] - '0';
        else N[r-i-1] = str[i] - 'A' + 10;
        if(N[r-i-1]==m) C[r-i-1]++;
    }
    for(i=0; i<r; i++)
        if(N[i]==m) C[i]--;

    //add 1 to N to get N+1
    for(i=0; N[i]==k-1; i++) N[i]=0;
    N[i]++;
    
    //the 1st step of the algorithm
    sum[0] = C[0]*N[0];
    if(N[0]>m) sum[0]++;
    
    //the algorithm
    power = 0;
    for(i=1; i<r; i++)
    {
        if(m!=0)
        {
            add(N[i]*i,power);
            power++;
            if(N[i]>m) add(1,power);
            add(N[i]*C[i],power);
        } else {
            if(i!=r-1)
            {
                add(N[i]*i,power);
            } else {
                add((N[i]-1)*i,power);
                for(p=1; p<i; p++)
                {
                    add(p*(k-1),p-1);
                }
            }
            power++;
            if(N[i]>m && i!=r-1) add(1,power);
            add(N[i]*C[i],power);
        }
    }

    //making sum a proper p-based number
    pren = 0;
    for(i=0; i<r+MAX_PREN; i++)
    {
        sum[i]+=pren;
        pren = sum[i]/k;
        sum[i]%=k;
    }
    
    //omitting the leading zeros
    for(i=r+MAX_PREN; !sum[i]; i--);
    //and printing the output
    for(;i>=0; i--)
    {
        if(sum[i]<10) printf("%ld",sum[i]);
        else printf("%c",sum[i]-10+'A');
    }
    printf("\n");
return 0;
}

void add(long a, long b)
{
    sum[b]+=a;
}								
								
								

Автори: Орлин Тенчев и Светослав Колев


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