Facebook Hacker Cup 2011 Round 3B

Discussion in 'Rebol' started by MaxV, Feb 11, 2011.

  1. MaxV

    MaxV Member

    Diminishing Circle
    N people are standing in circle and play following game: they start with the first person, count K people clockwise, then the K+1-th person leaves the circle and the process starts all over, using the person clockwise of the last person removed as the starting point.

    For example when N = 9 and K = 3 people would leave in following order: 4, 8, 3, 9, 6, 5, 7, 2

    Given N and K, find who wins the game if counting starts with person 1. Person indices are 1-based.

    The last person who is left is declared the winner.

    Input
    The input consists of a single integer T, the number of test cases. This is followed by T pairs of numbers N and K, all separated by whitespace.

    Output
    Print T whitespace-separated integers, the indices for each test case of the winner of the game.

    Constraints
    T = 20
    1 ≤ N ≤ 10^12
    1 ≤ K ≤ 10^4

    Example input
    Code:
    5
    9 3
    4 1
    3 2
    5 4
    6 9
    
    Example output
    Code:
    1
    1
    2
    2
    2
    
    File input:
    http://www.maxvessi.net/rebsite/fhc2011/diminishing_circle.txt

Share This Page