Есенен турнир - Шумен 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;
}
Автори: Орлин Тенчев и Светослав Колев
обратно към текущ брой
|