oj.uz

Submission #631445

# Submission time Handle Problem Language Result Execution time Memory
631445 2022-08-18T06:31:35 Z mousey Palindrome-Free Numbers (BOI13_numbers) C++14
96.25 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e6;
ll a, b;

string convert(ll a)
{
	string s="";
	while(a>0)
	{
		s=(char (a%10 + '0'))+s;
		a/=10;
	}
	return s;
}

void input()
{
	cin >> a >> b;
	a--;
}

ll calc(ll a)
{
	string _a=convert(a);
	ll dp[20][10][10][3]={};
	dp[0][0][0][1]=1;
	for(int i = 1; i <= 9; i++)
	{
		if(i<_a[0]-48) dp[1][0][i][0]++;
		if(i==_a[0]-48) dp[1][0][i][1]++;
		if(i>_a[0]-48) dp[1][0][i][2]++;
	}
	
	for(int i = 2; i <= _a.size(); i++)
	{
		for(int j = 0; j < 10; j++)
		{
			for(int l = 0; l < 10; l++)
			{
				for(int k = 0; k < 10; k++)
				{
					if((j==k || j==l || k==l) && i>2) continue;
					if(i==2 && k==l) continue;
					dp[i][l][k][0]+=dp[i-1][j][l][0];
					dp[i][l][k][2]+=dp[i-1][j][l][2];
					if(k==_a[i-1]-48) dp[i][l][k][1]+=dp[i-1][j][l][1];
					if(k<_a[i-1]-48) dp[i][l][k][0]+=dp[i-1][j][l][1];
					if(k>_a[i-1]-48) dp[i][l][k][2]+=dp[i-1][j][l][1];
				}
			}
		}
	}
	ll ans=0;
	for(int i = 1; i <= _a.size(); i++)
	{
		for(int j = 0; j < 10; j++)
		{
			for(int k = 0; k < 10; k++)
			{
				for(int p = 0; p <= 2; p++)
				{
					if(i==_a.size() && p==2) continue;
					ans+=dp[i][j][k][p];
				}
			}
		}
	}
	return ans;
}

void solve()
{
	ll ans=calc(b)-calc(a);
	cout << ans;
}

int main() 
{
//	auto start_time = chrono::high_resolution_clock::now();
//	freopen("test.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    input();
    solve();
//    auto end_time = chrono::high_resolution_clock::now();
//        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
//        cout << "\n[ " << duration << " ms ]\n"; 
}

Compilation message

numbers.cpp: In function 'long long int calc(long long int)':
numbers.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 2; i <= _a.size(); i++)
      |                 ~~^~~~~~~~~~~~
numbers.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i = 1; i <= _a.size(); i++)
      |                 ~~^~~~~~~~~~~~
numbers.cpp:82:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |      if(i==_a.size() && p==2) continue;
      |         ~^~~~~~~~~~~

Subtask #1
21.25 / 25.0

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

Subtask #2
75.0 / 75.0

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