QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#144184#6129. Magic MultiplicationPhantomThreshold#AC ✓57ms41824kbC++202.2kb2023-08-21 15:50:282023-08-21 15:50:31

Judging History

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

  • [2023-08-21 15:50:31]
  • 评测
  • 测评结果:AC
  • 用时:57ms
  • 内存:41824kb
  • [2023-08-21 15:50:28]
  • 提交

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