Why too late ?
Monday, July 28, 2008
I will make it quick. This is the C++ solution that I used to solve Google Code Jam Online Round 1C - Question 1. (it's so dumb, I know).
//
typedef long long int64;
typedef vector<int64> vi;
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
int main() {
freopen("in.in", "rt", stdin);
freopen("out.out", "wt", stdout);
int t;
cin >> t;
For(test, 1, t) {
int P,K,L;
cin >> P >> K >> L;
vector<vi> kk;
Rep(i, K){
vi vec;
kk.push_back(vec);
}
int64 letters[L];
Rep(i, L){
cin >> letters[i];
}
sort(AllA(letters,L));
int kx = 0;
Rep(i, L){
int64 l = letters[(L-i)-1];
bool put = true;
do{
int s = kk[kx].size();
if( s < P){
kk[kx].push_back(l);
put = false;
}
kx++;
if(kx>=K){
kx=0;
}
}while(put);
}
int64 minpress = 0;
Rep(i, K){
Rep(ix, kk[i].size()){
minpress += ( (kk[i][ix]) * (ix+1) );
}
}
cout << "Case #" << test << ": " << minpress << endl;
}
exit(0);
}
and this is the C++ solution that I came up after few hours of the contest.
//
typedef long long int64;
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
int main() {
freopen("in.in", "rt", stdin);
freopen("out.out", "wt", stdout);
int t;
cin >> t;
For(test, 1, t) {
int P,K,L;
cin >> P >> K >> L;
int64 letters[L];
Rep(i, L){
cin >> letters[i];
}
sort(AllA(letters,L));
int64 minpress = 0;
int store = 1;
Rep(i, L){
if(store>P)
store = 1;
int64 l = letters[(L-i)-1];
minpress += l * store;
if( (i+1)%K == 0)
store++;
}
cout << "Case #" << test << ": " << minpress << endl;
}
exit(0);
}
First solution is useless! and the second solution is far better than the first one. And both solutions provide the same output for the given input values. But I just couldn't code the easy and simple second solution during the contest. Why does it take too long.. ?

2 comments:
can you explain what is "Google Code Jam Online" that you are trying to solve here ???
Ah.. I'm talking about a question at Google Codejam, Online Round - 1. :)
http://code.google.com/codejam/contest/
Post a Comment