QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#252842#6129. Magic MultiplicationsfjhAC ✓18ms4640kbC++142.1kb2023-11-16 13:14:462023-11-16 13:14:47

Judging History

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

  • [2023-11-16 13:14:47]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:4640kb
  • [2023-11-16 13:14:46]
  • 提交

answer

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e5+5;
int T,n,m,a[maxn],b[maxn];
char c[maxn];
bool GetB() {
    int len=strlen(c),pos=0;
    for(int i=0; i<m; i++) {
        if(pos==len)return 0;//字符串不够用,不合法
        int x=c[pos++]-'0';//获得对应数字
        if(pos<len&&x&&x<a[0])x=x*10+c[pos++]-'0';
        //如果字符串够用,这一位不为0,数字小于a[0],就需要多拿一位
        if(x%a[0]||x/a[0]>9)return 0;
        //如果不能整除或者商为两位数
        b[i]=x/a[0];//构造b[i]
    }
    for(int i=1; i<n; i++)
        for(int j=0; j<m; j++) {
            if(pos==len)return 0;
            int x=c[pos++]-'0';//获得对应数字
            if(pos<len&&x&&x<b[j])x=x*10+c[pos++]-'0';
            //如果字符串够用,这一位不为0,数字小于a[0],就需要多拿一位
            if(x&&(b[j]==0||(j&&a[i]==0)))return 0;
            //如果有结果但是b的对应位为0或者a的对应位为0(j代表已经计算过,根据0~j-1推出a[i]==0)
            if(x==0) {
                if(j&&a[i]&&b[j])return 0;
                //结果有0并且a[i]已经算过,b的对应为有值
                if(!j)a[i]=0;//如果第一次算,结果为0,则a[i]为0
            } else {
                if (x%b[j]||j&&x/b[j]!=a[i]||x/b[j]>9) return 0;
                //如果不能整除或者商为两位数
                a[i]=x/b[j];
            }
        }
    return pos==len;
}
bool Judge(int x) {
    for(int i=1; i<=9; i++)
        if(x%i==0) {
            a[0]=i;
            if(GetB())return 1;
        }
    return 0;
}
bool solve() {
    int x=c[0]-'0';
    if(Judge(x))return 1;
    x=x*10+c[1]-'0';
    if(Judge(x))return 1;
    return 0;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%s",&n,&m,&c);
        if(solve()) {
            for(int i=0; i<n; i++)printf("%d",a[i]);
            putchar(' ');
            for(int i=0; i<m; i++)printf("%d",b[i]);
            putchar('\n');
        } else printf("Impossible\n");
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3760kb

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: 18ms
memory: 4640kb

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