Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? WTF is that?!
Oh, and I don't care so much about being able to win a contest as I am completing a personal challenge.
This is a discussion on Intercollegiate programming contest problems within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? ...
Alright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? WTF is that?!
Oh, and I don't care so much about being able to win a contest as I am completing a personal challenge.
FAQ
"The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.
"If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.
Yeah, I was just joking. Anyways, I had a question similar to that a few weeks ago, and wrote it up. After reading the question, mines not exactly what they want, but pretty close. Don't have the time to rewrite it. I'll post my version of it when I get home if you want it, I'm at work now.
Thanks for the offer, Terrance, but I'd like to code it out myself. That is, if I ever have the time
FAQ
"The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.
"If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.
Macs don't even have a console and we all know that macs wereAlright, thanks. I think I get it now, more or less. But, why aren't I supposed to use a Mac? WTF is that?!
programmed mostly in pascal.... The main advantage of
the macs is that the terminal emulator is pretty nice.
I can't believe this. They give me a syntax error on this code
Code:#include <iostream> using namespace std; const int NUM_SKILLS = 6; const int MAX_SKILL_VAL = 10; const int MAX_WARRIORS = 20; const int MAX_TOTAL_WARRIORS = MAX_WARRIORS * 2; double win_probability(int s[][NUM_SKILLS], int i, int j) { int I, J, IP, JP; const int MAX_DIFF = 10000; double p; I = J = IP = JP = -MAX_DIFF; for (int k = 0; k < NUM_SKILLS; ++k) { int ds = s[i][k] - s[j][k]; if (ds > IP) { IP = ds; } ds = s[j][k] - s[i][k]; if (ds > JP) JP = ds; } I = (IP >= 0)? IP : 0; J = (JP >= 0)? JP : 0; if (I + J == 0) p = 0.5; else p = I / double(I + J); return p; } void find_probabilites(double P[][MAX_WARRIORS], int s[][NUM_SKILLS], int num_warriors) { for (int i = 0; i < num_warriors; ++i) { for (int j = 0; j < num_warriors; ++j) { P[i][j] = win_probability(s, i, num_warriors + j); } } } void find_max_expected(double P[][MAX_WARRIORS], int T[], int num_warriors) { double best_val = -10000.0; int nperm = 0; int n = 0; for (int i = 0; i < num_warriors; ++i) T[i] = i; while(next_permutation(&T[0], &T[num_warriors])) { double e = 0.0; for (int i = 0; i < num_warriors; ++i) e += P[i][T[i]]; if (e > best_val) { best_val = e; nperm = n; } n++; } next_permutation(&T[0], &T[num_warriors]); // back to orig for (int i = 0; i < nperm; ++i) { next_permutation(&T[0], &T[num_warriors]); } } int main(void) { int s[MAX_TOTAL_WARRIORS][NUM_SKILLS]; double P[MAX_WARRIORS][MAX_WARRIORS]; int T[MAX_WARRIORS]; bool quit = false; int num_warriors = 0; int instance = 0; while(!quit) { cin >> num_warriors; if (num_warriors < 0 || num_warriors > MAX_WARRIORS) { cerr << "Invalid number of warriors\n"; exit(-1); } else if (num_warriors == 0) { quit = true; } else { for (int i = 0; i < num_warriors * 2; ++i) { for (int k = 0; k < NUM_SKILLS; ++k) { if (!cin) { cerr << "Invalid datafile\n"; exit(-1); } else { int n; cin >> n; if (n >= 0 && n <= MAX_SKILL_VAL) s[i][k] = n; else { cerr << "Invalid datafile\n"; exit(-1); } } } } find_probabilites(P, s, num_warriors); find_max_expected(P, T, num_warriors); cout << "Instance " << ++instance << ": "; for (int i = 0; i < num_warriors; ++i) { cout << (T[i] + 1) << " "; } cout << endl; } } return 0; }
This problem is harder than I thought since if
there 20 warriors it will try all 20! possible matches.