Try the following test case
Input
*1*
*0 536870911*
Expected output:
*Case #1: NNNNNNNNNNNNNNNNNNNNNNNNNNNNN*
The problem is that for the case above, *min_jumps* should be *29*
However, due to floating point precision error, your *min_jumps* is rounded
up to *30*
The following code will fix the problem
*long long total_distance = std::abs(x_goal) + std::abs(y_goal);*
*int min_jumps = 0;*
*while (total_distance) {*
* min_jumps++;*
* total_distance >>= 1;*
*}*
--------------
Full passing solution:
*#include <algorithm>*
*#include <cmath>*
*#include <functional>*
*#include <iostream>*
*#include <map>*
*#include <set>*
*#include <string>*
*#include <vector>*
*int main()*
*{*
* int testCaseCount = 0;*
* std::cin >> testCaseCount;*
* for (int t = 0; t < testCaseCount; ++t)*
* {*
* long long x_goal = 0;*
* long long y_goal = 0;*
* std::cin >> x_goal >> y_goal;*
* auto IsValidCoord = [](long long x, long long y)*
* {*
* return (std::abs(x) % 2) != (std::abs(y) % 2);*
* };*
* bool possible = IsValidCoord(x_goal, y_goal);*
* std::string solution;*
* if (possible)*
* {*
* long long total_distance = std::abs(x_goal) + std::abs(y_goal);*
* int min_jumps = 0;*
* while (total_distance) {*
* min_jumps++;*
* total_distance >>= 1;*
* }*
* std::vector<long long> jumps;*
* for (int i = 0; i < min_jumps; ++i)*
* {*
* jumps.push_back(1LL << i);*
* }*
* long long current_x = x_goal;*
* long long current_y = y_goal;*
* for (; !jumps.empty(); )*
* {*
* // Last move must be in E/W direction*
* if (std::abs(current_x) > std::abs(current_y))*
* {*
* if (current_x > 0)*
* {*
* solution.insert(solution.begin(), 'E');*
* current_x -= jumps.back();*
* }*
* else*
* {*
* solution.insert(solution.begin(), 'W');*
* current_x += jumps.back();*
* }*
* }*
* // Last move must be in N/S direction*
* else {*
* if (current_y > 0) {*
* solution.insert(solution.begin(), 'N');*
* current_y -= jumps.back();*
* }*
* else {*
* solution.insert(solution.begin(), 'S');*
* current_y += jumps.back();*
* }*
* }*
* jumps.pop_back();*
* }*
* }*
* std::cout << "Case #" << t + 1 << ": " << (possible ? solution :
"IMPOSSIBLE") << "\n";*
* }*
* 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 view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/a6d442fb-5d6c-4602-aff9-c2e2a5464554%40googlegroups.com.
