結果
問題 | No.362 門松ナンバー |
ユーザー | yaoshimax |
提出日時 | 2016-04-18 09:42:13 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 14 ms / 3,000 ms |
コード長 | 2,752 bytes |
コンパイル時間 | 598 ms |
コンパイル使用メモリ | 72,644 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-10 23:59:02 |
合計ジャッジ時間 | 1,534 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
6,816 KB |
testcase_01 | AC | 4 ms
6,820 KB |
testcase_02 | AC | 4 ms
6,816 KB |
testcase_03 | AC | 3 ms
6,816 KB |
testcase_04 | AC | 3 ms
6,820 KB |
testcase_05 | AC | 6 ms
6,820 KB |
testcase_06 | AC | 10 ms
6,816 KB |
testcase_07 | AC | 6 ms
6,816 KB |
testcase_08 | AC | 8 ms
6,820 KB |
testcase_09 | AC | 12 ms
6,820 KB |
testcase_10 | AC | 14 ms
6,820 KB |
testcase_11 | AC | 14 ms
6,820 KB |
testcase_12 | AC | 14 ms
6,820 KB |
testcase_13 | AC | 14 ms
6,816 KB |
testcase_14 | AC | 14 ms
6,816 KB |
testcase_15 | AC | 14 ms
6,816 KB |
testcase_16 | AC | 14 ms
6,820 KB |
testcase_17 | AC | 13 ms
6,816 KB |
testcase_18 | AC | 14 ms
6,816 KB |
testcase_19 | AC | 8 ms
6,816 KB |
testcase_20 | AC | 14 ms
6,816 KB |
testcase_21 | AC | 3 ms
6,816 KB |
ソースコード
#include <iostream> #include <climits> #include <vector> #include <cstdio> #include <cstring> #include <set> using namespace std; bool kadomatsu(int x,int y, int z){ if( x==y || y==z || z==x ) return false; if( x<y && y>z ) return true; if( x>y && y<z) return true; return false; } long long func( long long X ){ long long ret = 0; long long dp[16][10][10][2]; for( int i=0; i<16; i++ ) for( int j=0; j<10; j++ ) for(int k=0 ;k<10; k++ )for(int l=0; l<2;l++){ dp[i][j][k][l]=0; } int offset=0; for( int i = 0 ; i < 1000; i++ ){ int x=i/100; int y=(i/10)%10; int z=i%10; int flag = 0; if( X%1000 < i ) flag =1; if( x==y || y==z || x==z ) continue; if( x<y&&y>z ){ if( x==0 ) offset++; if( X>=i ){ ret++; } dp[3][x][y][flag]++; } if( x>y&&y<z ){ if( x==0 ) offset++; if( X>=i ){ ret++; } dp[3][x][y][flag]++; } } long long curDigit=1000; int di=4; while(curDigit<= X){ int curD = (X/curDigit)%10; for( int i = 0; i <= 9 ; i++ ){ for( int j=0; j<=9; j++ ){ for( int k=0; k <=9; k++){ if(kadomatsu(i,j,k)){ if( i> curD ){ dp[di][i][j][1]+=dp[di-1][j][k][0]; dp[di][i][j][1]+=dp[di-1][j][k][1]; } else if( i< curD ){ dp[di][i][j][0]+=dp[di-1][j][k][0]; dp[di][i][j][0]+=dp[di-1][j][k][1]; } else{ dp[di][i][j][0]+=dp[di-1][j][k][0]; dp[di][i][j][1]+=dp[di-1][j][k][1]; } } } } } curDigit*=10; di++; } for( int d = 4; d <di; d++){ for( int i=1; i<=9; i++ ){ for( int j=0; j<=9; j++ ){ ret+=dp[d][i][j][0]; if( d!=di-1 ){ ret+=dp[d][i][j][1]; //cout << X<<": "<< d<<"-keta:" << ": "<<i <<", "<<j <<": "<<dp[d][i][j][0]<<"+"<<dp[3][i][j][1]<<endl; } //else //cout << X<<": "<< d<<"-keta:" << ": "<<i <<", "<<j <<": "<<dp[d][i][j][0]<<endl; } } //cout << d<<"-keta:" << ": "<< ret-offset<<endl; } return ret-offset; } int main(){ int T; cin >> T; for( int ti=0; ti<T; ti++ ){ long long K; cin >> K; long long left=101; long long right=4e13; while( left+1 <right ){ long long mid = (left+right)/2; // cout << mid << ": "<< func(mid)<<endl; if( func(mid) < K ) left=mid; else right=mid; } cout << right<<endl; } return 0; }