QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222533 | #6129. Magic Multiplication | ucup-team1001# | TL | 0ms | 3760kb | C++20 | 2.3kb | 2023-10-21 17:32:01 | 2023-10-21 17:32:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define irep(i,l,r) for(int i = (l); (i) <= (r); ++ (i))
#define ll long long
inline ll read(){
ll s = 0;
bool w = 0;
char ch = getchar();
while(! isdigit(ch)){
if(ch == '-')w = 1;
ch = getchar();
}
while(isdigit(ch)){
s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
}
return w ? -s : s;
}
string s;
int len;
int n,m;
vector<int>A,B;
vector<vector<int>>AA,BB;
void work(){
A.resize(n);
//cerr << A.size() << endl;
//cout << A[0] << endl ;
//irep(i, 0, m -1)cout << B[i];
//cout << endl;
string opt[10];
int optlen[10];
for(int c = 0; c < 10; ++ c){
for(int i = 0; i < m; ++ i){
int val = c * B[i];
if(val < 10)opt[c] += val + '0';
else opt[c] += (val / 10) + '0', opt[c] += (val % 10) + '0';
}
optlen[c] = opt[c].length();
// cout << opt[c] << endl;
}
int match = 0, pos = 0, ok = 0;
for(int i = 0; i < n; ++ i){
int pas = 0;
irep(ch, 0, 9){
int fl = 0;
if(pos + optlen[ch] > len)continue;
if(i == 0 && ch == 0)continue;
for(int p = 0; p < optlen[ch]; ++ p){
if(opt[ch][p] != s[pos + p]){
fl = 1;
break;
}
}
if(fl == 0){
pos = optlen[ch] + pos;
A[i] = ch;
fl = 1, pas = 1;
break;
}
}
if(i == n - 1 && pos != len)return;
if(pas == 0)return;
}
AA.push_back(A);
BB.push_back(B);
}
void dfs(int x, int a0, int cur){
if(x == m){
if(B[0])work();
return;
}
int op1 = s[cur] - '0', op2 = (s[cur] - '0') * 10 + s[cur + 1] - '0';
if(op1 % a0 == 0){
B[x] = op1 / a0;
dfs(x + 1, a0, cur + 1);
}
if(op2 % a0 == 0 && op2 / a0 < 10 && op2 != 0){
B[x] = op2 / a0;
dfs(x + 1, a0, cur + 2);
}
}
void solve(){
n = read(), m = read();
A.resize(n);
B.resize(m);
AA.clear();
BB.clear();
cin >> s;
len = s.length();
if(n * m > s.length()){
puts("Impossible");
return;
}
A.push_back(0);
for(int a0 = 1; a0 < 10; ++ a0){
A[0] = a0;
B.resize(m);
dfs(0, a0, 0);
}
if(AA.size() == 0){
puts("Impossible");
return;
}else{
for(int x : AA[0])printf("%d", x);
putchar(' ');
for(int x : BB[0])printf("%d",x);
putchar('\n');
}
}
int main(){
int T = read();
while(T --){
solve();
//cout << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
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: -100
Time Limit Exceeded
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...