QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#220484#6300. Best Carry Player 2ucup-team1883#TL 0ms1364kbC++171.4kb2023-10-20 14:27:342023-10-20 14:27:35

Judging History

你现在查看的是最新测评结果

  • [2023-10-20 14:27:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:1364kb
  • [2023-10-20 14:27:34]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define LOG(f...) fprintf(stderr, f)

char s[25], t[25];

bool DFS(int i, int ncar, int n9) {
  if (i < 0) return ncar == 0;
  if (ncar < 0 || i + 1 + n9 < ncar) return false;
  for (t[i] = 0; t[i] <= 9; ++t[i]) {
    // LOG("DFS %d %d %d => %d (s %d)\n", i, ncar, n9, t[i], s[i]);
    int dig = s[i] + t[i];
    int ncar_ = ncar - (dig > 9 ? n9 + 1 : 0);
    dig %= 10;
    int n9_ = dig == 9 ? n9 + 1 : 0;
    if (DFS(i - 1, ncar_, n9_)) return true;
  }
  return false;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    memset(s, 0, sizeof(s)); memset(t, 0, sizeof(t));
    int req;
    scanf("%s%d", s, &req);
    int len = strlen(s);
    reverse(s, s + len);
    for (int i = 0; i < len; ++i)
      s[i] -= '0';
    if (req == 0) {
      for (int i = 0; i < len + 1; ++i)
        if (s[i] != 9) {
          putchar('1');
          for (int j = 0; j < i; ++j)
            putchar('0');
          break;
        }
      putchar('\n');
      continue;
    }
    DFS(24, req, 0);
    int lent = 0;
    for (int i = 0; i < 25; ++i)
      if (t[i]) lent = i + 1;
    // for (int i = 0; i < 25; ++i)
    //   printf("%d ", int(t[i]));
    // puts("");
    reverse(t, t + lent);
    for (int i = 0; i < lent; ++i)
      t[i] += '0', putchar(t[i]);
    putchar('\n');
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 1364kb

input:

4
12345678 0
12345678 5
12345678 18
990099 5

output:

1
54322
999999999987654322
9910

result:

ok 4 lines

Test #2:

score: -100
Time Limit Exceeded

input:

21
999990000099999 0
999990000099999 1
999990000099999 2
999990000099999 3
999990000099999 4
999990000099999 5
999990000099999 6
999990000099999 7
999990000099999 8
999990000099999 9
999990000099999 10
999990000099999 11
999990000099999 12
999990000099999 13
999990000099999 14
999990000099999 15
999...

output:


result: