First, congrats for those who manage to solve the question. I didn't manage
that with literally every single formula derived wrongly.
BTW, after fixing those formulas and applying the ideas from the analysis, I
have the file at the bottom of the message.
What confuse me is the time to run the solution. It takes about 6 minutes in my
i7-4790, and most of the time of course goes to the debuff simulation which is
O(n) where n = knight_attack / debuff. I've double checked that my binary is
compiled with -O2.
It means: if I am to run the code in a slower computer (e.g. an AMD E-350), the
code will fail the time limit.
I've also timed Eryx's solution in my computer. It's a bit faster than my
solution here, but only faster for less than a minute, so the big picture is
still the same. Didn't try the other six solutions, but they all appear to do
the same simulation as Eryx, so the time needed to run shouldn't be very
surprising.
So I'll put my questions here:
(1) is there a better algorithm to do this?
(2) did anyone tried using multiple threads? (This should run 4 times faster in
the i7-4790, but note that my E-350 is 20 times slower than the i7-4790, so
threading likely won't help.)
(3) DID ANYONE HAVE THE TIMER EXPIRED ONLY BECAUSE YOU'RE USING A SLOWER CPU?
If yes please post up here.
Regards,
WC Leung.
(p.s. I still managed to get to round 2. So see you there!)
// Compile with MinGW-64 (6.3.0) in MSYS2
// Compile switches: -std=c++11 -Wall -Wconversion -Werror
#include <stdint.h>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int64_t maxint = 20000000000ll;
int64_t DivCeiling(int64_t n, int64_t d) {
return (n-1) / d + 1;
}
int64_t GetTurnsWithBuff(int64_t hit, int64_t attack, int64_t buff, int64_t
buff_turns) {
return buff_turns + DivCeiling(hit, attack + buff * buff_turns);
}
struct DataAfterDebuff {
int64_t hit;
int64_t attack;
int64_t turns;
};
DataAfterDebuff GetDataAfterDeBuff(DataAfterDebuff original_data, int64_t hit,
int64_t debuff, int64_t debuff_turns) {
DataAfterDebuff data = original_data;
for (int64_t i = 0; i < debuff_turns; ++i) {
data.turns ++;
data.attack -= debuff;
if (data.attack < 0) {
data.attack = 0;
return data; // unable to kill
}
data.hit -= data.attack;
if (data.hit <= 0) {
data.turns++;
data.hit = hit - data.attack - data.attack - debuff;
}
}
return data;
}
void solve(int caseNo) {
std::cout << "Case #" << caseNo << ": ";
int64_t d_hit, d_attack, k_hit, k_attack, buff, debuff;
cin >> d_hit >> d_attack >> k_hit >> k_attack >> buff >> debuff;
int64_t attack_turns = maxint;
for (int64_t i = 0; i+1 < attack_turns; ++i) {
int64_t new_attack_turns = GetTurnsWithBuff(k_hit, d_attack, buff, i);
if (new_attack_turns > attack_turns)
break;
attack_turns = std::min(attack_turns, new_attack_turns);
}
if ((attack_turns > 1 && (k_attack - debuff) >= d_hit) ||
(attack_turns > 2 && (k_attack * 2 - debuff * 3) >= d_hit)) {
cout << "IMPOSSIBLE" << "\n";
return;
}
int64_t debuff_turns = 0;
int64_t real_turns = maxint;
int64_t endurance = 0;
DataAfterDebuff data = {d_hit, k_attack, 0};
for ( ; ; ) {
// if debuff_turns > 0, get the turns needed for the next endurance.
int64_t max_attack = endurance > 0 ? DivCeiling(d_hit, endurance) - 1
: maxint;
debuff_turns = debuff > 0 ? std::max(0ll, DivCeiling(k_attack -
max_attack, debuff))
: 0;
data = GetDataAfterDeBuff(data, d_hit, debuff,
debuff_turns > 0 ? debuff_turns - (k_attack -
data.attack) / debuff : 0);
//cout << data.hit << ' ' << data.attack << ' ' << data.turns << '\n';
int64_t current_turns;
if (data.attack <= 0 || DivCeiling(data.hit, data.attack) >=
attack_turns) {
current_turns = data.turns + attack_turns;
endurance = data.attack <= 0 ? maxint : DivCeiling(d_hit,
data.attack);
}
else {
int64_t first_attack_turns = DivCeiling(data.hit, data.attack) - 1;
int64_t remaining_attack_turns = attack_turns - first_attack_turns;
endurance = DivCeiling(d_hit, data.attack);
if (endurance < 3)
continue;
int64_t heal_turns =
remaining_attack_turns < 2
? 1
: (remaining_attack_turns - 2) / (endurance - 2) + 1;
current_turns = data.turns + attack_turns + heal_turns;
}
real_turns = std::min(real_turns, current_turns);
if (data.attack <= 0 || debuff == 0)
break;
}
cout << real_turns << "\n";
}
int main(int argc, char** argv) {
int N;
std::cin >> N;
std::string str;
std::getline(std::cin, str);
for (int i = 0; i < N; ++i) {
solve(i + 1);
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To post to this group, send email to google-code@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/4b883d47-553f-4049-ba1a-7b44e6ae991d%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
