I was attempting a question on SPOJ in which i was required to precompute Cube Root. I approached via binary search method but I am getting wrong answer while checking if given no. is integer or double.
I followed this
if (ceil(num) == floor (num)) //integer
but I am getting wrong answer in floor (num),
for example: 27 (floor = 2, ceil = 3), 125 (floor = 4, ceil = 5)
Here is the code.
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#define Size 1000001
//vector for storing positions
std::vector<int> pos;
//function for calculating cube root
double cubeRoot(int n) {
double low = 0;
double high = (double)n;
for (int i = 0; i < 50; ++i) {
double mid = (low + (high - low) / 2.0);
if (mid * mid * mid > n) high = mid;
else low = mid;
}
//std::cout << " low : " << low << " , high : " << high << '\n';
return low;
}
int main () {
std::ios_base::sync_with_stdio(0);
std::cout.tie(0);
std::cin.tie(0);
//resized according to the question requirement
pos.resize(Size, 0);
pos[1] = 1;
int currentPosition = 2; //variable to store the current position.
for (int i = 2; i <= Size; i++) {
double ans = cubeRoot(i);
//std::cout << i << ' ' << std::setprecision (10) << ans << ' ' << floor(ans) << ' ' << ceil(ans) << '\n';
if (ceil (cubeRoot(i)) == floor (cubeRoot(i))) {
pos[i] = -1;
currentPosition --;
}
else {
pos[i] = 1 + currentPosition;
currentPosition ++;
}
}
int testCase;
std::cin >> testCase;
for (int test = 1; test <= testCase; ++test) {
int num;
std::cin >> num;
//Output format
std::cout << "Case " << test << ": ";
if (pos[num] == -1) std::cout << "Not Cube Free\n";
else std::cout << pos[num] << '\n';
}
}
Aucun commentaire:
Enregistrer un commentaire