QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91974 | #6129. Magic Multiplication | sycheng# | AC ✓ | 9ms | 3560kb | C++14 | 3.1kb | 2023-03-30 02:06:11 | 2023-03-30 02:06:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
void work() {
cin >> n >> m;
cin >> s;
int len = s.size();
if(1LL * n * m > len){
cout << "Impossible" << '\n';
return;
}
int st = (n != 1);
for(int i = st; i <= 9; i ++) {
string B = ""; int now = 0;
bool flag = 1;
for(int j = 1; j <= m; j ++) {
if(now == len){
flag = 0;
break;
}
int v = s[now] - '0'; ++now;
if(i == 0 && v != 0){
flag = 0;
break;
}
if(v == 0){
if(j == 1 && m != 1){
flag = 0;
break;
}
B += '0';
continue;
}
if(now == len && v < i){
flag = 0;
break;
}
if(v < i) v = v * 10 + s[now] - '0', ++now;
if(v % i != 0){
flag = 0;
break;
}
B += char(v / i + '0');
}
string A = "";
A += char(i + '0');
if(flag && n == 1){
if(now == len){
cout << A << ' ' << B << '\n';
return;
}
continue;
}
if(flag && now < len){
for(int j = 2; j <= n; ++j){
int fow = -1;
for(int t = 0; t < m; ++t){
if(now == len){
flag = 0;
break;
}
int x = B[t] - '0';
int v = s[now] - '0'; ++now;
if(x == 0 && v != 0){
flag = 0;
break;
}
if(v == 0){
if(fow != -1 && fow != 0 && x!= 0){
flag = 0;
break;
}
if(x != 0) fow = 0;
continue;
}
if(now == len && v < x){
flag = 0;
break;
}
if(v < x) v = v * 10 + s[now] - '0', ++now;
if(v % x != 0){
flag = 0;
break;
}
if(fow != -1 && fow != v / x){
flag = 0;
break;
}
fow = v / x;
}
if(!flag) break;
if(fow == -1) fow = 0;
A += char(fow + '0');
}
if(flag && now == len){
cout << A << ' ' << B << '\n';
return;
}
}
}
cout << "Impossible" << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int Case;
cin >> Case;
while(Case --) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 9ms
memory: 3560kb
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