Submission #163664
Source Code Expand
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <functional>
#include <cmath>
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2((x),0,(to))
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll fnc1(ll n){
string sn = to_string(n);
int cn=sz(sn);
vector<vector<ll> > p(cn+1, vector<ll>(2,0));
p[0][0]=1;
rep(i, cn){
rep(j, 10){
if(j==4 || j==9) continue;
if(j < sn[i] -'0') p[i+1][1] += p[i][0] + p[i][1];
else if(j== sn[i] -'0'){
p[i+1][0] += p[i][0]; p[i+1][1] += p[i][1];
}
else p[i+1][1] += p[i][1];
}
}
// rep(i,cn+1) printf("%7lld ",p[i][0]);puts("");
// rep(i,cn+1) printf("%7lld ",p[i][1]);puts("");
// printf("rtn %lld: %lld\n",n,p[cn][0]+p[cn][1]);
return p[cn][0]+p[cn][1];
}
ll fnc2(ll n){
string sn = to_string(n), ws;
int tbl[]={0,1,2,3,4,4,5,6,7,7};
int cn=sz(sn), sw=0;
rep(i, cn){
if(sw==1) sn[i]='8';
else if(sn[i]=='4') sn[i]='3', sw=1;
else if(sn[i]=='9') sn[i]='8', sw=1;
}
rep(i,cn) ws += char(tbl[(sn[i]-'0')]+'0');
ll rtn=0;
rep(i,cn){
rtn *= 8;
rtn += ws[i]-'0';
}
return rtn + 1;
}
int main()
{
ll a,b, ans=0;
cin >>a >>b;
ans = b - a +1 - fnc1(b) + fnc1(a-1);
cout << ans << endl;
// ans = b - a +1 - fnc2(b) + fnc2(a-1);
// cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 禁止された数字 |
User |
damekamo |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
1625 Byte |
Status |
AC |
Exec Time |
24 ms |
Memory |
924 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 |
23 ms |
792 KB |
subtask0_sample02.txt |
AC |
22 ms |
808 KB |
subtask0_sample03.txt |
AC |
20 ms |
792 KB |
subtask0_sample04.txt |
AC |
22 ms |
916 KB |
subtask1_01.txt |
AC |
21 ms |
924 KB |
subtask1_02.txt |
AC |
20 ms |
740 KB |
subtask1_03.txt |
AC |
23 ms |
812 KB |
subtask1_04.txt |
AC |
23 ms |
792 KB |
subtask1_05.txt |
AC |
21 ms |
912 KB |
subtask1_06.txt |
AC |
24 ms |
796 KB |
subtask1_07.txt |
AC |
22 ms |
792 KB |
subtask1_08.txt |
AC |
22 ms |
924 KB |
subtask1_09.txt |
AC |
21 ms |
792 KB |
subtask1_10.txt |
AC |
22 ms |
792 KB |
subtask1_11.txt |
AC |
23 ms |
788 KB |
subtask1_12.txt |
AC |
22 ms |
792 KB |
subtask1_13.txt |
AC |
22 ms |
796 KB |
subtask2_01.txt |
AC |
22 ms |
796 KB |
subtask2_02.txt |
AC |
20 ms |
912 KB |
subtask2_03.txt |
AC |
23 ms |
800 KB |
subtask2_04.txt |
AC |
23 ms |
796 KB |
subtask2_05.txt |
AC |
22 ms |
716 KB |
subtask2_06.txt |
AC |
20 ms |
920 KB |
subtask2_07.txt |
AC |
19 ms |
912 KB |
subtask2_08.txt |
AC |
19 ms |
920 KB |
subtask2_09.txt |
AC |
21 ms |
916 KB |
subtask2_10.txt |
AC |
22 ms |
796 KB |
subtask2_11.txt |
AC |
22 ms |
916 KB |
subtask2_12.txt |
AC |
23 ms |
804 KB |
subtask2_13.txt |
AC |
22 ms |
796 KB |
subtask2_14.txt |
AC |
23 ms |
920 KB |
subtask2_15.txt |
AC |
24 ms |
896 KB |
subtask2_16.txt |
AC |
22 ms |
796 KB |
subtask2_17.txt |
AC |
22 ms |
920 KB |
subtask2_18.txt |
AC |
23 ms |
796 KB |
subtask2_19.txt |
AC |
24 ms |
800 KB |
subtask2_20.txt |
AC |
22 ms |
788 KB |
subtask2_21.txt |
AC |
21 ms |
920 KB |
subtask2_22.txt |
AC |
24 ms |
800 KB |