猜算式

猜算式

时间: 1ms        内存:128M

描述:

看下面的算式:

□□ x □□ = □□ x □□□

它表示:两个两位数相乘等于一个两位数乘以一个三位数。

如果没有限定条件,这样的例子很多。

但目前的限定是:这9个方块,表示1~9的9个数字,不包含0。
该算式中1至9的每个数字出现且只出现一次!

比如:
46 x 79 = 23 x 158
54 x 69 = 27 x 138
54 x 93 = 27 x 186
.....

请编程,输出所有可能的情况!

注意:
左边的两个乘数交换算同一方案,不要重复输出!
不同方案的输出顺序不重要

输入:

输出:

示例输入:

示例输出:

46x79=23x158
54x69=27x138
54x93=27x186
........

提示:

参考答案(内存最优[776]):

#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node
{
        long w,s,num;
}node;
node a[N];
long f[N],b[N],q[N],n;

int bigger(node x,node y)
{
     if (x.w!=y.w) return (x.w>y.w);
     else return (x.s<y.s);
}

void sort(long left,long right)
{
     long i,j;
     node x,t;
     i=left;j=right;
     x=a[(i+j)/2];
     while (i<=j)
     {
           while (bigger(x,a[i])) i++;
           while (bigger(a[j],x)) j--;
           if (i<=j)
           {     t=a[i];a[i]=a[j];a[j]=t;
                 i++;j--;
           }
     }
     if (left<j) sort(left,j);
     if (i<right) sort(i,right);
}
int main()
{
    long i,j,k,max;
    i=1;
    while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;  
    n=i-1;
    sort(1,n);
    for (i=1;i<=n;i++) {f[i]=1;b[i]=i;}
    for (i=1;i<=n;i++)
        for (j=1;j<i;j++)
            if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i])
            {  f[i]=f[j]+1; b[i]=j; }
    max=0;
    for (i=1;i<=n;i++)
        if (f[i]>max) {max=f[i];k=i;}
    printf("%ld\n",max);
    q[1]=a[k].num; i=1;
    while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
    for (i=max;i>=1;i--)
        printf("%ld\n",q[i]);
    return 0;
}

参考答案(时间最优[4]):

#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node
{
        long w,s,num;
}node;
node a[N];
long f[N],b[N],q[N],n;

int bigger(node x,node y)
{
     if (x.w!=y.w) return (x.w>y.w);
     else return (x.s<y.s);
}

void sort(long left,long right)
{
     long i,j;
     node x,t;
     i=left;j=right;
     x=a[(i+j)/2];
     while (i<=j)
     {
           while (bigger(x,a[i])) i++;
           while (bigger(a[j],x)) j--;
           if (i<=j)
           {     t=a[i];a[i]=a[j];a[j]=t;
                 i++;j--;
           }
     }
     if (left<j) sort(left,j);
     if (i<right) sort(i,right);
}
int main()
{
    long i,j,k,max;
    i=1;
    while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;  
    n=i-1;
    sort(1,n);
    for (i=1;i<=n;i++) {f[i]=1;b[i]=i;}
    for (i=1;i<=n;i++)
        for (j=1;j<i;j++)
            if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i])
            {  f[i]=f[j]+1; b[i]=j; }
    max=0;
    for (i=1;i<=n;i++)
        if (f[i]>max) {max=f[i];k=i;}
    printf("%ld\n",max);
    q[1]=a[k].num; i=1;
    while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
    for (i=max;i>=1;i--)
        printf("%ld\n",q[i]);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注