1998 ACM Finals, Dan Adkins
Farmer John feeds his cows only the finest mixture of cow food, which has three components: Barley, Oats, and Wheat. While he knows the precise mixture of these easily mixable grains, he can not buy that mixture! He buys three other mixtures of the three grains and then combines them to form the perfect mixture.
Given a set of integer ratios barley:oats:wheat, find a way to combine them IN INTEGER MULTIPLES to form a mix with some goal ratio x:y:z.
For example, given the goal 3:4:5 and the ratios of three mixtures:
1:2:3 3:7:1 2:1:2
your program should find some minimum number of integer units (the `mixture') of the first, second, and third mixture that should be mixed together to achieve the goal ratio or print `NONE'. `Minimum number' means the sum of the three non-negative mixture integers is minimized.
For this example, you can combine eight units of mixture 1, one unit of mixture 2, and five units of mixture 3 to get seven units of the goal ratio:
8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)
Integers in the goal ratio and mixture ratios are all non-negative and smaller than 100 in magnitude. The number of units of each type of feed in the mixture must be less than 100. The mixture ratios are not linear combinations of each other.
PROGRAM NAME: ratios
INPUT FORMAT
Line 1: | Three space separated integers that represent the goal ratios |
Line 2..4: | Each contain three space separated integers that represent the ratios of the three mixtures purchased. |
SAMPLE INPUT (file ratios.in)
3 4 5 1 2 3 3 7 1 2 1 2
OUTPUT FORMAT
The output file should contain one line containing four integers or the word `NONE'. The first three integers should represent the number of units of each mixture to use to obtain the goal ratio. The fourth number should be the multiple of the goal ratio obtained by mixing the initial feed using the first three integers as mixing ratios.
SAMPLE OUTPUT (file ratios.out)
8 1 5 7
题意:
给出 3 个数,还有 3 X 3 的矩阵,可以对每一行乘上一个系数,使最终对应加起来能得到给出的 3 个数,可以提出公因子,输出这 3 个系数和公因子。凑不出则输出 NONE。数据小于100。
思路:
乍一看就想到高斯消元。但是一看数据才小于 100,所以果断暴力了。因为可能会有除 0 的状况,所以每一种情况都讨论了一遍。
AC:
/* ID:sum-g1 LANG:C++ PROG:ratios */ #include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; int main() { freopen("ratios.in","r",stdin); freopen("ratios.out","w",stdout); int A, B, C; int num[5][5]; scanf("%d%d%d", &A, &B, &C); for (int i = 1; i <= 3; ++i) for (int j = 1; j <= 3; ++j) scanf("%d", &num[i][j]); int temp = 0; for (int x = 0; x <= 100; ++x) { for (int y = 0; y <= 100; ++y) { for (int z = 0; z <= 100; ++z) { int aa = x * num[1][1] + y * num[2][1] + z * num[3][1]; int bb = x * num[1][2] + y * num[2][2] + z * num[3][2]; int cc = x * num[1][3] + y * num[2][3] + z * num[3][3]; int t1, t2, t3; if (!A && B && C) { if (!bb || !cc || aa) continue; if (bb % B || cc & C) continue; if (bb / B == cc / C) { printf("%d %d %d %d\n", x, y, z, bb / B); temp = 1; break; } } else if (A && !B && C) { if (!aa || bb || !cc) continue; if (aa % A || cc % C) continue; if (aa / A == cc / C) { printf("%d %d %d %d\n", x, y, z, aa / A); temp = 1; break; } } else if (A && B && !C) { if (!aa || !bb || cc) continue; if (aa % A || bb % B) continue; if (aa / A == bb / B) { printf("%d %d %d %d\n", x, y, z, bb / B); temp = 1; break; } } else if (!A && !B && C) { if (aa || bb || !cc) continue; if (cc % C) continue; printf("%d %d %d %d\n", x, y, z, cc / C); temp = 1; break; } else if (!A && B && !C) { if (aa || !bb || cc) continue; if (bb % B) continue; printf("%d %d %d %d\n", x, y, z, bb / B); temp = 1; break; } else if (A && !B && !C) { if (!aa || bb || cc) continue; if (aa % A) continue; printf("%d %d %d %d\n", x, y, z, aa / A); temp = 1; break; } else if (!A && !B && !C) { printf("%d %d %d %d\n", 0, 0, 0, 0); temp = 1; break; } else { if (!aa || !bb || !cc) continue; if (aa % A || bb % B || cc % C) continue; if (aa / A == bb / B && aa / A == cc / C) { printf("%d %d %d %d\n", x, y, z, aa / A); temp = 1; break; } } } if (temp) break; } if (temp) break; } if (!temp) printf("NONE\n"); return 0; }
相关推荐
Financial history and ratios.xls
The Sharpe ratio (Sharpe 1992) is one industry standard for measuring the absolute risk adjusted performance of hedge funds. This function performs the testing of Sharpe ratio difference for two funds...
The Sharpe ratio (Sharpe 1992) is one industry standard for measuring the absolute risk adjusted performance of hedge funds. This function performs the testing of Sharpe ratio difference for two funds...
Measuring additive interaction using odds ratios Linda Kalilani and Julius Atashili* alth, University of North Carolina at Chapel Hill, USA Email: Linda Kalilani - kalilani@email.unc.edu; Julius ...
Selecting PDM Microphone Clock Frequencies and Decimation Ratios PDM麦克风选择以及抽取比设置
FINANCIAL HISTORY AND RATIOS(表格模板、XLS格式).xls
CFA 一级试题 八 Investment Tools Financial Statement Analysis Financial Ratios and Earnings per Share_removed
与选定的参考基准相比,向上和... Reference 和 account 可以在同一个输入表中,也可以在具有相同列布局的不同表文件中输入。 很少,这也可能作为一个指标是可取的,为此目的,为两个比率的移动窗口计算添加回顾滞后。
连分数中某些遍历和的比,廖灵敏,,本文研究与连分数相关的高斯动力系统中的遍历和的比的重分形分析。对任意的零一区间上的无理数x, 令x=[a1(x),a2(x),...]为它的连分数展�
高长径比宏孔硅阵列光电化学腐蚀中孔径控制技术,王国政,王蓟,高长径比宏孔硅阵列(MSA)在光子晶体、硅微通道板、MEMS 器件等领域应用前景广阔,引起人们广泛关注。为制备理想的MSA结构,本文开�
不同Si/Al比的HZSM-5分子筛对碱性分子和烷烃分子的吸附,夏溢芬,薛念华,通过在HZSM-5分子筛上吸附碱性分子进行程序升温脱附和红外光谱表征,结果表明,含有不同Si/Al比值的HZSM-5分子筛子在酸性质上没有明显差�
to nonlinear sum-of-ratios problem arising in image processing, engineering and man- agement. Unlike traditional methods which may get trapped in local minima due to the non-convex nature of this ...
Universal Linear-Optical Logic Gate with Maximal Intensity Contrast Ratios
固固比对磷酸镁钾化学结合陶瓷的固化行为及相组成和微观结构的影响,王爱娟,袁志龙,磷酸镁钾化学结合陶瓷已经应用到生物医学领域。在本研究中,了解了不同固固比(即氧化镁:磷酸二氢钾)所形成的化学结合陶瓷的固化...
类铍离子内壳激发态1s2p3 3Po 和 3Do的能量、俄歇宽度和俄歇分支率的计算,张孟,苟秉聪,本文采用鞍点变分方法计算了类铍离子等电子系列(Z=4-10)内壳激发态1s2p3 3Po 和3Do的相对论能量。采用鞍点复数转动方法计算...
Ba0.99(Bi0.5Na0.5)0.01TiO3陶瓷中Bi/Ba掺杂比例与其物理性能和PTC特性的相互关系,刘明龙,,论文研究了Bi/Ba的掺杂量对Ba0.99(Bi0.5Na0.5)0.01TiO3陶瓷物理性能和PTC特性的关系。由于Bi2O3具有易挥发的特性,最终...
具有自交互暗物质晕的球状星团 Wiki中的文档。
本人亲自试验 mysql存储分页 mysql存储过程分页 mysql数据分页 limit数据分页 mysql的limit