hi_cf's blog

How to solve this problem(1) ..?
By hi_cf, 12 years ago, In English

The beauty of a number X is the number of 1s in the binary representation of X.

Two players are plaing a game. There is number n written on a black board. The game is played as following:

Each time a player chooses an integer number (0 <= k) so that 2^k is less than n and (n-2^k) has as beautiful as n. Next he removes n from blackboard and writes n-2^k instead. The player that can not continue the game (there is no such k that satisfies the constrains) looses the game.

The First player starts the game and they play in turns alternatively. Knowing that both two players play optimally you have to specify the winner.

Input:

First line of the Input contains an integer T, the number of testcase. 0 <= T <= 5.

Then follow T lines, each containing an integer n.

n more than 0 and less than 10^9 +1.

Output

For each testcase print "First Player" if first player can win the game and "Second Player" otherwise.

Sample Input

7

1

2

8

16

42

1000

123

Sample Output

Second Player

First Player

First Player

Second Player

Second Player

First Player

Second Player

Explanation

In the first example n is 1 and first player can't change it so the winner is the second player.

In the second example n is 2, so the first player subtracts 1 (2^0) from n and the second player looses the game.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone Please ..

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    As k is small (less than 30) and the number of allowed moves for each n is rather small too (if ith bit of n is 1, you can't subtract 2^i; also not all "zeroes" are available too), the overall amount of states (n,k) you can obtain can be also not so big, so you can try dp on map.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I implemented your idea , but i am getting TLE .

      Code

      http://ideone.com/bo1Ma2

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        And what is TL for this problem? Maybe optimizing of calculating the beauty can help you — you can also precalc it for all numbers up to 10M, for example.

        UPD. If you go only into zeroes which stand immediately after ones, as riadwaw said, it doesn't get TLE in Ideone: http://ideone.com/oK0fwy

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I improved it to 0.25 Sec by breaking for loop in solve() immediately after i found a losing position . http://ideone.com/3OERdw

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            That's cool:) Does it decrease the amount of overall states in 20 times?..

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        It's possible to use unordered_map, it may be faster.

        Doesn't help

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Usually solution to this type of problem goes like this: Do DP for numbers 1 — 200, print solutions and find pattern.

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You should only choose 0-s that are after 1-s, after that you sholdn't calculate beauty.

Ex:

100 - 010 = 010 OK. 1 moved right
100 - 001 = 011 bad, 1 moved to choosen 0 and all digits between them became 1s
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    After that it seems, it's not important how game are played and answer only depends of pairity (sum_of_number_of_position_of_ones — sum(0...n — 1)) where n is the number of ones.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "You should only choose 0-s that are after 1-s"

    Why should we leave other possible moves ..??

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See, if we choose 1, it's disappered. It's bad.

      If we choose 0 consider nearest 1 on the left.

      (first)100000(second)
            ^ choose it

      After subtraction it will look like

      (first)011111(second)

      one 1 is disappeared, and [distance between chosen pos and pos of this 1] of 1's appered. So distance should be 1.

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

actually choosing such k where (n-2^k) have the same beauty that means moving one of 1's bits one step to right for example let n=1000100 (in binary) you can either choose k=1 then n-2^k=1000010 or k=5 so n-2^k=0100100, there is no anothor valid value for k in the position.

I think the problem is too easy now :)

→ Reply