250pt
题意：上帝知道一个“先有鸡还是先有蛋”的答案，上帝和N<=10^6个人说了答案，不过有x个人故意告诉了他们错误的答案，然后有一个人问了这N个人问题的答案，有M个人说先有鸡，N-M个人说现有蛋，已知其中有y个人故意说了上帝告诉他们的相反的答案。现在给N M x y，问是否能推测出答案，或者多解，或者无解。
思路：因为N很小，直接枚举那些人说谎，然后判定即可。
500pt
题意：有N<=50个任务，每个任务有运行时间和用户，机器同一个时间只能跑一个任务，一个任务运行中不能中断，每个用户可能有多个任务，每个用户的等待时间为他的最后一个任务完成前等待的时间。电脑安排任务始终保证所有用户的平均等待时间最短，在这个条件下， 每个schedule都有同等的可能性。现在给你N个任务的信息，问每个任务期望的结束时间是多少。
思路：很明显，对于某个人的任务，那么一定是连着运行对于结果最优。
那么那么如果a与b的任务运行时间相同，那么他们两个是可以交换的。
同时，对于同一user的任务间，顺序任意。接下去便是统计了。注意任务是等概率的就好做了。
code：
// BEGIN CUT HERE
/* */
// END CUT HERE
#line 7 "BatchSystemRoulette.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int, int> PII;
struct oo{
int val, id;
string usr;
oo(){}
oo(int _val, int _id, string _usr): val(_val), id(_id), usr(_usr){}
bool operator<(const oo &b)const{
return usr < b.usr || (usr == b.usr && val < b.val);
}
};
int P[], S[], last[];
long long sum[];
class BatchSystemRoulette
{
public:
vector <double> expectedFinishTimes(vector <int> dur, vector <string> user)
{
vector<oo> v;
v.clear();
for (int i = ; i < dur.size(); ++i)
v.push_back(oo(dur[i], i, user[i]));
sort(v.begin(), v.end());
int n = v.size();
memset(sum, , sizeof(sum));
memset(P, , sizeof(P));
int m = ;
sum[] = v[].val;
P[] = ;
for (int i = ; i < n; ++i){
if (v[i].usr != v[i-].usr) m++;
sum[m] += v[i].val;
P[i] = m;
}
last[m] = n - ;
memset(S, , sizeof(S));
for (int i = ; i <= m; ++i)
for (int j = ; j <= m; ++j)
if (sum[i] == sum[j]) S[i]++;
vector<double> ans(n);
for (int i = ; i < n; ++i){
double ssum = ;
for (int j = ; j <= m; ++j)
if (sum[P[i]] > sum[j]) ssum += sum[j];
double tmp = (S[P[i]] - 1.0) / 2.0 * sum[P[i]];
tmp += 0.5 * (sum[P[i]] - v[i].val) + v[i].val;
ans[v[i].id] = tmp + ssum;
}
return ans;
}
};