QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330841#6129. Magic MultiplicationLainAC ✓19ms4984kbC++232.4kb2024-02-17 19:45:512024-02-17 19:45:52

Judging History

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

  • [2024-02-17 19:45:52]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:4984kb
  • [2024-02-17 19:45:51]
  • 提交

answer

// Very easy, and I am lazy
#include <bits/stdc++.h>
#define MAXN ((int) 2e5)
using namespace std;

int n, m, sLen;
char s[MAXN + 10];

int A[MAXN + 10], B[MAXN + 10], f[10][100];

// given a factor (1 ~ 9) of the product, calculate the other factor (0 ~ 9)
// x: the given factor
// now: the position of product in s
int gao(int x, int &now) {
    if (now > sLen) return -1;

    // product starts with 0, the other factor must be 0
    if (s[now] == '0') {
        now++;
        return 0;
    }

    // product not start with 0, check the multiplication table
    int t = s[now] - '0';
    if (f[x][t] > 0) {
        now++;
        return f[x][t];
    }

    t = t * 10 + (s[now + 1] - '0');
    if (now < sLen && f[x][t] > 0) {
        now += 2;
        return f[x][t];
    }

    return -1;
}

// enumerate a_1 = X
bool check(int X) {
    A[1] = X;

    // use a_1 to determine all elements in B
    int now = 1;
    for (int i = 1; i <= m; i++) {
        B[i] = gao(X, now);
        if (B[i] < 0) return false;
    }
    // problem requires that b_1 != 0
    if (B[1] == 0) return false;

    for (int i = 2; i <= n; i++) {
        // use b_1 to reversely calculate a_i
        // here b_1 != 0, so we can also use the gao() function
        A[i] = gao(B[1], now);
        if (A[i] < 0) return false;
        // check if the remaining product matches
        for (int j = 2; j <= m; j++) {
            int t = A[i] * B[j];
            int l = t >= 10 ? 2 : 1;
            for (int k = l - 1; k >= 0; k--) {
                if (now + k > sLen || s[now + k] - '0' != t % 10) return false;
                t /= 10;
            }
            now += l;
        }
    }

    // we must use up all characters in the string
    return now == sLen + 1;
}

void solve() {
    scanf("%d%d%s", &n, &m, s + 1);
    sLen = strlen(s + 1);

    // enumerate a_1
    for (int i = 1; i <= 9; i++) if (check(i)) {
        for (int j = 1; j <= n; j++) printf("%d", A[j]);
        printf(" ");
        for (int j = 1; j <= m; j++) printf("%d", B[j]);
        printf("\n");
        return;
    }
    printf("Impossible\n");
}

int main() {
    // pre-calculate the multiplication table
    for (int i = 1; i <= 9; i++) for (int j = 1; j <= 9; j++) f[i][i * j] = j;

    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}

詳細信息

Test #1:

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

input:

4
2 2
8101215
3 4
100000001000
2 2
80101215
3 4
1000000010000

output:

23 45
101 1000
Impossible
Impossible

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 19ms
memory: 4984kb

input:

1025
11 18
1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...

output:

Impossible
3583 5
161650357972 65354104569
597523997017 7693
Impossible
406723924695110 973937089831524
59331138450754 554
4 189401911962950
980565699171 84748728972992
Impossible
62155650672 4241405
9458752764004792353 8717596993614
Impossible
941952596 49242258343771276739
Impossible
64053045751 4...

result:

ok 1025 lines