QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190673 | #6129. Magic Multiplication | Zhou_JK | AC ✓ | 15ms | 5688kb | C++23 | 1.8kb | 2023-09-29 12:23:42 | 2023-09-29 12:23:42 |
Judging History
answer
#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n,m,len;
int c[N];
int a[N],b[N];
bool check(int v)
{
int cur=1;
a[1]=v;
for(int i=1;i<=m;i++)
{
if(cur<=len&&c[cur]%a[1]==0) b[i]=c[cur]/a[1],cur++;
else if(cur+1<=len&&(c[cur]*10+c[cur+1])%a[1]==0&&(c[cur]*10+c[cur+1])/a[1]<=9) b[i]=(c[cur]*10+c[cur+1])/a[1],cur+=2;
else return false;
// cerr<<"b"<<b[i]<<"\n";
}
for(int i=2;i<=n;i++)
{
a[i]=-1;
for(int j=1;j<=m;j++)
if(b[j]!=0)
{
int val=-1;
if(cur<=len&&c[cur]%b[j]==0) val=c[cur]/b[j],cur++;
else if(cur+1<=len&&(c[cur]*10+c[cur+1])%b[j]==0&&(c[cur]*10+c[cur+1])/b[j]<=9) val=(c[cur]*10+c[cur+1])/b[j],cur+=2;
else return false;
if(a[i]!=-1&&a[i]!=val) return false;
else a[i]=val;
}
else
{
if(cur<=len&&c[cur]==0) cur++;
else return false;
}
}
return cur==len+1;
}
void solve()
{
cin>>n>>m;
string str;
cin>>str;
len=str.size();
for(int i=1;i<=len;i++)
c[i]=str[i-1]-'0';
// check(2);
for(int v=1;v<=9;v++)
if(check(v))
{
for(int i=1;i<=n;i++)
cout<<a[i];
cout<<" ";
for(int i=1;i<=m;i++)
cout<<b[i];
cout<<"\n";
return;
}
cout<<"Impossible\n";
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
/*
1
1 7
8154819274518
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 15ms
memory: 5688kb
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