QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#695000 | #6129. Magic Multiplication | proven# | AC ✓ | 24ms | 7120kb | C++20 | 3.3kb | 2024-10-31 19:06:40 | 2024-10-31 19:06:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
void solve() {
int n, m;
cin >> n >> m;
string c; cin >> c;
int len = (int)c.size();
vector<int> C(len + 1);
for(int i = 1;i <= len;i++) {
C[i] = c[i - 1] - '0';
}
auto check = [&] (int l, int r, int x) {
int tmp = 0;
for(int i = l;i <= r;i++) tmp = tmp * 10 + C[i];
return x == tmp;
};
auto calc = [&] (int x) {
array<vector<int>, 2> res{};
vector<int> A(n + 1), B(m + 1);
A[1] = x;
int i = 1;
for(int j = 1;j <= m;j++) {
if(i > len) return res;
int tmp = C[i];
if(tmp < x) {
if(tmp == 0) {
B[j] = 0;
i++;
continue;
}
if(i == len) return res;
tmp = tmp * 10 + C[i + 1];
if(tmp % x) return res;
B[j] = tmp / x;
i += 2;
}
else {
if(tmp % x) return res;
B[j] = tmp / x;
i++;
}
}
// for(int j = 1;j <= m;j++) cout << B[j];
// cout << endl;
// cout << i << endl;
for(int k = 2;k <= n;k++) {
// cout << i << endl;
if(i > len) return res;
int tmp = C[i];
if(tmp < B[1]) {
if(tmp == 0) {
A[k] = 0;
i++;
}
else {
if(i == len) return res;
tmp = tmp * 10 + C[i + 1];
if(tmp % B[1]) return res;
A[k] = tmp / B[1];
// cout << tmp << " " << x << " " << A[k] << endl;
i += 2;
}
}
else {
if(tmp % B[1]) return res;
A[k] = tmp / B[1];
i++;
}
// cout << "k = " << k << " " << A[k] << " " << i << endl;
for(int j = 2;j <= m;j++) {
if(i > len) return res;
int now = B[j] * A[k];
// cout << "now = " << now << " " << i << endl;
if(now < 10) {
if(check(i, i, now)) i++;
else return res;
}
else {
if(i == len) return res;
if(check(i, i + 1, now)) i += 2;
else return res;
}
}
// cout << "i = " << i << "number = " << A[k] << endl;
}
if(i <= len) return res;
res[0] = A, res[1] = B;
return res;
};
// calc(1);
for(int i = 1;i <= 9;i++) {
auto ans = calc(i);
if((int)ans[0].size() > 0) {
for(int j = 1;j <= n;j++) cout << ans[0][j];
cout << " ";
for(int j = 1;j <= m;j++) cout << ans[1][j];
cout << endl;
return;
}
}
cout << "Impossible" << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
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: 24ms
memory: 7120kb
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