2017年04月14日00時52分48秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

Google Code Jam 2017 Qualification Round B問題 - Tidy Numbers

Source

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 )$．

cLay（version 20170408-3）のコード

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月19日07時23分26秒
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)

ログイン：