Одно из самых оптимальных решений по скорости работы. Сложность - порядка длины числа (десятичного логарифма).
unsigned long long P10[] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000, 10000000000LL};
unsigned long long P5[] = {1,5 ,25 ,125 ,625 ,3125 ,15625 ,78125 ,390625 ,1953125 , 9765625};
unsigned long long P45[2][9] =
{4,45,454,4545,45454,454545,4545454,45454545, 454545454,
5,54,545,5454,54545,545454,5454545,54545454, 545454545};
unsigned int getCount(long long a){
int r = 0;
for (;a >0; a/=10,r++) ;
return r;
}
unsigned int getFirst(long long a){
for (;a >= 10; a/=10) ;
return a;
}
unsigned long long getFullDp(int count, bool isOdd){
if (count <= 0)
return 0;
return P45[!isOdd][count-1]*P5[count];
}
unsigned long long getCountDp(long long a, int flag, int count){
if (!a && !count)
return 1;
if (!count)
return 0;
count--;
int first = a/P10[count];
long long res = 0;
for (int i=!flag;i<first; i+=2)
res+= P5[count];
if (first&1 ^ flag == 1)
res+= getCountDp(a - P10[count]*first, first&1, count);
return res;
}
unsigned long long getDP(unsigned long long a, int flag, int count){
if (!count)
return 0;
count--;
int first = a/P10[count];
long long res = 0;
for (int i=!flag;i<first; i+=2)
res+= P10[count]*i*P5[count]+getFullDp(count, i&1);
if (first&1 ^ flag == 1)
res+= P10[count]*first*getCountDp(a - P10[count]*first, first&1, count)
+ getDP(a - P10[count]*first, first&1,count);
return res;
}
unsigned long long getDP(unsigned long long a){
if (!a)
return 0;
int count = getCount(a) - 1;
int first = getFirst(a);
long long res = getFullDp(count,0) + getFullDp(count,1);
for (int i=1;i<count;i++)
res += getFullDp(i,1);
for (int i=1;i<first; i++)
res+= P10[count]*i*P5[count]+getFullDp(count, i&1);
res+= P10[count]*first*getCountDp(a - P10[count]*first, first&1,count)
+ getDP(a - P10[count]*first, first&1,count);
return res;
}
Привожу также тестирующую обвязку (полное тестирование до 1 миллиарда, осторожно с переполнениями int-а), тестовый код из решения @Harry.
bool alter(unsigned int n)
{
bool last = n&1;
n /= 10;
while(n)
{
bool now = n&1;
if (now == last) return false;
last = now;
n /= 10;
}
return true;
}
int main() {
long long sum = 0;
for(unsigned int i = 0; i <= 100000000; ++i){
if (alter(i))
sum += i;
long long r = getDP(i);
if (sum != r)
cout << i<<" "<<sum<<" "<<r<<endl;
}
return 0;
}
Теперь как это работает)
- Мы разрешаем числу начинаться с 0.
- Мы замечаем что на промежутке [1,10^k] таких чисел будет 5^k, а их сумма нетрудно вычисляется через усреднение (там появятся средние 454545... и 545454...)
- Учимся считать суммы на таких интервалах (метод
getFullDp
)
- Учимся учитывать что в числе может быть меньше цифр (метод
getDP(long long a)
цикл res += getFullDp(i,1);
- Понимаем что если мы фиксируем 1 цифру, то задача опять сводится к нахождению суммы на подобном интервале и нахождению количества таких чисел
- Кодим нахождение количества (метод
getCountDp
)
- Кодим остальное
- Боремся с такими багами как неправильно учтённый 0 или что-то подобное.
- Для вычисления на интервале [a,b] нужно писать
getDP(b) - getDP(a-1)
if (true) {...}
доif (...) {} else;
. – andy.37 2 мар '17 в 20:23