NOI OpenJudge 题库 7623 五户共井问题

Algorithms
NOI OpenJudge

描述

有A, B, C, D, E五家人共用一口井，已知井深不超过k米。A, B, C, D, E的绳长各不相同，而且厘米表示的绳长一定是整数。
从井口放下绳索正好达到水面时：
(a)需要A家的绳n1条接上B家的绳1条
(b)需要B家的绳n2条接上C家的绳1条
(c)需要C家的绳n3条接上D家的绳1条
(d)需要D家的绳n4条接上E家的绳1条
(e)需要E家的绳n5条接上A家的绳1条
问井深和各家绳长。

输入

输入只有1行。包括空格分开的6个整数。
第一个整数k（1 <= k <= 20)，代表井的最大深度（单位：米）。
接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。

输出

输出只有1行。
如果找到了可行解，就输出6个整数，用空格分开，分别代表井的深度和A, B, C, D, E的绳长（单位都是厘米）。
如果有多组可行解，输出井的深度最小的那组解。
如果不存在可行解，就输出一行：
not found

样例输入

1
10 2 3 4 5 6

样例输出

1
721 265 191 148 129 76

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
int main()
{
	int k;
	int n1,n2,n3,n4,n5;
	cin >>k>>n1>>n2>>n3>>n4>>n5;
	int H,A,B,C,D,E;
	int ANSH=2147483647,ANSA,ANSB,ANSC,ANSD,ANSE;
	for(A=1;A<=k*100;A++)
		for(B=1;B<=k*100;B++)
		{
            H = A * n1 + B;
            C = H - B * n2;
            D = H - C * n3;
            E = H - D * n4;
            if((E * n5 + A != H) || H>k*100 || C<=0 || D<=0 || E<=0 || A==B || A==C || A==D || A==E || B==C || B==D || B==E || C==D || C==E ||D==E)
            	continue;
            if(H<ANSH)
            {
            	ANSH=H;
            	ANSA=A;
            	ANSB=B;
            	ANSC=C;
            	ANSD=D;
            	ANSE=E;
            }
		}
	if (ANSH==2147483647)
		cout <<"not found"<<endl;
	else cout <<ANSH<<" "<<ANSA<<" "<<ANSB<<" "<<ANSC<<" "<<ANSD<<" "<<ANSE<<endl;
	return 0;
}
分享到