結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー tnakao0123
提出日時 2025-11-04 18:58:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,603 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 45,280 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-04 18:58:52
合計ジャッジ時間 3,954 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:54:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |   scanf("%d", &tn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3316.cc:  No.3316 Make 81181819 with only 0,1,or 8 - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int T = 81181819;
const int MAX_D = 8;
const int MAX_K = 9 + 4;
const int INF = 1 << 30;

/* typedef */

/* global variables */

int ds[MAX_D + 1];
int mink;
int v1[MAX_D], v8[MAX_D], w1[MAX_D], w8[MAX_D];
int xvs[MAX_D][MAX_K];

/* subroutines */

void rec(int u, int d, int co = 0, int k = 0) {
  if (u >= d) {
    if (mink > k) {
      mink = k;
      copy(v1, v1 + d, w1);
      copy(v8, v8 + d, w8);
    }
    return;
  }

  int du = ds[u] - co;
  for (int c8 = 0; c8 < 5; c8++) {
    int c1 = (du + 40 - 8 * c8) % 10;
    int co1 = (c1 + 8 * c8) / 10;
    if (ds[u + 1] >= co1) {
      v1[u] = c1, v8[u] = c8;
      rec(u + 1, d, co1, max(k, c1 + c8));
    }
  }
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n;
    scanf("%d", &n);

    int m = T - n, d = 0;
    while (m > 0) ds[d++] = m % 10, m /= 10;
    ds[d] = 0;
    //for (int i = 0; i < d; i++) printf("%d", ds[i]); putchar('\n');

    mink = INF;
    rec(0, d, 0, 0);
    //printf(" mink=%d\n", mink);

    for (int i = 0; i < d; i++) {
      auto &xv = xvs[i];
      int c0 = mink - (w1[i] + w8[i]);
      fill(xv, xv + c0, 0);
      fill(xv + c0, xv + c0 + w1[i], 1);
      fill(xv + c0 + w1[i], xv + mink, 8);
    }

    printf("%d\n", mink);
    for (int i = 0; i < mink; i++) {
      int pi = 0;
      for (int j = d - 1; j >= 0; j--) pi = pi * 10 + xvs[j][i];
      printf("%d\n", pi);
    }
  }

  return 0;
}
0