Google Code Jam 2017 Qualification Round B問題
Problem Statement
(10進数において)左から右に見たときに,各桁の数字が減らない正整数を tidy と呼ぶ.
例えば,$1122334455, 7889$ は tidy だが,$213, 778899990$ は tidy でない.
$N$ 以下の整数の中で tidy な整数の最大値を求める問題.
色々な解き方があるが以下のようにやった.
$i$ 桁目の数字が $i+1$ 桁目の数字より大きいような $i$ を見つけてきて,
$i$ 桁目の数字を $1$ 減らし,$i+1$ 桁以降の数字を $9$ に置き換える.
これを繰り返して,$i$ が見つからなくなったらそれが答え.
この方法だと時間計算量は $O( (\log N)^2 )$.
C++に変換後のコードはこちら
{
int test = 0, TEST;
rd(TEST);
while(TEST--){
printf("Case #%d: ", ++test);
fprintf(stderr, "r=%d\n", TEST);
char N[20];
int i, j, len, fg;
rd(N);
len = strlen(N);
rep(i,len) N[i] -= '0';
for(;;){
fg = 0;
rep(i,1,len) if(N[i-1] > N[i]){
N[i-1]--;
N[i..len-1] = 9;
fg = 1;
break;
}
if(!fg) break;
}
if(N[0]==0){
len--;
N[0..len-1] = N[1..];
N[len] = '\0';
}
N[0..len-1] += '0';
wt(N);
}
}
Current time: 2024年04月26日07時32分54秒
Last modified: 2017年04月14日00時52分48秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2017 GCJ_2017_Qualification_Round
トップページに戻る
Logged in as: unknown user (not login)