QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694196#6129. Magic Multiplicationucup-team3294#AC ✓16ms5336kbC++231.6kb2024-10-31 17:27:342024-10-31 17:27:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 17:27:35]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:5336kb
  • [2024-10-31 17:27:34]
  • 提交

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