2014
03-03

# What is the air speed velocity…

What is the air speed velocity…

…of a fully laden swallow? This fearful question was posed to the intrepid band of Grail searchers.Their response of "African or European?" was partly correct.The air speed would most definitely depend on the sub-species of swallow. King Arthur, fearing more intense questioning in this vein,ordered his royal mathematicians to determine the air speed of a fully laden swallow – both African and European.

The mathematicians called upon the royal birders to capture a number of swallows of both types, lade them fully, and then release them from point A and time their arrival at point B.Since they didn’t want to confuse their figures, the European and African swallows were each started from a different location, so that each group flew a different distance, but all swallows in the same group flew the same distance. They then asked the royal map-makers to determine the distance (measured in furlongs) between the two starting points and the finish point. Using 10 swallows of each type, the royal mathematicians would then compute the average air speed for each group.

However, the royal mathematicians were somewhat lazy. After gathering all the data, they decided it was MUCH too hard to do all those nasty calculations by hand. So, they quickly constructed a time machine and have come into the future to enlist your help: they need you to write a program to do the calculations, which they will then take back into the past with them. Thus the searchers of the Grail will be saved from certain doom, (should this dastardly question be posed again), and you will go down in history as a hero. (Well, maybe not history, since they are from the past, so maybe you’ll go down in futurory?)

There’s one tricky bit (you knew it was coming): the royal mathematicians cannot agree on exactly how the average should be calculated. Some believe that, for each group, one should add up all of the times and then divide the total distance covered by all the swallows of that type by the total time (this is method 1). Others are of the opinion that the average speed is determined by computing the speed for each swallow, summing those values and then dividing that total by the total number of swallows (this is method 2). Your program should compute the average both ways, to avoid a nasty falling out among the royal mathematicians.

The input provided by the royal mathematicians is somewhat disorganized – the two breeds’times have been intermixed and they weren’t too careful about capitalization. But each entry is on a separate line and marked with an ‘A’ or ‘a’ or ‘E’ or ‘e’ to aid in identification. Each line begins with this single letter, followed by a single space. The final datum on the line is the elapsed time the swallow flew, expressed in hours. Since the time-keeping of the era wasn’t very accurate, this value is simply a real number (>0) with a single level of precision, such as 1.5 (one and a half hours), or 0.4 (four-tenths of an hour).

The very first line of the input file will consist of 2 integers, both greater than 0, separated by a single space. The first integer is the distance the African swallows flew and the second integer is the distance the European swallows flew. Next come the times for the swallows (20 lines total: 10 for African, 10 for European – NOT in this order). Thus the input file has a total of 21 lines.

The very first line of the input file will consist of 2 integers, both greater than 0, separated by a single space. The first integer is the distance the African swallows flew and the second integer is the distance the European swallows flew. Next come the times for the swallows (20 lines total: 10 for African, 10 for European – NOT in this order). Thus the input file has a total of 21 lines.

6 5
a 1.0
A 1.0
E 2.0
E 2.0
A 1.0
e 2.0
a 1.0
A 1.0
E 2.0
E 2.0
A 1.0
e 2.0
a 1.0
A 1.0
E 2.0
E 2.0
A 1.0
e 2.0
e 1.0
a 2.0

Method 1
African: 5.45 furlongs per hour
European: 2.63 furlongs per hour
Method 2
African: 5.70 furlongs per hour
European: 2.75 furlongs per hour

#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <cctype>
#include <list>
#include <hash_map>
#include <stack>
#include <hash_set>
#include <hash_map>
#include <sstream>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <hash_map>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define mset(a) memset(a,0,sizeof(a))
#define mmset(a) memset(a,-1,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
const int inf=1e9+7;
const long long linf=1e18;
typedef long double lf;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long double,long double> pdd;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
double a[10],b[10];
int main(){
double n,m;
scanf("%lf%lf\n",&n,&m);
int cnt1=0,cnt2=0;
for (int i=0;i<20;i++){
char ch;
cin>>ch;
ch=toupper(ch);
if (ch=='A') scanf("%lf",&a[cnt1++]);
else scanf("%lf",&b[cnt2++]);
}
double ans=0;
for (int i=0;i<10;i++)
ans+=a[i];
ans=n*10/ans;
printf("Method 1\n");
printf("African: %.2f furlongs per hour\n",ans);
ans=0;
for (int i=0;i<10;i++)
ans+=b[i];
ans=m*10/ans;
printf("European: %.2f furlongs per hour\n",ans);
printf("Method 2\n");
ans=0;
for (int i=0;i<10;i++)
ans+=(n/a[i]);
ans=ans/10;
printf("African: %.2f furlongs per hour\n",ans);
ans=0;
for (int i=0;i<10;i++)
ans+=(m/b[i]);
ans=ans/10;
printf("European: %.2f furlongs per hour\n",ans);
//system("pause");
return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

3. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.

4. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

5. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

6. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮