CSES - Putka Open 2015 – 3/6 - Results
Submission details
Task:Onnenluku
Sender:
Submission time:2015-09-12 17:47:02 +0300
Language:C++
Status:READY
Result:52
Feedback
groupverdictscore
#1ACCEPTED19
#2ACCEPTED33
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.04 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.06 s2details
#7ACCEPTED0.06 s2details
#8ACCEPTED0.06 s2details
#9ACCEPTED0.05 s2details
#10ACCEPTED0.05 s2details
#110.06 s3details
#120.05 s3details
#130.06 s3details
#140.05 s3details
#150.06 s3details

Code

#include <iostream>
using namespace std;
typedef long long ll;

ll f(int n, int k) {
	return (k==0?1:k==1?8:9*4)*((1LL<<n)-k);
}

ll solve(string s) {
	int n = s.size();
	if (n<2) return 0;
	ll res=0;
	for(int i=2; i<n; ++i)res+=f(i,2);
	res += f(n-1,1) * (s[0]-'1');
	for(int i=1; i<n; ++i) {
		if (s[i]=='0') break;
		res += f(n-i-1,0) * (s[i]-'1' - (s[0]<s[i]));
		if (s[i]>s[0]) res+=f(n-i-1,1);
		if (s[i]!=s[0]) {
			char a=s[0],b=s[i];
			if (a>b)swap(a,b);
			for(int j=i+1; ; ++j) {
				if (j==n) {res++;break;}
				char c = s[j];
				if (c>b) {
					res += f(n-j,0);
					break;
				} else if (c==b) {
					res += f(n-j-1,0);
				} else if (c>a) {
					res += f(n-j-1,0);
					break;
				} else if (c==a) {
				} else {
					break;
				}
			}
			break;
		}
	}
	return res;
}

int main() {
	ll a,b;
	cin>>a>>b;
	cout<<solve(to_string(b))-solve(to_string(a-1))<<'\n';
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
2157 93337

correct output
1421

user output
1421

Test 2

Group: 1

Verdict: ACCEPTED

input
4875 95124

correct output
1278

user output
1278

Test 3

Group: 1

Verdict: ACCEPTED

input
5577 96352

correct output
1245

user output
1245

Test 4

Group: 1

Verdict: ACCEPTED

input
8362 92950

correct output
1076

user output
1076

Test 5

Group: 1

Verdict: ACCEPTED

input
5658 96660

correct output
1238

user output
1238

Test 6

Group: 2

Verdict: ACCEPTED

input
51312303535233 994542403556353

correct output
1453976

user output
1453976

Test 7

Group: 2

Verdict: ACCEPTED

input
25636920452341 934558290712847

correct output
1544072

user output
1544072

Test 8

Group: 2

Verdict: ACCEPTED

input
7917952071965 985207415843573

correct output
1763176

user output
1763176

Test 9

Group: 2

Verdict: ACCEPTED

input
48991581181227 907034837225965

correct output
1380248

user output
1380248

Test 10

Group: 2

Verdict: ACCEPTED

input
47968703305149 924246001328437

correct output
1396632

user output
1396632

Test 11

Group: 3

Verdict:

input
292953755324413237753216241025...

correct output
53286731528535944

user output
-34553512

Test 12

Group: 3

Verdict:

input
373990979330820426927419348165...

correct output
51580289482227600

user output
-34553512

Test 13

Group: 3

Verdict:

input
701417326319476057561825658890...

correct output
42924933948374952

user output
-34553512

Test 14

Group: 3

Verdict:

input
177202883511434557056457305647...

correct output
54500592365600640

user output
-34553512

Test 15

Group: 3

Verdict:

input
977665117437419620152569155919...

correct output
38562071809359800

user output
-34553512