Qualification round of Google Code Jam is over, I have managed to get only 53 points of 99 possible. Not a very good start, but nevertheless I proceeded to Round 1. Here is some of my code, that I solved the problems with.
Snapper Chain
It was the easiest problem to solve. (Problem Text) The key to the solution is that the chain shows number of snaps in binary (actually last n bits of it), and light is on when all snappers are in ON state (= the last n bits are all equal to 1).
#include <iostream>
#include <math.h>
using namespace std;
int main(){
unsigned int t, n, k;
cin >> t;
for (unsigned int i=1; i<=t; i++){
cin >> n >> k;
unsigned int d = (1U << n ) - 1;
cout << "Case #" << i << ": " <<
( (k & d) == d ? "ON" : "OFF" ) << endl;
}
}
Provided code was successful with large input too.
Fair Warning
This one was a little bit harder. (Problem Text) The key is that the difference is time between any 2 events stays the same, no matter how big/small number of starboseconds we add to all of them. So we need a greatest common divisor of the differences.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
uint gcd( uint a, uint b ){
if ( b == 0 ) return a;
return gcd( b, a % b );
}
uint op_minus( uint a, uint b){
return a > b ? a - b : b - a;
}
int main(){
uint c, n, tmp;
cin >> c;
for (uint i=1; i<=c; i++){
cin >> n;
vector<uint> t;
for (uint j=0; j<n; j++){
cin >> tmp;
t.push_back( tmp );
}
//after first transformation t[i] will have the difference
//between former t[i] and t[i+1].
//The last member t[n-1] remains - it will be needed at the end
//to find the required amount of seconds to add
transform( t.begin(), t.end()-1, t.begin()+1, t.begin(), op_minus );
//after second transformation t[i] will have the gcd of t[i-1] and t[i]
//I use the following feature of gcd: gcd(a,b,c) == gcd(gcd(a,b), c)
//every time we are at t[i] there is alreaady a gcd(t[i-2], t[i-1]) in t[i-1]
transform( t.begin(), t.end()-2, t.begin()+1, t.begin()+1, gcd );
uint remainder = t.back() % *(t.end()-2);
cout << "Case #" << i << ": " <<
(remainder > 0 ? *(t.end()-2) - remainder : 0 )<< endl;
}
}
This code does not solve the large input as there are integers up to 1050, and we need to use a bigint class, which I didn't find/write myself.
Theme Park
This is the hardest one to solve, because small input can be solved with straight approach, but the large one needs some different. And I couldn't figure it out. (Problem Text) The code that solves the small input is pretty straightforward. We take the group at the beginning of the queue as soon as it can fit in roller coaster. And don't forget that 1 and the same group cannot be taken twice in 1 run (that may happen if number of seats in roller coaster is more than all the number of people in queue)
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned int uint;
int main(){
uint t, r, k, n, tmp, sum, total;
cin >> t;
for (uint i=1; i<=t; i++){
cin >> r >> k >> n;
vector<uint> g;
total = 0;
for (uint j=0; j<n; j++){
cin >> tmp;
g.push_back( tmp );
}
uint a=0;
for (uint j=0; j<r; j++){
uint sum = 0;
for (uint b=0; b<n && sum + g[a] <= k; a=(a+1)%n, b++ ){
sum += g[a];
}
//cout << "sum: " << sum << " ";
total += sum;
}
cout << "Case #" << i << ": " << total << endl;
}
}
Pity, the same approach is too slow for large input.
The "official" solutions can be found here.
