山东科技大学OJ集锦(10)

你的任务是求解下面这个问题。问题是这样描述的：a文钱可买一只公鸡，b文钱可买一只母鸡，c文钱可买d只小鸡。用m文钱买n只鸡，那么有公鸡x只、母鸡y只、小鸡z只。求解出符合题意的x,y,z。 Input

输入为一张表。第一行是一个固定不变的表头，格式见sample。后面有多行，每行为一组测试数据。每组测试数据由6个整数组成，分别为“a,b,c/d,m,n”。满足0

每组测试数据的运行结果输出为一张表，表头固定为“COCKS,HENS,CHICKS”。每组测试数据的一个可行解数出为一行，为三个整数：“x,y,z”。多组解按照公鸡数从少到多的顺序输出。若测试数据无解则输出“Cannot buy!”。两组测试数据之间用一个空行分隔开。 Sample Input

COCK,HEN,CHICK,MONEY,CHICKS 3,2,1/3,100,100 5,3,1/3,100,100 8,5,1/7,100,100 8,5,1/7,300,300 Sample Output

COCKS,HENS,CHICKS 0,40,60 5,32,63 10,24,66 15,16,69 20,8,72 25,0,75

COCKS,HENS,CHICKS 0,25,75 4,18,78 8,11,81 12,4,84 Cannot buy!

COCKS,HENS,CHICKS

8,40,252 HINT

本题重点在于了解多重循环的运行效率问题，减少一层循环可以降低很大规模的运算量。通过在循环体内加计数器可以统计出循环的运行次数，当测试数据变大时，运行次数的增长会非常可观，这就是超时的原因了。 #include int main() {

int a,b,c,d,e=0,m,n,x,y,z,i;

scanf(\,CHICKS\

while(scanf(\ { i=1;

for(x=0;x<=m/a;x++) {

y=(m*d-c*n+c*x-a*d*x)/(b*d-c); z=n-x-y;

if(x>=0&&y>=0&&z>=0&&x*a+y*b+(z*c)/d==m&&(c*z)%d==0) {

i=2; if(i==2) {

printf(\ printf(\ }

printf(\ }

}

if(i==1) {

printf(\ printf(\ } printf(\ }

return 0; }

正解：

#include int main() {

long int m,n;

int x,y,z,a,b,c,d,num_x,mon,count,flag;

scanf(\,CHICKS\

while(scanf(\ {

flag = 0; count = 0;

num_x = m / a;

for(x = 0;x <= num_x;x++) {

y = (m*d+c*x-c*n-a*d*x)/(b*d-c); z = n-x-y;

mon = a*x+b*y+c*z/d;

if(mon==m&&(c*z)%d==0&&y>=0&&z>=0) {

count++; if(count==1)

printf(\ printf(\ flag=1; } }

if(flag==0) {

printf(\ }

printf(\ } } (3-9)I

Description 问题背景：

神棍队的神棍童鞋很喜欢和女盆友逛街。神棍节这天，他们照例去逛街，亲昵过程中忽然发现路边上围了好一圈人。好奇心大盛的神棍于是凑过去围观。原来那里有一个棍神，他出了一道题目，如果有人能够答对的话，他就会实现那个人的一个愿望。神棍心想，有个女盆友多么幸福，要是大家都有女盆友该有多好。于是神棍想要答出这个问题，然后许一个让大家都可以很快拥有自己的女盆友的愿望，顺便在女盆友的面前臭美一番。神棍扫了一眼题目，拿出贴身小电脑，巴拉巴拉几下就敲出了代码，解决了那个问题。大家都在为神棍欢呼。这是什么问题呢？你是否也有兴趣看看？如果AC了的话就可以跟魔法少女签订契约，成为魔法少女的奴隶喔！ 问题描述：

某个数的立方如果以111结尾的话，我们就称其为“神棍数”，现在要你求第k大的“神棍数”是多少。 Input