結果
問題 | No.319 happy b1rthday 2 me |
ユーザー |
![]() |
提出日時 | 2021-03-31 01:35:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,466 bytes |
コンパイル時間 | 3,219 ms |
コンパイル使用メモリ | 206,492 KB |
最終ジャッジ日時 | 2025-01-20 00:59:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 18 WA * 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){ll last=-1;while(x){last=x%10;x/=10;}return (x%10==1 and last==1);}ll naive(int n){string p="???";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(p.back()=='1' and s[0]=='2'){// cout<<"! "<<p<<", "<<s<<endl;b++;}p=s;}// cout<<a<<" ! "<<endl;return a+b;}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;// lenif(n>=2) ret++;if(s.size()<=1){return ret;}int i;for(i=0;i+2<(int)s.size();i++){ret+=p10[i];}if(s[0]=='2'){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--;ret+=max(0ll,add);return ret;}else if(s[0]<'2') return ret;else return ret+p10[i];}signed main(){// ll n;cin>>n;// ll H=solve(n);// cout<<H<<" solve"<<endl;// ll h=naive(n);// cout<<h<<" naive"<<endl;// return 0;ll a,b;cin>>a>>b;ll p=solve(b);ll m=solve(a-1);// cout<<p<<" - "<<m<<endl;ll res=solve(b)-solve(a-1);if(len(a-1)) res--;cout<<res<<endl;return 0;}