제출 #255611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255611		Saboon	Palindrome-Free Numbers (BOI13_numbers)	C++14	100 / 100	1 ms	384 KiB

numbers

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e5 + 10;

ll dp[20][12][12];

ll get(string s){
	if (s.size() == 1)
		return stoi(s) + 1;
	int n = s.size();
	ll ret = 0;
	for (int i = 1; i <= n-1; i++)
		ret += 9ll * dp[i][10][1];
	ret ++;
	for (int i = 0; i < n; i++){
		for (char c = '0'; c < s[i]; c++){
			if (i == 0 and c == '0')
				continue;
			if (i > 0 and c == s[i-1])
				continue;
			if (i > 1 and c == s[i-2])
				continue;
			if (i == 0)
				ret += dp[n-i][10][(int)(c-'0')];
			else
				ret += dp[n-i+1][(int)(s[i-1]-'0')][(int)(c-'0')];
		}
		
		if (i > 0 and s[i] == s[i-1])
			break;
		if (i > 1 and s[i] == s[i-2])
			break;
		if (i == n-1)
			ret ++;
	}
	return ret;
}

bool check(string s){
	for (int i = 1; i < s.size(); i++)
		if (s[i] == s[i-1])
			return false;
	for (int i = 2; i < s.size(); i++)
		if (s[i] == s[i-2])
			return false;
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	for (int i = 0; i <= 9; i++)
		dp[1][10][i] = 1;
	for (int a = 0; a < 10; a++)
		for (int b = 0; b < 10; b++)
			if (a != b)
				dp[2][a][b] = 1;
	for (int len = 2; len <= 19; len++){
		for (int a = 0; a < 10; a++){
			for (int b = 0; b < 10; b++){
				if (a == b)
					continue;
				for (int c = 0; c < 10; c++){
					if (a == b or b == c)
						continue;
					dp[len][a][b] += dp[len-1][c][a];
				}
			}
		}
		for (int b = 0; b < 10; b++){
			for (int c = 0; c < 10; c++){
				if (b == c)
					continue;
				dp[len][10][b] += dp[len][b][c];
			}
		}
	}
	ll l, r;
	cin >> l >> r;
	string a = to_string(r), b = to_string(l-1);
	if (l == 0)
		return cout << get(a) << endl, 0;
	cout << get(a) - get(b) << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

numbers.cpp: In function 'bool check(std::__cxx11::string)':
numbers.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++)
                  ~~^~~~~~~~~~
numbers.cpp:47:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 2; i < s.size(); i++)
                  ~~^~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 75 / 75