Как я могу изменить свой код, чтобы убрать ограничение по времени?
Вопрос в том:
Есть полоса билетов с номерами из 8 цифр. Первый билет имеет номер М, последний — N. Величины M и N соответствуют следующим соотношениям: 10000000 ≤ M < N ≤ 99999999. Вам необходимо определить количество «счастливых» билетов между указанными номерами. Билет считается «счастливым», если сумма первых четырех цифр равна сумме последних четырех цифр.
И вот мой код:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int calcSumDigits(int n)
{
int sum=0;
while (n!=0)
{
sum+=n%10;
n/=10;
}
return sum;
}
int main(void)
{
int a,b,cnt=0,x,y;
cin>>a>>b;
for (int i=a;i<=b;i++)
{
x=i%10000;
y=(i-x)/10000;
if (calcSumDigits(x)==calcSumDigits(y)) cnt++;
}
cout<<cnt;
return 0;
}
Результаты верны, но программе требуется немного больше времени, чтобы дать результат. Например, когда я пытаюсь от 10000000 до 99999999, результат показывает 4379055, но это занимает более 6 секунд.
Решение
Вам просто нужно сравнить два набора сумм, сгенерированных всеми перестановками каждой половины ваших чисел — чтобы упростить, я немного округлил числа:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int calcSumDigits(int n)
{
int sum=0;
while (n!=0)
{
sum+=n%10;
n/=10;
}
return sum;
}
int SlowVersion(int a, int b) {
int cnt=0,x,y;
for (int i=a;i<=b;i++)
{
x=i%10000;
y=(i-x)/10000;
if (calcSumDigits(x)==calcSumDigits(y)) cnt++;
}
return cnt;
}
int main()
{
int lower;
int upper;
int original_lower;
int original_upper;
cout<<"enter lower:";
cin>>original_lower;
cout<<"enter upper:";
cin>>original_upper;
lower = original_lower - (original_lower%10000);
upper = original_upper + (9999 - (original_upper%10000));
cout<<"to simplify the calculations the lower was changed to:" << lower << endl;
cout<<"to simplify the calculations the upper was changed to:" << upper << endl;
int cnt=0;
const int b=lower%10000;
const int a=(lower-b)/10000;
const int b_top=upper%10000;
const int a_top=(upper-b_top)/10000;
int a_sums[a_top-a];
int b_sums[b_top-b];int counter = 0;
for (int i=a;i<=a_top;i++)
{
a_sums[counter] = calcSumDigits(i);
counter++;
}
counter = 0;
for (int x=b;x<=b_top;x++)
{
b_sums[counter] = calcSumDigits(x);
counter++;
}
int countera = 0;
int counterb = 0;
for (int i=a;i<=a_top;i++)
{
counterb = 0;
for (int x=b;x<=b_top;x++)
{
if (a_sums[countera]==b_sums[counterb]) cnt++;
counterb++;
}
countera++;
}
cnt = cnt - SlowVersion(lower,original_lower-1);
cnt = cnt - SlowVersion(original_upper+1,upper);
cout << "The total \"lucky numbers\" are " << cnt << endl;
cout << "a is " << a << endl;
cout << "b is " << b << endl;
cout << "a_top is " << a_top << endl;
cout << "b_top is " << b_top << endl;
system("PAUSE");
return 0;
}
который с вашими входами приводит к 4379055 (тот же результат, который вы получили) и работает очень быстро.
Другие решения
Других решений пока нет …