結果
問題 |
No.319 happy b1rthday 2 me
|
ユーザー |
|
提出日時 | 2017-01-04 17:52:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,834 bytes |
コンパイル時間 | 1,892 ms |
コンパイル使用メモリ | 180,268 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 19:31:01 |
合計ジャッジ時間 | 3,150 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< vvi > vvvi; typedef vector< vvvi > vvvvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef vector< vvl > vvvl; typedef vector< vvvl > vvvvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; string A, B; void init(){ cin >> A >> B; } ll dp1( const string &s, int cover ){ vvvvl dp( s.size() + 1, vvvl( 2, vvl( 2, vl( 6 + 1 ) ) ) ); dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1; // len, less, tailing 1, count of 12s for( int i = 0; i < s.size(); ++i ){ for( int j = 0; j < 2; ++j ){ for( int k = 0; k < 2; ++k ){ for( int l = 0; l < 7; ++l ){ for( int d = 0; d <= ( j ? 9 : s[ i ] - '0' ); ++d ){ if( k and d == 2 ){ dp[ i + 1 ][ j | d < s[ i ] - '0' ][ 0 ][ l + 1 ] += dp[ i ][ j ][ k ][ l ]; } else{ dp[ i + 1 ][ j | d < s[ i ] - '0' ][ d == 1 ][ l ] += dp[ i ][ j ][ k ][ l ]; } } } } } } ll res = 0; for( int j = 0; j < 2; ++j ){ if( not j and not cover ) continue; // not less and not supposed to be covered for( int k = 0; k < 2; ++k ){ for( int l = 1; l < 7; ++l ){ res += dp[ s.size() ][ j ][ k ][ l ] * l; } } } return res; } // how many 12s in string format of each 0, 1, 2, .., s ll dp2( const string &s, int cover ){ vvvvl dp( s.size() + 1, vvvl( 2, vvl( 2, vl( 2 ) ) ) ); dp[ 0 ][ 0 ][ 0 ][ 0 ] = 1; // len, less, not zero, tailing 1 for( int i = 0; i < s.size(); ++i ){ for( int j = 0; j < 2; ++j ){ for( int k = 0; k < 2; ++k ){ for( int l = 0; l < 2; ++l ){ for( int d = 0; d <= ( j ? 9 : s[ i ] - '0' ); ++d ){ if( not k ){ if( not ( d == 0 or d == 2 ) ) continue; } dp[ i + 1 ][ j | d < s[ i ] - '0' ][ k | d != 0 ][ d == 1 ] += dp[ i ][ j ][ k ][ l ]; } } } } } ll res = 0; for( int j = 0; j < 2; ++j ){ if( not j and not cover ) continue; res += dp[ s.size() ][ j ][ 1 ][ 1 ]; } return res; } // how many values of format 2....1 in range [ 0, s ] void preprocess(){ } void solve(){ ll ans = dp1( B, 1 ) - dp1( A, 0 ) + dp2( B, 0 ) - dp2( A, 0 ); if( A == "1" and B != "1" ){ ++ans; } cout << ans << endl; } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }