soultaker-ի խոսքերից
Կառաջարկեմ նույն խնդիրը, երբ տարիների քանակը կարող է լինել մինչև 1 000 000 000, իսկ պատասխանի փոխարեն պետք է տպել քանակը 1 000 003 -ի վրա բաժանվելուց ստացվող մնացորդը (մեծ թվերից խուսափելու համար):
Երկար հանրահաշիվ գրելու հավես չկա, բայց դրա վրա մտածել կարելի ա: Իմ գրած լուծումը փաստորեն O(N) ա, նույնիսկ եթե n-րդ անդամի համար ինչ-որ բանաձև գտնեմ, չգիտեմ O(N)-ից ավելի լավ ժամանակում կլինի հաշվել, թե չէ
: Իսկ եթե պետք ա, որ մի 10 րոպեի մեջ տեղավորվի, գրածս լուծումը կարելի ա հեշտությամբ ձևափոխել, որ հիշողության օգտագործումը O(1) լինի:
Կոդ:
#include <iostream>
#include <time.h>
using namespace std;
#define MOD 1000000
double getTime()
{
return (double(clock())/CLK_TCK);
}
int F[2][40], N;
int main()
{
cin >> N;
double startTime = getTime();
F[0][15] = 1;
for (int i = 1, x = 1; i <= N; i++, x ^= 1)
{
int s = 0;
for (int j = 15; j < 35; j++)
s = (s + F[x ^ 1][j]) % MOD;
F[x][1] = s;
for (int j = 2; j <= 35; j++)
F[x][j] = F[x ^ 1][j - 1];
}
int ans = 0;
for (int i = 1; i <= 35; i++)
ans = (ans + F[x ^ 1][i]) % MOD;
cout << ans << endl;
cout << "Time: " << getTime() - startTime << endl;
return 0;
}
Իմ մոտ 450 վրկ. էր 1,000,000,000-ի համար:
Էջանիշներ