Найти количество счастливых билетов
Даны 2 восьмизначные числа: N и M. К примеру: 1000 0000 и 9999 9999 надо написать код, который будет проверять, равность сумм первых и последних четырех цифр в диапазоне от N до M.
к примеру: 1234 9001 сумма первой половины 1+2+3+4=10, второй половины 9+0+0+1=10.
Надо в конце вывести сколько всего чисел подходят по этому критерию.
написала код на с++, но работает он 3.3 секунды, мне надо что бы он работал меньше секунды
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Попробуйте предвычислить для четырехзначных чисел суммы:
int lucky(int M, int N)
{
int s[10000] = {0}, total = 0;
for(int i = 0; i <= 9999; ++i)
{
for(int k = i; k; k/=10)
{
s[i] += k%10;
}
}
for(int i = M; i <= N; ++i)
if (s[i/10000] == s[i%10000]) ++total;
return total;
}
Ваша программа работает на моей машине 1.13±0.03с, моя - 0.16±0.03с.
Для CrazyElf: а вот микрооптимизация, снижающая время с 1.16 до 1.15 - немного быстрее просчитать таблицу:
int lucky(int M, int N)
{
int s[10000] = {0}, total = 0;
for(int i = 0; i <= 999; ++i)
{
int sum = 0;
for(int k = i; k; k/=10)
{
sum += k%10;
}
for(int j = 0; j < 10; ++j)
s[10*i+j] = sum+j;
}
for(int i = M; i <= N; ++i)
if (s[i/10000] == s[i%10000]) ++total;
return total;
}