A49987. 井和绳子
填空题
中等
知识点
题目描述
井和绳子
题目描述
有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个整数。第一个整数1<=k<=20)，代表井的最大深度（单位：米）。
接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。
输出
输出只有1行。
如果找到了可行解，就输出6个整数，用空格分开，分别代表井的深度和A, B, C, D, E的绳长（单位都是厘米）。
如果有多组可行解，输出井的深度最小的那组解。
如果不存在可行解，就输出一行：not found
样例输入
10 2 3 4 5 6样例输出
721 265 191 148 129 76参考答案
#include <bits/stdc++.h>
using namespace std;
int main(){
int k,n1,n2,n3,n4,n5;
int a,b,c,d,e,len;
cin>>k>>n1>>n2>>n3>>n4>>n5;
for(len=1;len<=k*100;len++){
for(a=1;a<=len;a++){
b=len-a*n1;
c=len-b*n2;
d=len-c*n3;
e=len-d*n4;
if(a==b||a==c||a==d||a==e||b==c||b==d||b==e||c==d||c==e||d==e)continue;
if(e*n5+a==len){
printf("%d %d %d %d %d %d",len,a,b,c,d,e);
return 0;
}
}
}
printf("not found");
return 0;
}答案解析
#include <iostream>
using namespace std;
int main() {
int k, n1, n2, n3, n4, n5;
cin >> k >> n1 >> n2 >> n3 >> n4 >> n5;
int max_H = k * 100; // 转换为厘米
for (int H = 1; H <= max_H; ++H) {
// 计算系数 coeff = 1 - n5*(1 - n4*(1 - n3*(1 - n2)))
int coeff = 1 - n5 * (1 - n4 * (1 - n3 * (1 - n2)));
long long denom = 1LL + (long long)n1 * n2 * n3 * n4 * n5; // 防止溢出
long long numer = (long long)H * coeff;
if (numer <= 0 || numer % denom != 0) continue;
int A = numer / denom;
if (A <= 0) continue;
// 依次计算其他绳长
int B = H - n1 * A;
if (B <= 0) continue;
int C = H - n2 * B;
if (C <= 0) continue;
int D = H - n3 * C;
if (D <= 0) continue;
int E = H - n4 * D;
if (E <= 0) continue;
// 验证条件 (e)
if (n5 * E + A != H) continue;
// 检查所有绳长是否互不相同
if (A == B || A == C || A == D || A == E ||
B == C || B == D || B == E ||
C == D || C == E ||
D == E) {
continue;
}
// 输出结果
cout << H << " " << A << " " << B << " " << C << " " << D << " " << E << endl;
return 0;
}
return 0;
}
上一题
下一题