QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#144184 | #6129. Magic Multiplication | PhantomThreshold# | AC ✓ | 57ms | 41824kb | C++20 | 2.2kb | 2023-08-21 15:50:28 | 2023-08-21 15:50:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
string s;
cin>>s;
vector<pair<string,string>> ans;
string A(n,'0'),B(m,'0');
function<void(int,int,int)> dfs=[&](int x,int y,int p)
{
if(x==n)
{
if(p+0u==s.length())
ans.emplace_back(A,B);
return;
}
if(y==m)return dfs(x+1,0,p);
if(x==0 and y==0)
{
for(A[x]='1';A[x]<='9';A[x]++)
{
for(B[y]='1';B[y]<='9';B[y]++)
{
int res=(A[x]-'0')*(B[y]-'0');
if(res>=10)
{
if(s.length()<p+2u)continue;
if(res/10==s[p]-'0' and res%10==s[p+1]-'0')
{
dfs(x,y+1,p+2);
}
}
else
{
if(s.length()<p+1u)continue;
if(res==s[p]-'0')
{
dfs(x,y+1,p+1);
}
}
}
}
}
else if(x==0)
{
for(B[y]='0';B[y]<='9';B[y]++)
{
int res=(A[x]-'0')*(B[y]-'0');
if(res>=10)
{
if(s.length()<p+2u)continue;
if(res/10==s[p]-'0' and res%10==s[p+1]-'0')
{
dfs(x,y+1,p+2);
}
}
else
{
if(s.length()<p+1u)continue;
if(res==s[p]-'0')
{
dfs(x,y+1,p+1);
}
}
}
}
else if(y==0)
{
for(A[x]='0';A[x]<='9';A[x]++)
{
int res=(A[x]-'0')*(B[y]-'0');
if(res>=10)
{
if(s.length()<p+2u)continue;
if(res/10==s[p]-'0' and res%10==s[p+1]-'0')
{
dfs(x,y+1,p+2);
}
}
else
{
if(s.length()<p+1u)continue;
if(res==s[p]-'0')
{
dfs(x,y+1,p+1);
}
}
}
}
else
{
int res=(A[x]-'0')*(B[y]-'0');
if(res>=10)
{
if(s.length()<p+2u)return;
if(res/10==s[p]-'0' and res%10==s[p+1]-'0')
{
dfs(x,y+1,p+2);
}
}
else
{
if(s.length()<p+1u)return;
if(res==s[p]-'0')
{
dfs(x,y+1,p+1);
}
}
}
};
dfs(0,0,0);
if(ans.size()==0u)cout<<"Impossible\n";
else
{
auto [a,b]=*min_element(ans.begin(),ans.end());
cout<<a<<' '<<b<<"\n";
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3464kb
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: 57ms
memory: 41824kb
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