题目很长,就是说用从n种硬币中选取4种不同的硬币堆叠起来,作为桌子的四个腿,显然,桌子的四个腿要相等。问对于一个给定的高度h,硬币能够堆成的不大于h的最大高度和不小于h的最小高度分别为多少?
应为数据不大, n为50左右,可以用4个for循环来枚举硬币,假设四种硬币为a、b、c、d,求的这四个数的最小公倍数即可,然后就用欧几里得算法解决。
1
/**//*
2
Source Code
3
4
Problem: 1855 User: yzhw
5
Memory: 8648K Time: 313MS
6
Language: G++ Result: Accepted
7
*/
8
9
10
# include <iostream>
11
# include <cstdio>
12
using namespace std;
13
int l[51];
14
int refer[51][51][51][51];
15
int gcd(int a,int b)
16

{
17
while(b)
18
{
19
int t=a%b;
20
a=b;
21
b=t;
22
}
23
return a;
24
}
25
int main()
26

{
27
int n,t;
28
while(true)
29
{
30
scanf("%d%d",&n,&t);
31
if(!n&&!t) break;
32
for(int i=0;i<n;i++)
33
scanf("%d",l+i);
34
for(int a=0;a<n;a++)
35
for(int b=a+1;b<n;b++)
36
//if(a!=b)
37
for(int c=b+1;c<n;c++)
38
//if(a!=c&&b!=c)
39
for(int d=c+1;d<n;d++)
40
//if(a!=d&&b!=d&&c!=d)
41
{
42
int lcd1=l[a]*l[b]/gcd(l[a],l[b]),lcd2=l[c]*l[d]/gcd(l[c],l[d]);
43
int lcd=lcd1*lcd2/gcd(lcd1,lcd2);
44
refer[a][b][c][d]=lcd;
45
46
}
47
48
while(t--)
49
{
50
int minnum=0xfffffff,maxnum=-1;
51
int pos;
52
scanf("%d",&pos);
53
for(int a=0;a<n;a++)
54
for(int b=a+1;b<n;b++)
55
for(int c=b+1;c<n;c++)
56
for(int d=c+1;d<n;d++)
57
{
58
59
int lcd=refer[a][b][c][d];
60
if(pos-pos%lcd>maxnum)
61
maxnum=pos-pos%lcd;
62
if(pos%lcd&&lcd*(pos/lcd+1)<minnum)
63
minnum=lcd*(pos/lcd+1);
64
if(pos%lcd==0&&pos<minnum)
65
minnum=pos;
66
67
}
68
printf("%d %d\n",maxnum,minnum);
69
}
70
}
71
return 0;
72
}
73
74