Rating: Not Rated -> 1170.387
Socializing Game around Pizza(BIGPIZA)
This is a problem about a simple game. It can be solved easily by using Grundy Number.
First, let G[0] and G[1] be 0, because it is impossible to make any pairs if we have 0 or 1 people around the pizza. For N >= 2, we can calculate G[N] by searching the smallest non-negative integer which doesn't appear in a set {G[i] xor G[N-2-i] | 0 <= i <= N-2}.
Time complexity of this algorithm is O(N^2).
Solution in C++ (in the contest)
#include<cstdio>
using namespace std;
int main()
{
int grundy[10001];
grundy[0] = 0; grundy[1] = 0;
for(int i=2; i<=10000; ++i) {
int a[10001] = {0};
for(int j=0; j<=i-2; ++j)
a[grundy[j] ^ grundy[i-j-2]] = 1;
for(int j=0; j<=10000; ++j) {
if(a[j] == 0) {
grundy[i] = j;
break;
}
}
}
int T;
scanf("%d", &T);
while(T--) {
int n;
scanf("%d", &n);
puts(grundy[n] ? "Arjuna" : "Bhima");
}
return 0;
}
Preferred Cooking Schools(CKSCHOOL)
This is really hard problem. I can't solve this yet.
Distribute idlis Equally(EQIDLIS)
My solution for this problem is just simulate the redistributing process. Using multiset, one step can be done in O(log N). So the overall complexity is O(N + Result * log N).
But the result will not be so large, so I didn't use multiset. In my solution, one step is done in O(N). So the overall complexity of my solution is O(Result * N).
Solution in C++ (in the contest)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int T;
scanf("%d", &T);
while(T--) {
int N;
scanf("%d", &N);
vector<int> v(N);
for(int i=0; i<N; ++i)
scanf("%d", &v[i]);
int S=0;
for(int i=0; i<N; ++i)
S+=v[i];
if(S%N != 0) {
puts("-1");
continue;
}
vector<int> t;
sort(v.begin(), v.end());
for(int i=0; i<(int)v.size(); ++i)
if(v[i] != S/N) t.push_back(v[i]);
v = t;
int cnt = 0;
while(v.size() > 0) {
vector<int> p;
int R = (v.back()-v.front()+1) / 2;
int A = v.front()+R, B = v.back()-R, K = v.size();
if(A > B) swap(A, B);
if(A == S/N) K--, A = -100;
if(B == S/N) K--, B = -100;
p.resize(K);
int k = 0;
for(int i=1; i<(int)v.size()-1; ++i) {
int prev = i==1 ? -1 : p.back();
if(prev <= A && A <= v[i]) p[k++]=A, A=-100;
if(prev <= B && B <= v[i]) p[k++]=B, B=-100;
p[k++]=v[i];
}
if(A >= 0) p[k++]=A;
if(B >= 0) p[k++]=B;
v = p;
cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
Packing the Golden Triangles(PACKBAND)
This problem can be solved by greedy approach. We sort the lengths of the boxes in increasing order, and sort the rubber bands in increasing order of R2. Then for each box, we search the first unused rubber bands which can be used to pack the box.
Solution in C++ (in the contest)
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
bool cmp(const pair<int, int> a, const pair<int, int> b)
{
return make_pair(a.second, a.first)<make_pair(b.second, b.first);
}
int N, M, L[1024], U[1024];
pair<int, int> R[1024];
int dp[1024][1024];
inline bool ok(int i, int j)
{
return R[j].first*11<=L[i]*7 && L[i]*7<=R[j].second*11;
}
int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
for(int i=0; i<N; ++i)
scanf("%d", &L[i]);
scanf("%d", &M);
for(int i=0; i<M; ++i)
scanf("%d%d", &R[i].first, &R[i].second), U[i]=0;
sort(L, L+N);
sort(R, R+M, cmp);
int S=0;
for(int i=0; i<N; ++i) {
for(int j=0; j<M; ++j) {
if(U[j]==0 && ok(i, j)) {
U[j]=1;
S++;
break;
}
}
}
printf("%d\n", S);
}
return 0;
}
Popular Rice Recipe(TIDRICE)
This is straight forward problem and quite easy. Just implementation.
Solution in C++ (in the contest)
#include<map>
#include<string>
#include<iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--) {
int N;
cin >> N;
map<string, int> V;
while(N--) {
string s, t;
cin >> s >> t;
if(t=="+") V[s]=1; else V[s]=-1;
}
int S=0;
for(map<string, int>::iterator it=V.begin(); it!=V.end(); ++it)
S+=it->second;
cout << S << endl;
}
return 0;
}
