結果

問題 No.3658 Darumaka Number 2
コンテスト
ユーザー nekoti
提出日時 2026-08-30 15:23:03
言語 C
(gcc 15.3.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,485 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 106 ms
コンパイル使用メモリ 39,040 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-30 15:23:08
合計ジャッジ時間 2,437 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#define _DEBUG 0

#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#include<stdlib.h>
int main(void)
{
  int scan;//scanf警告用
  int ans=0;
  int i, j;
  
  char s[100010];scan=scanf("%s",s);int slen=strlen(s);
  
  bool can[10][100010]  ={false};//繰り下がっても5になる一覧
  // bool can5[100010]  ={false};//5になる一覧
  // bool can4[100010]  ={false};//5がダメなら4になる一覧
  bool cannot[100010]={false};//何もかもダメなので、繰り下げして5になる一覧
  //■左から右へいったん走査
  for(i=0; i<slen; i++)
  {
    bool ok=false;
    for(j=4;j<=9;j++)
    {
      if(j <= s[i]-'0')can[j][i]=true,ok=true;
    }
    if(!ok)cannot[i]=true;
    // if     (6 <= s[i]-'0')can6[i]=true;//繰り下がっても5可能
    // if     (5 <= s[i]-'0')can5[i]=true;//5可能
    // if     (4 <= s[i]-'0')can4[i]=true;//4可能
    // else                  cannot[i]=true;
  }
#if _DEBUG
  puts("■1");
  for(i=0; i<slen; i++)
  {
    printf("i=%d : 9(%d), 8(%d), 7(%d), 6(%d), 5(%d), 4(%d), !(%d)\n",i,can[9][i],can[8][i],can[7][i],can[6][i],can[5][i],can[4][i],cannot[i]);
  }
  puts("");
#endif


  //■右から左へ繰り下げ
  bool kurisage = false;
  int kurisageindex = -1;
  for(i=slen-1; 0<=i; i--)
  {
#if _DEBUG
printf("  kurisage = %d ->",kurisage);
#endif
    if(kurisage)
    {
      if     (can[6][i])kurisage=false,kurisageindex=i+1;//5より大きいので繰り下げても影響なし。そして繰り下げ完了
      else if(can[5][i])can[5][i]=false,kurisage=false,kurisageindex=i+1;//5を繰り下げて4にする。そして繰り下げ完了
      else              can[4][i]=false,cannot[i]=true;//繰り下げ継続
    }
    if(cannot[i])
    {
      //繰り下げ開始
      kurisage=true;
      kurisageindex=i;
    }
#if _DEBUG
printf(" %d (index = %d)\n",kurisage,kurisageindex);
#endif
  }
  
#if _DEBUG
  puts("■2");
  for(i=0; i<slen; i++)
  {
    printf("i=%d : 9(%d), 8(%d), 7(%d), 6(%d), 5(%d), 4(%d), !(%d)\n",i,can[9][i],can[8][i],can[7][i],can[6][i],can[5][i],can[4][i],cannot[i]);
  }
  puts("");
#endif
  
  //■出力
  if(!can[5][0]&&!can[4][0])
  {
    for(i=1; i<slen; i++)printf("5");puts("");
    return scan-scan;
  }
  for(i=0; i<slen; i++)
  {
    if(-1!=kurisageindex && kurisageindex<=i)printf("5");
    else
    {
      if     (can[5][i])printf("5");
      else if(can[4][i])printf("4");
      else              printf("5");
    }
  }
  return scan-scan;
}
0