QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492771 | #6129. Magic Multiplication | priudy | WA | 7ms | 4064kb | C++14 | 2.1kb | 2024-07-26 15:58:18 | 2024-07-26 15:58:18 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110005;
int n,m;
string a,b,s;
string ansa,ansb;
vector<pair<int,int> > nums;
bool check(pair<int,int> it){
a=b="";
a+=it.first+'0',b+=it.second+'0';
int k=0;
int u=0;
for(int p=1;p<s.length()-1;p++){
if(k>m-1)k=0,u=0;
if(b.length()==m){
if(b[k]=='0'){
k++;
}
else if((s[p]-'0') % (b[k]-'0') ==0){
// cout<<((s[p]-'0')/(b[k]-'0'))<<endl;
if(u==0)a+=((s[p]-'0')/(b[k]-'0'))+'0',u=1;
k++;
}
else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') ) == 0 ){
if(u==0)a+=( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )+'0',u=1;
p++;k++;
}
else return false;
}
else {
if(s[p]=='0'){
b+='0';
}
else if((s[p]-'0')%it.first==0){
b+=((s[p]-'0')/it.first)+'0';
}
else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) %it.first) == 0 ){
b+= ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)+'0';
p++;
}
else return false;
}
// cout<<a<<" "<<b<<endl;
}
if(a.length()!=n)return false;
return true;
}
void solve(){
cin>>n>>m;ansa=ansb="";
cin>>s;
if(s.length()<n*m||s.length()>n*m*2){
cout<<"Impossible"<<endl;
return;
}
if(s.length()==1){
for(int i=0;i<=9;i++){
for(int j=1;j<=9;j++){
if(i*j==s[0]-'0'){
cout<<i<<" "<<j<<endl;
return;
}
}
}
}
else {
s+='0';
int s1=s[0]-'0',s2=10*(s[0]-'0')+s[1]-'0';
nums.clear();
for(int i=0;i<=9;i++){
for(int j=1;j<=9;j++){
if(i*j==s1){
nums.emplace_back(make_pair(i,j));
}
}
}
for(auto it:nums){
if(check(it)){
if(ansa==""){
ansa=a,ansb=b;
}
else {
if(ansa>a){
ansa=a,ansb=b;
}
else if(ansa==ansb&&ansb>b){
ansa=a,ansb=b;
}
}
}
}
}
if(ansa!=""){
cout<<ansa<<" "<<ansb<<endl;
}
else cout<<"Impossible"<<endl;
return;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
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: -100
Wrong Answer
time: 7ms
memory: 4064kb
input:
1025 11 18 1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...
output:
Impossible Impossible 161650357972 65354104569 Impossible Impossible Impossible Impossible 4 189401911962950 Impossible Impossible Impossible Impossible 3750 119080845168191642 Impossible Impossible Impossible 2035 145998266186 26838140969 1 Impossible Impossible Impossible Impossible Impossible 140...
result:
wrong answer 2nd lines differ - expected: '3583 5', found: 'Impossible'