CSES - Datatähti 2015 loppu - Results
Submission details
Task:Lukujono
Sender:SampoH
Submission time:2015-01-29 16:41:19 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.06 s1details
#20.05 s1details
#30.06 s1details
#40.07 s1details
#50.06 s1details
#60.06 s1details
#7ACCEPTED0.06 s1details
#80.06 s1details
#90.07 s2details
#100.07 s2details
#110.07 s2details
#120.07 s2details
#130.07 s2details
#140.07 s2details
#150.07 s2details
#160.07 s2details
#17--3details
#18--3details
#19--3details
#20--3details
#21--3details
#22--3details
#23--3details
#24--3details

Compiler report

input/code.cpp: In function 'long long int uolevi(long long int, long long int)':
input/code.cpp:31:5: warning: unused variable 'a' [-Wunused-variable]
  ll a = 0;
     ^
input/code.cpp:32:5: warning: unused variable 'b' [-Wunused-variable]
  ll b = 0;
     ^
input/code.cpp:33:5: warning: unused variable 'c' [-Wunused-variable]
  ll c = 0;
     ^

Code

#include <iostream>
#include <map>
#include <cmath>

using namespace std;

#define ll long long

map<ll,ll> cache;
map<ll,ll> cache2;

int kertoma[11] = {1,1,2,6,24,120,720,5040,40320,362880,3628800};
int values[100] = {0,1,1,2,3,4,6,7,9,11,13,14,19,20,22,25,29,30,36,37,42,45,47,48,60,62,64,68,73,74,84,85,93,96,98,101,119,120,122,125,137,138,148,149,154,162,164,165,193,195,201,204,209,210,226,229,241,244,246,247,278,279,281,289,305,308,318,319,324,327,337,338,388,389,391,399,404,407,417,418,446,454,456,457,488,491,493,496,508,509,545,548,553,556,558,561,625,626,632,640};

ll uolevi(ll x, ll magic) {
	if (x < 100)
		return values[x];
	ll s = 0;
	ll n = 0;
	ll v = 0;
	if (x > 10000) {		
		if (cache2.find(x) != cache2.end()) {
			ll s = cache2.at(x);
			return s;
		}
	}
	if (cache.find(x) != cache.end()) {
		ll s = cache.at(x);
		return s;
	}
	ll a = 0;
	ll b = 0;
	ll c = 0;
	ll l = 0;
	ll lv = 0;
	for (int i = 2; i <= x; i++) {
		n = x/i;
		if (n < magic) {
			break;
		}	
		if (l == n) {
			s+=lv;
			continue;
		}	
		l = n;
		if (n < 100)
			v = values[n];
		else if (n > 10000) {
			if (cache.find(n) != cache.end()) {
				v = cache.at(n);
			} else {
				v = uolevi(n,magic);
				cache[n] = v;
			}
		} else {
			if (cache2.find(n) != cache2.end()) {
				v = cache2.at(n);
			} else {
				v = uolevi(n,magic);
				cache2[n] = v;
			}
		}
		lv = v;
		s += v;
	}
	for (int i = magic; i >= 2; i--) {
		s += (x/kertoma[i])+((x%i!=0)?1:0);
	}
	return s;
}
/*ll uolevi_naive(ll x) {
	if (x == 0) return 0;
	if (x == 1) return 1;
	ll s = 0;
	ll n = 0;
	ll v = 0;
	for (int i = 2; i <= x; i++) {
		n = x/i;
		v = uolevi_naive(n);
		s += v;
	}
	return s;
}
}*/
int main(int argc, char ** argv) {
	cin.sync_with_stdio(false);

	ll n;
	cin >> n;
	
	/*ll x = uolevi(n,2);
	ll y = uolevi(n,3);
	cout << x << "\n";
	cout << y << "\n";
	cout << y-x << "\n";*/
	cout << uolevi(n,3) << "\n";
}

Test details

Test 1

Group: 1

Verdict:

input
542

correct output
11942

user output
11943

Test 2

Group: 1

Verdict:

input
929

correct output
29913

user output
29915

Test 3

Group: 1

Verdict:

input
801

correct output
23460

user output
23463

Test 4

Group: 1

Verdict:

input
935

correct output
30006

user output
30010

Test 5

Group: 1

Verdict:

input
998

correct output
33766

user output
33768

Test 6

Group: 1

Verdict:

input
942

correct output
30490

user output
30495

Test 7

Group: 1

Verdict: ACCEPTED

input
736

correct output
20285

user output
20285

Test 8

Group: 1

Verdict:

input
930

correct output
29975

user output
29977

Test 9

Group: 2

Verdict:

input
95404

correct output
90172356

user output
90178246

Test 10

Group: 2

Verdict:

input
98060

correct output
94687572

user output
94696885

Test 11

Group: 2

Verdict:

input
69495

correct output
52308390

user output
52313914

Test 12

Group: 2

Verdict:

input
92197

correct output
85306979

user output
85312556

Test 13

Group: 2

Verdict:

input
53418

correct output
32957881

user output
32960844

Test 14

Group: 2

Verdict:

input
97377

correct output
93859995

user output
93867762

Test 15

Group: 2

Verdict:

input
68065

correct output
50223001

user output
50227500

Test 16

Group: 2

Verdict:

input
95463

correct output
90201672

user output
90207425

Test 17

Group: 3

Verdict:

input
74323456

correct output
8975396101231

user output
(empty)

Test 18

Group: 3

Verdict:

input
92132055

correct output
13006378374515

user output
(empty)

Test 19

Group: 3

Verdict:

input
55135704

correct output
5354656932672

user output
(empty)

Test 20

Group: 3

Verdict:

input
98613338

correct output
14631125716007

user output
(empty)

Test 21

Group: 3

Verdict:

input
75558302

correct output
9238208186405

user output
(empty)

Test 22

Group: 3

Verdict:

input
94968034

correct output
13713914468591

user output
(empty)

Test 23

Group: 3

Verdict:

input
52163652

correct output
4858985762438

user output
(empty)

Test 24

Group: 3

Verdict:

input
94830583

correct output
13674294022172

user output
(empty)