結果
問題 | No.319 happy b1rthday 2 me |
ユーザー |
![]() |
提出日時 | 2021-03-31 01:48:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,454 bytes |
コンパイル時間 | 3,256 ms |
コンパイル使用メモリ | 208,928 KB |
最終ジャッジ日時 | 2025-01-20 01:00:15 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 RE * 1 |
other | AC * 18 RE * 11 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) begin(x),end(x)#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define mod 1000000007using ll=long long;const int INF=1000000000;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0},dy[]={0,1,0,-1};// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}struct IOSetup{IOSetup(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(12);}} iosetup;template<typename T>ostream &operator<<(ostream &os,const vector<T>&v){for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");return os;}template<typename T>istream &operator>>(istream &is,vector<T>&v){for(T &x:v)is>>x;return is;}vector<ll> p10{1ll,10ll,100ll,1000ll,10000ll,100000ll,1000000ll,10000000ll,100000000ll,1000000000ll,10000000000ll,100000000000ll,1000000000000ll,10000000000000ll,100000000000000ll,1000000000000000ll};// x, x+1bool len(ll x){string s=to_string(x);string t=to_string(x+1);if(s.back()=='1' and t[0]=='2') return true;return false;}pair<ll,ll> naive(int n){ll a=0,b=0;for(int i=1;i<=n;i++){string s=to_string(i);for(int j=0;j+1<(int)s.size();j++){if(s[j]=='1' and s[j+1]=='2') a++;}if(i+1<=n and len(i)) b++;}return make_pair(a,b);}pair<ll,ll> solve(ll n){ll ret=0;string s;for(ll m=n;m;m/=10) s.push_back('0'+m%10);reverse(ALL(s));// 桁DPint m=(int)s.size();vector<vector<vector<vector<ll>>>> dp(m+1,vector<vector<vector<ll>>>(2,vector<vector<ll>>(2,vector<ll>(100,0))));dp[0][0][0][0]=1;rep(i,m){int num=s[i]-'0';rep(j,2){rep(k,2){rep(l,80){rep(p,10){if(j==0 and p>num) continue;if(k==1 and p==2) dp[i+1][j or p<num][0][l+1]+=dp[i][j][k][l];else dp[i+1][j or p<num][p==1][l]+=dp[i][j][k][l];}}}}}rep(j,2)rep(k,2)rep(l,10){// if(dp[m][j][k][l]) cout<<j<<" aaa "<<k<<" "<<l<<" "<<dp[m][j][k][l]<<endl;ret+=dp[m][j][k][l]*l;}// cout<<ret<<" !"<<endl;ll unko=0;// lenif(n>=2) unko++;if(s.size()<=2){return make_pair(ret,unko);}int i;for(i=0;i+2<(int)s.size();i++){unko+=p10[i];}if(s[0]=='2'){assert(false);ll add=0;for(int i=1;i<(int)s.size()-1;i++) add+=10*add+s[i]-'0';add++;if(s.back()<'2'){add--;}unko+=max(0ll,add);return {ret,unko};}else if(s[0]<'2') return {ret,unko};else return {ret,unko+p10[i]};}signed main(){// ll n;cin>>n;// auto [a,b]=naive(n);// cout<<"N "<<a<<" "<<b<<endl;// tie(a,b)=solve(n);// cout<<"S "<<a<<" "<<b<<endl;ll a,b;cin>>a>>b;ll res=0;auto [x,y]=solve(b);res+=x+y;tie(x,y)=solve(a-1);res-=x+y;if(len(a-1)) res--;cout<<res<<endl;return 0;}