QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#492954 | #6129. Magic Multiplication | priudy | AC ✓ | 3ms | 4020kb | C++14 | 3.8kb | 2024-07-26 17:26:55 | 2024-07-26 17:26:55 |
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+(it.first*it.second>=10);p<s.length()-1;p++){
if(k>m-1)k=0,u=0;
if(b.length()==m){
// cout<<"p: "<<p<<" "<<a<<" "<<b<<" u "<<u<<endl;
// cout<<(s[p]-'0') % (b[k]-'0')<<" "<<( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') )<<endl;
int o=0;
if(b[k]=='0'){o=1;
if(u==1){
if ( ( ((s[p]-'0')) != (a.back()-'0')*(b[k]-'0')) &&( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) ) != (a.back()-'0')*(b[k]-'0'))){
return false;
}
}
k++;
}
else if((s[p]-'0') % (b[k]-'0') ==0){
// cout<<((s[p]-'0')/(b[k]-'0'))<<endl;
// cout<<a<<" "<<b<<endl;
if(u==0 && ((s[p]-'0')/(b[k]-'0'))<10 )
a+=((s[p]-'0')/(b[k]-'0'))+'0',u=1,o=1;
else if(u==1){o=1;
// cout<<"xiangcheng "<<(a.back()-'0')*(b[k]-'0') <<" daan"<<((s[p]-'0')/(b[k]-'0'))+'0'<<endl;
if( ((s[p]-'0')) != (a.back()-'0')*(b[k]-'0')){
//cout<<"eufhewuihfueifh";
return false;
}
}
k++;
}
else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) % (b[k]-'0') ) == 0 ){
//cout<<a<<" "<<b<<" "<<k<<endl;
if(p+1<s.length()-1&&u==0&& ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )<10)
a+=( ( (s[p+1]-'0') + 10*(s[p]-'0') ) / (b[k]-'0') )+'0',u=1,o=1;
else if(u==1){o=1;
if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) ) != (a.back()-'0')*(b[k]-'0')){
// cout<<"asjhdfbasfbah "<<( ( (s[p+1]-'0') + 10*(s[p]-'0') ) ) <<endl;
return false;
}
}
p++;k++;
}
else return false;
if(!o)return false;
}
else {
int o=0;
if(s[p]=='0'){
o=1;
b+='0';
}
else if((s[p]-'0')%it.first==0){
if(((s[p]-'0')/it.first)<10)
b+=((s[p]-'0')/it.first)+'0',o=1;
if(o==0)return false;
}
else if( ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) %it.first) == 0 ){
if(p+1<s.length()-1&&( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)<10)
b+= ( ( (s[p+1]-'0') + 10*(s[p]-'0') ) /it.first)+'0',o=1;
p++;
if(o==0)return false;
}
else return false;
}
}
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)){
// cout<<"ekfhbewiuhf"<<a<<" "<<b<<endl;
if(ansa==""){
ansa=a,ansb=b;
}
else {
if(ansa>a){
ansa=a,ansb=b;
}
else if(ansa==ansb&&ansb>b){
ansa=a,ansb=b;
}
}
}
}
nums.clear();
for(int i=0;i<=9;i++){
for(int j=1;j<=9;j++){
if(i*j==s2){
nums.emplace_back(make_pair(i,j));
}
}
}
for(auto it:nums){
if(check(it)){//cout<<"wefewfewfew"<<a<<" "<<b<<endl;
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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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: 3ms
memory: 4020kb
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