首页 > 搜索 > BFS搜索 > hdu 1340 Cog-Wheels-BFS-[解题报告]
2013
12-09

hdu 1340 Cog-Wheels-BFS-[解题报告]

Cog-Wheels

问题描述 :

Your little sister has got a new mechanical building kit, which includes many cog-wheels of different sizes. She starts building gears with different ratios, but soon she notices that there are some ratios which are quite difficult to realize, and some others she cannot realize at all. She would like to have a computer program that tells her what ratios can be realized and what ratios cannot. She asks you to write a program that does the job.

For example, let us assume that the kit contains cog-wheels with 6, 12, and 30 cogs. Your sister wants to realize a gear of ratio 5 : 4. One possible solution is shown in Figure 2.

Figure 2: Combination of cog-wheels realizing a gear of 5 : 4.

It depicts a complete gear of ratio 5 : 4. Four wheels are used: cog-wheels of sizes 30 and 12 on the first axis, cog-wheels of sizes 6 and 12 on the second axis. The gear ratio is given by

as desired. However, a gear of ratio 1 : 6 cannot be realized using the cog-wheels your sister has.

Given the sizes of the cog-wheels in the kit (i.e. the number of cogs they have), decide whether a given gear ratio can be built or not. You may use any finite number of cog-wheels of each size available.

输入:

The input begins with a line containing the number of scenarios.

The input for each scenario starts with a description of the cog-wheels in the kit. First, there is a line containing the number n of different sizes of cog-wheels (1<=n<=20). The next line contains n numbers c1 . . . cn, separated by single blanks. These denote the n different sizes of the cog-wheels in the kit, with 5<=ci<=100 for i = 1, . . . , n. You may assume that there is a cog-wheel of smallest size c = min{c1, . . . , cn} in the kit such that all sizes c1, . . . , cn are multiples of c.

The line describing the available cog-wheels is followed by the list of gear ratios to be realized. It starts with a line containing the numbermof ratios. The nextmlines each contain two integers a and b, separated by a single blank. They denote the ratio a : b, with 1<=a, b<=10000.

输出:

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print the results for all the gear ratios given in that scenario. For each gear ratio a : b, print a line containing either Gear ratio a:b can be realized.

or

Gear ratio a:b cannot be realized.

Terminate the output of each scenario with a blank line.

样例输入:

2
3
6 12 30
2
5 4
1 6
1
42
2
13 13
42 1

样例输出:

Scenario #1:
Gear ratio 5:4 can be realized.
Gear ratio 1:6 cannot be realized.

Scenario #2:
Gear ratio 13:13 can be realized.
Gear ratio 42:1 cannot be realized.

首先根据给出的数算出所有在10000内的能到达的比率 r : 1 用bfs 来做,输入所要判断的 x:y 我们只要做的就是先求t=gcd(x,y),而后将
x:y转化为求 x /= t : y /= t;而这个过程我们来将新得的 x与y 因式分解for(int i = 2; i <= x; i++)只要找到x的因子i并mark[i] == i 即i的比率是
可达得就更新 x /= i; 如此也处理y; 若最后 x == y == 1则可达否则不可达
#include <iostream>
//#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 10001;
int q[MAX],a[21];
bool mark[MAX];
int Case,N,x,y;
int gcd(int n, int m){
int t;
while(m){
   t = m;
   m = n % m;
   n = t;
}
return n;
}
void bfs();

int main()
{
cin>>Case;
for(int S = 1; S <= Case; S++){
   cin>>N;
   for(int i = 0; i < N; i++)
    cin>>a[i];
   sort(a,a+N);
   for(int i = 1; i < N; i++)
    a[i] /= a[0];
   a[0] = 1;
   memset(mark, 0, sizeof(mark));
   //mark[q[0] = 1] = 1;
   bfs();
   int m;
   cin>>m;
   cout<<"Scenario #"<<S<<":\n";
   while(m–){   
    cin>>x>>y;
    int t;
    cout<<"Gear ratio "<<x<<’:'<<y;
    t = gcd(x,y);
    x /= t;
    y /= t;
    for(int i = 2; i <= y; i++)
     if(mark[i] && y%i == 0)
      y /= i;
    for(int i = 2; i <= x; i++)
     if(mark[i] && x%i == 0)
      x /= i;
    if(mark[y] && mark[x])cout<<" can ";
    else cout<<" cannot ";
    cout<<"be realized.\n";
   }
   cout<<endl;
}
return 0;
}
void bfs(){
int i = 0,top = 1, t;
mark[q[0] = 1] = 1;
while(i < top){
   for(int j = 0; j < N; j++){
    t = q[i] * a[j];
    if(t < MAX && !mark[t]){
     q[top++] = t;
     mark[t] = 1;
    }
    t = q[i] / a[j];
    if(t * a[j] == q[i] && !mark[t]){
     q[top++] = t;
     mark[t] = 1;
    }
   }
   i++;
}
}

解题转自:http://hi.baidu.com/yangchenhao/item/88331ef13797610884d278b2