結果

問題 No.362 門松ナンバー
ユーザー yaoshimax
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0