oj.uz

Submission #32280

# Submission time Handle Problem Language Result Execution time Memory
32280 2017-10-06T08:21:50 Z amidethuong2 Palindrome-Free Numbers (BOI13_numbers) C++
100 / 100
 0 ms 2088 KB 
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

long long mem[2][2][21][110];
char start[21],END[21];

int N;

long long pos(int b1,int b2, int digits, int last){
	if(digits >= N){
		return 1;
	}

	long long &res = mem[b1][b2][digits][last];
	if(res >= 0) return res;


	res = 0;
	int i,sd,ed,t1,t2;

	sd = b1 ? start[digits] : 0;
	ed = b2 ? END[digits] : 9;

	for(i = sd; i <= ed; ++i){
		if(i == last%10 || i == last/10) continue;
		t1 = (b1 && i == sd);
		t2 = (b2 && i == ed);
		res += pos(t1,t2,digits+1,(last%10)*10+i);
	}

	return res;
}

int main(){
	//freopen("PFNUM.INP","r",stdin);
	//freopen("PFNUM.OUT","w",stdout);
	int i,st,en,n,m,b1,b2;
	long long sol;

	scanf("%s %s",start,END);

	n = strlen(start);
	m = strlen(END);

	for(i = 0; i < n; ++i) start[i] -= '0';
	for(i = 0; i < m; ++i) END[i] -= '0';

	sol = 0;
	if(n < 2 && m < 2) sol += END[0]-start[0]+1;
	else if(n < 2) sol += 10-start[0];

	for(N = max(2,n); N <= m; ++N){
		memset(mem,-1,sizeof(long long)*2*2*21*110);
		b1 = N == n;
		b2 = N == m;
		st = b1 ? start[0]*10+start[1] : 10;
		en = b2 ? END[0]*10+END[1] : 99;

		for(i = st; i <= en; ++i){
			if(i%10 == i/10) continue;
			sol += pos(b1 && i==st ,b2 && i==en,2,i);
		}
	}

	printf("%lld\n",sol);

	return 0;
}

Compilation message

numbers.cpp: In function 'int main()':
numbers.cpp:44:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s %s",start,END);
                          ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2088 KB Output is correct
2 Correct 0 ms 2088 KB Output is correct
3 Correct 0 ms 2088 KB Output is correct
4 Correct 0 ms 2088 KB Output is correct
5 Correct 0 ms 2088 KB Output is correct
6 Correct 0 ms 2088 KB Output is correct
7 Correct 0 ms 2088 KB Output is correct
8 Correct 0 ms 2088 KB Output is correct
9 Correct 0 ms 2088 KB Output is correct
10 Correct 0 ms 2088 KB Output is correct
11 Correct 0 ms 2088 KB Output is correct
12 Correct 0 ms 2088 KB Output is correct
13 Correct 0 ms 2088 KB Output is correct
14 Correct 0 ms 2088 KB Output is correct
15 Correct 0 ms 2088 KB Output is correct
16 Correct 0 ms 2088 KB Output is correct
17 Correct 0 ms 2088 KB Output is correct
18 Correct 0 ms 2088 KB Output is correct
19 Correct 0 ms 2088 KB Output is correct
20 Correct 0 ms 2088 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2088 KB Output is correct
2 Correct 0 ms 2088 KB Output is correct
3 Correct 0 ms 2088 KB Output is correct
4 Correct 0 ms 2088 KB Output is correct
5 Correct 0 ms 2088 KB Output is correct
6 Correct 0 ms 2088 KB Output is correct
7 Correct 0 ms 2088 KB Output is correct
8 Correct 0 ms 2088 KB Output is correct
9 Correct 0 ms 2088 KB Output is correct
10 Correct 0 ms 2088 KB Output is correct
11 Correct 0 ms 2088 KB Output is correct
12 Correct 0 ms 2088 KB Output is correct
13 Correct 0 ms 2088 KB Output is correct
14 Correct 0 ms 2088 KB Output is correct
15 Correct 0 ms 2088 KB Output is correct
16 Correct 0 ms 2088 KB Output is correct
17 Correct 0 ms 2088 KB Output is correct
18 Correct 0 ms 2088 KB Output is correct
19 Correct 0 ms 2088 KB Output is correct
20 Correct 0 ms 2088 KB Output is correct
21 Correct 0 ms 2088 KB Output is correct
22 Correct 0 ms 2088 KB Output is correct
23 Correct 0 ms 2088 KB Output is correct
24 Correct 0 ms 2088 KB Output is correct
25 Correct 0 ms 2088 KB Output is correct
26 Correct 0 ms 2088 KB Output is correct
27 Correct 0 ms 2088 KB Output is correct
28 Correct 0 ms 2088 KB Output is correct
29 Correct 0 ms 2088 KB Output is correct
30 Correct 0 ms 2088 KB Output is correct
31 Correct 0 ms 2088 KB Output is correct
32 Correct 0 ms 2088 KB Output is correct
33 Correct 0 ms 2088 KB Output is correct
34 Correct 0 ms 2088 KB Output is correct
35 Correct 0 ms 2088 KB Output is correct
36 Correct 0 ms 2088 KB Output is correct
37 Correct 0 ms 2088 KB Output is correct
38 Correct 0 ms 2088 KB Output is correct
39 Correct 0 ms 2088 KB Output is correct
40 Correct 0 ms 2088 KB Output is correct
41 Correct 0 ms 2088 KB Output is correct
42 Correct 0 ms 2088 KB Output is correct
43 Correct 0 ms 2088 KB Output is correct
44 Correct 0 ms 2088 KB Output is correct
45 Correct 0 ms 2088 KB Output is correct