Tuenti Programming
Challenge 2

Go to tuenti

  Home  Info  Questions  Stats       

Challenge 2: The binary granny « Prev Next »

Completion time: min: 0:15 h
10 percentile: 0:47 h
90 percentile: 24:05 h
max: 133:54 h
Submit exec time: min: 0.21 s
10 percentile: 0.70 s
90 percentile: 4.26 s
max: 41870.53 s
Test tries: min: 1
10 percentile: 1
90 percentile: 19
max: 139
# of completions:312

Yuki is a lucky girl. Her grandma Chika is a lovely old lady, owner of a sheep farm, expert baker and knitting ninja, and has a hazelnut tree in her backyard. Yuki is always craving the super tasty hazelnuts that can be picked from it and asking for more and more. But her grandma is a wise woman and she doesn’t want to spoil Yuki or to make her sick with all the hazelnuts she can eat.

Chika is quite a fan of binary numbers and uses base 2 for everything (and I can assure you she has never been cheated when buying groceries). She came up with the following simple game for Yuki: she would say a number N and Yuki would choose two numbers, x and y, such that x + y = N. Then Chika would give Yuki as many hazelnuts as the sum of the number of ones of x and y in base 2. For example, if Chika chooses 7 and Yuki picks 3 and 4, then she will get 2 (as 3 in base 2 is 11) plus 1 (since 4 in base 2 is 100): 3 hazelnuts.

Yuki wants to know what the maximum number of hazelnuts that she could get from Chika.


The first line of the input gives the number of test cases, C, and C test cases follow. Each test case consists of a line with an integer N, 0 ≤ N.


For each test case, output one line containing "Case #x: M", where x is the case number (starting from 1) and M is the maximum number of hazelnuts that Yuki can get from her binary grandmother.


1 ≤ C ≤ 2000
Test dataset: N ≤ 104
Challenge dataset: N ≤ 1019 (may not fit in a 32 bit integer)

Sample input


Sample output

Case #1: 1
Case #2: 4
Case #3: 14