Hey i tried the code using DP but the solution is not being accepted ,
the code works for the sample test cases and any other test case that i can think of .
Please help
Here is the link to my code : https://www.codechef.com/viewsolution/14492082
My solution is a bit different and is very short if you are using C++ and stl as your tool to solve the problem
It uses a greedy approach to find the nearest value just smaller than or equal to n from the menu list.
while (n > 0) {
long nearest = upper_bound(menuList.begin(), menuList.end(), n) - menuList.begin();
n -= menuList[nearest - 1];
++count;
}
Here menuList is an array of the powers of 2 up to the required item - [1,2,4,8…]
I am not familiar with Python but it seems that you are using file for input. You should read from the standard input and output to the standard output.
I actually am using standard input. It reads from an input file on my computer (for testing), but if that file doesn’t exist (when I submit) it uses raw_input() instead. I’ve tested this method on the codechef judge and it works for other problems, so I don’t understand why it gets runtime error now.
That doesn’t make sense… bin is a built-in function, how could it not be defined? I thought it must be something with the input because this solution CodeChef: Practical coding for everyone got accepted.
You will be angry, but your code works - CodeChef: Practical coding for everyone , is there problem with whitespace, PY is “whitespace sensitive”, isn’t it?
That link doesn’t work, but I see that you got my solution accepted. So I tried it myself and got runtime error CodeChef: Practical coding for everyone. (this is the exact same code that you got accepted, right?) And yeah, python is whitespace-sensitive, but I don’t see how that could be the problem because the solution I posted above got accepted. Something really weird is going on…
for _ in range(int(input())):
p = int(input())
c = 0
if p<=2048:
print(bin(p).replace("0b","").count('1'))
continue
else:
c = p//2048
p = p - 2048*(c)
print(c + bin(p).replace("0b","").count('1'))