Submission #1419867
Source Code Expand
#define MYDEBUG
//
#include <bits/stdc++.h>
#ifdef MYDEBUG
#define dbp(x) cout<<#x<<": "<<x<<endl
#define dbp2(x,y) cout<<#x<<","<<#y<<": "<<x<<","<<y<<endl
#define dbp3(x,y,z) cout<<#x<<","<<#y<<","<<#z<<": "<<x<<","<<y<<","<<z<<endl
#define dbp4(w,x,y,z) cout<<#w<<","<<#x<<","<<#y<<","<<#z<<": "<<w<<","<<x<<","<<y<<","<<z<<endl
#define ifcin(x) std::ifstream cin(x)
#else
#define dbp(x)
#define dbp2(x,y)
#define dbp3(x,y,z)
#define dbp4(w,x,y,z)
#define ifcin(x)
#endif
#define ll long long
#define all(x) x.begin(), x.end()
#define rep(i, from, to) for(int i=from; i<to; ++i)
#define REP(i, from, to) for(int i=from; i<=to; ++i)
using namespace std;
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
out << "[";
size_t last = v.size() - 1;
for (size_t i = 0; i < v.size(); ++i) {
out << v[i];
if (i != last) {
out << ",";
}
}
out << "]";
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<vector<T> >& v) {
for (size_t i = 0; i < v.size(); ++i) {
out << v[i] << endl;
}
return out;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
out << "{" << p.first << "," << p.second << "}";
return out;
}
template<typename T>
inline string toString(const T &a) {
ostringstream oss;
oss << a;
return oss.str();
}
//桁DP: [i桁決めた][N未満確定フラグ] + 必要なら[条件]
//今回: [i桁決めた][N未満確定フラグ][4または9を含む]
//dp[i][j][k]: 状態(i,j,k)を満たすものの総数
//i -> i+1
//j -> 1 (最初から1 or 試した値がNのi+1桁目未満)
//k -> 1 (最初から1 or 試した値が4または9)
ll A, B;
string a, b;
ll dp[32][2][2];
ll doDP(string s) {
memset(dp, 0, sizeof(dp));
const int L = s.size();
dp[0][0][0] = 1; //出発地点は1以上でないと0を足してしまう
rep(i,0,L)
{
const int D = s[i] - '0'; //対応するNのi桁目の数字
REP(j,0,1)
{
//if j==0 -> 0 <= d <= D(制限がつく)
//if j==1 -> 0 <= d <= 9(制限なし)
REP(k,0,1)
{
for (int d = 0; d <= (j == 0 ? D : 9); ++d) {
int ni, nj, nk;
ni = i + 1; //iが最大L-1より, dp[L][][]まで埋まることに注意
nj = j || (d < D);
nk = k || d == 4 || d == 9;
dp[ni][nj][nk] += dp[i][j][k]; //次の遷移先に配る
}
}
}
}
return dp[L][0][1] + dp[L][1][1];
}
void solve() {
cin >> A >> B;
a = toString(A - 1);
b = toString(B);
cout << doDP(b) - doDP(a) << endl;
}
int main() {
solve();
}
Submission Info
Submission Time |
|
Task |
D - 禁止された数字 |
User |
LitMc |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2617 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask0_sample04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask0_sample04.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
1 ms |
256 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
1 ms |
256 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
1 ms |
256 KB |
subtask1_10.txt |
AC |
1 ms |
256 KB |
subtask1_11.txt |
AC |
1 ms |
256 KB |
subtask1_12.txt |
AC |
1 ms |
256 KB |
subtask1_13.txt |
AC |
1 ms |
256 KB |
subtask2_01.txt |
AC |
1 ms |
256 KB |
subtask2_02.txt |
AC |
1 ms |
256 KB |
subtask2_03.txt |
AC |
1 ms |
256 KB |
subtask2_04.txt |
AC |
1 ms |
256 KB |
subtask2_05.txt |
AC |
1 ms |
256 KB |
subtask2_06.txt |
AC |
1 ms |
256 KB |
subtask2_07.txt |
AC |
1 ms |
256 KB |
subtask2_08.txt |
AC |
1 ms |
256 KB |
subtask2_09.txt |
AC |
1 ms |
256 KB |
subtask2_10.txt |
AC |
1 ms |
256 KB |
subtask2_11.txt |
AC |
1 ms |
256 KB |
subtask2_12.txt |
AC |
1 ms |
256 KB |
subtask2_13.txt |
AC |
1 ms |
256 KB |
subtask2_14.txt |
AC |
1 ms |
256 KB |
subtask2_15.txt |
AC |
1 ms |
256 KB |
subtask2_16.txt |
AC |
1 ms |
256 KB |
subtask2_17.txt |
AC |
1 ms |
256 KB |
subtask2_18.txt |
AC |
1 ms |
256 KB |
subtask2_19.txt |
AC |
1 ms |
256 KB |
subtask2_20.txt |
AC |
1 ms |
256 KB |
subtask2_21.txt |
AC |
1 ms |
256 KB |
subtask2_22.txt |
AC |
1 ms |
256 KB |