結果
問題 | No.362 門松ナンバー |
ユーザー |
![]() |
提出日時 | 2016-04-18 09:42:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#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;}