看下數據范圍~~最大才100...稍微想一下...答案求出的所有結果肯定都是小於100的了...那麼三層for循環來暴力找滿足要求的最優解就ok了..注意的是惡心點的..給出的(x,y,z)可能有為0的...所以要特殊處理下...
Program:
/*
ID: zzyzzy12
LANG: C++
TASK: ratios
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<algorithm>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
int x,y,z;
}s[4];
int i,j,k,ans[4],m;
void getanswer()
{
ans[0]=oo;
for (i=0;i<=100;i++)
for (j=0;j<=100;j++)
for (k=0;k<=100;k++)
if ((!s[0].x || (s[1].x*i+s[2].x*j+s[3].x*k)%s[0].x==0) && (!s[0].y || (s[1].y*i+s[2].y*j+s[3].y*k)%s[0].y==0) && (!s[0].z || (s[1].z*i+s[2].z*j+s[3].z*k)%s[0].z==0))
{
m=0;
if (s[0].x) m=(s[1].x*i+s[2].x*j+s[3].x*k)/s[0].x;
else
{
if (s[1].x*i+s[2].x*j+s[3].x*k) continue;
if (s[0].y) m=(s[1].y*i+s[2].y*j+s[3].y*k)/s[0].y;
else
{
if (s[1].y*i+s[2].y*j+s[3].y*k) continue;
if (s[0].z) m=(s[1].z*i+s[2].z*j+s[3].z*k)/s[0].z;
}
}
if (!m) continue;
if (s[1].y*i+s[2].y*j+s[3].y*k==m*s[0].y)
if (s[1].z*i+s[2].z*j+s[3].z*k==m*s[0].z)
if (ans[0]>m)
{
ans[1]=i; ans[2]=j; ans[3]=k;
ans[0]=m;
}
}
}
int main()
{
freopen("ratios.in","r",stdin);
freopen("ratios.out","w",stdout);
for (i=0;i<4;i++) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);
getanswer();
if (ans[0]==oo) printf("NONE\n"); else
printf("%d %d %d %d\n",ans[1],ans[2],ans[3],ans[0]);
return 0;
}
/*
ID: zzyzzy12
LANG: C++
TASK: ratios
*/
#include<iostream>
#include<istream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<algorithm>
#include<queue>
#define oo 2000000000
#define ll long long
using namespace std;
struct node
{
int x,y,z;
}s[4];
int i,j,k,ans[4],m;
void getanswer()
{
ans[0]=oo;
for (i=0;i<=100;i++)
for (j=0;j<=100;j++)
for (k=0;k<=100;k++)
if ((!s[0].x || (s[1].x*i+s[2].x*j+s[3].x*k)%s[0].x==0) && (!s[0].y || (s[1].y*i+s[2].y*j+s[3].y*k)%s[0].y==0) && (!s[0].z || (s[1].z*i+s[2].z*j+s[3].z*k)%s[0].z==0))
{
m=0;
if (s[0].x) m=(s[1].x*i+s[2].x*j+s[3].x*k)/s[0].x;
else
{
if (s[1].x*i+s[2].x*j+s[3].x*k) continue;
if (s[0].y) m=(s[1].y*i+s[2].y*j+s[3].y*k)/s[0].y;
else
{
if (s[1].y*i+s[2].y*j+s[3].y*k) continue;
if (s[0].z) m=(s[1].z*i+s[2].z*j+s[3].z*k)/s[0].z;
}
}
if (!m) continue;
if (s[1].y*i+s[2].y*j+s[3].y*k==m*s[0].y)
if (s[1].z*i+s[2].z*j+s[3].z*k==m*s[0].z)
if (ans[0]>m)
{
ans[1]=i; ans[2]=j; ans[3]=k;
ans[0]=m;
}
}
}
int main()
{
freopen("ratios.in","r",stdin);
freopen("ratios.out","w",stdout);
for (i=0;i<4;i++) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].z);
getanswer();
if (ans[0]==oo) printf("NONE\n"); else
printf("%d %d %d %d\n",ans[1],ans[2],ans[3],ans[0]);
return 0;
}
摘自 Jacob's zone
