QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#330841 | #6129. Magic Multiplication | Lain | AC ✓ | 19ms | 4984kb | C++23 | 2.4kb | 2024-02-17 19:45:51 | 2024-02-17 19:45:52 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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