We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Tower Breakers - The Final Battle

Tower Breakers - The Final Battle

Problem
Submissions
Leaderboard
Discussions
Editorial

Our unsung tower-breaking heroes (players and ) only have one tower left, and they've decided to break it for a special game commemorating the end of days of Game Theory! The rules are as follows:

  • always moves first, and both players always move optimally.
  • Initially there is tower of height .
  • The players move in alternating turns. The moves performed by each player are different:
    1. At each turn, divides the current tower into some number of smaller towers. If the turn starts with a tower of height and breaks it into smaller towers, the following condition must apply: , where denotes the height of the new tower.
    2. At each turn, chooses some tower of the new towers made by (where ). Then must pay coins to . After that, gets another turn with tower and the game continues.
  • The game is over when no valid move can be made by , meaning that .
  • 's goal is to pay as few coins as possible, and 's goal is to earn as many coins as possible.

Can you predict the number of coins that will earn?

Input Format

The first line contains a single integer, , denoting the number of test cases.
Each of the subsequent lines contains a single integer, , defining the initial tower height for a test case.

Constraints

Output Format

For each test case, print a single integer denoting the number of coins earned by on a new line.

Sample Input

3
4
2
7

Sample Output

6
4
8

Explanation

Test Case 0:
Our players make the following moves:

    1. splits the initial tower into smaller towers of sizes and .
    2. chooses the first tower and earns coin.
    1. splits the tower into smaller towers of sizes and .
    2. chooses the first tower and earns coin.
    1. splits the tower into smaller towers of size .
    2. chooses the second tower and earns coins.

The total number of coins earned by is , so we print on a new line.

Author

allllekssssa

Difficulty

Medium

Max Score

50

Submitted By

1169

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy