QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694196 | #6129. Magic Multiplication | ucup-team3294# | AC ✓ | 16ms | 5336kb | C++23 | 1.6kb | 2024-10-31 17:27:34 | 2024-10-31 17:27:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define PII pair<int,int>
#define x first
#define y second
void solve() {
int k1,k2;
cin>>k1>>k2;
string d;
cin>>d;
int n=d.size();
vector<int>a(n+2);
for(int i=1;i<=n;i++) a[i]=d[i-1]-'0';
// cout<<a[1]<<"\n\n";
vector<int>b(k1+1),c(k2+1);
for(int i=1;i<=9;i++){
b[1]=i;
int now=1,f=1;
for(int j=1;j<=k2;j++){
if(now>n){
f=0;
break;
}
if(a[now]%i==0){
c[j]=a[now]/i;
now++;
}else if(now==n||(a[now]*10+a[now+1])%i){
f=0;
break;
}else{
c[j]=(a[now]*10+a[now+1])/i;
if(c[j]>=10){
f=0;
break;
}
now+=2;
}
}
// cout<<i<<" "<<now<<" "<<c[1]<<c[2]<<"\n";
if(f==0) continue;
//cout<<i<<"\n";
for(int j=2;j<=k1;j++){
if(a[now]%c[1]==0) b[j]=a[now]/c[1];
else if(now==n||(a[now]*10+a[now+1])%c[1]){
f=0;break;
}else b[j]=(a[now]*10+a[now+1])/c[1];
if(b[j]>10){
f=0;
break;
}
// cout<<j<<" "<<b[j]<<"\n";
for(int k=1;k<=k2;k++){
int res=b[j]*c[k];
if(now>n){
f=0;
break;
}
if(res<=9&&res==a[now]) now++;
else if(now!=n&&res==a[now]*10+a[now+1]) now+=2;
else{
f=0;
break;
}
}
}
if(f==0||now!=n+1) continue;
for(int i=1;i<=k1;i++) cout<<b[i];
cout<<" ";
for(int i=1;i<=k2;i++) cout<<c[i];
cout<<"\n";
return;
}
cout<<"Impossible\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
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: 3616kb
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: 16ms
memory: 5336kb
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