oj.uz

Submission #86132

# Submission time Handle Problem Language Result Execution time Memory
86132 2018-11-25T04:02:11 Z win11905 Palindrome-Free Numbers (BOI13_numbers) C++11
100 / 100
 3 ms 736 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author win11905
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define long long long
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};


class numbers {
private:
	long a, b;
    char inp[25];
    long dp[25][11][11][2];
   	long solve(int n, int a, int b, bool st) {
		long &val = dp[n][a][b][st];
		if(~val) return val;
		if(inp[n] == 10) return val = 1;
		val = 0;
		for(int i = 0; i <= (st ? 9 : inp[n]); ++i) {
			if(i == a || i == b) continue;
			if(i == 0 && a == 10 && b == 10) val += solve(n+1, a, b, true);
			else val += solve(n+1, i, a, st || i != inp[n]);
		}
		return val;
   	}
	long get(long val) {
		if(val == -1) return 0;
		sprintf(inp, "%lld", val);
		for(int i = 0; ; ++i) {
			if(inp[i]) inp[i] -= '0';
			else {
				inp[i] = 10;
				break;
			}
		}
		memset(dp, -1, sizeof dp);
		return solve(0, 10, 10, false);
	}
public:
	void solve(istream& cin, ostream& cout) {
		cin >> a >> b;
		cout << get(b) - get(a-1) << endl;
	}
};

class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
		numbers *obj = new numbers();
		obj->solve(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Subtask #1
25.0 / 25.0

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

Subtask #2
75.0 / 75.0

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