Under construction

Still being built. Things may change

Round Robin

Interview

Time limit1sMemory limit128 MB

Summary
Simulate rounds of T turns around the circle, remove the player who takes the last turn, and report the survivors and their shared count when the rest tie.
Level

Easy3 of 10

Topics
Simulation
Solved
No attempts yet

Problem

NN players sit in a fixed order and take turns one at a time. The first player follows the last one, so turns keep going around the circle. Every player counts the turns he or she has taken.

The game runs in rounds. One round consists of exactly TT turns, and when a round ends, the player who just took a turn leaves the game. If every remaining player has the same count at that moment, the game is over. Otherwise a new round of TT turns starts with the player immediately after the one who just left.

When a single player remains, there is nobody to compare with, so the counts are treated as equal and the game is over.

Here is how a game with N=5N = 5 and T=17T = 17 plays out. Label the players A, B, C, D and E in order, with every count starting at zero.

PlayerABCDE
Count00000

Starting with A, 17 turns are taken. B takes the last of them.

PlayerABCDE
Count44333

B leaves the game, and the next turn goes to C.

PlayerACDE
Count4333

After 17 more turns starting with C, players A, D and E gain 4 turns each, while C gains 5 including the last one.

PlayerACDE
Count8877

C leaves. The remaining counts are not all equal, so a new round begins with D.

PlayerADE
Count877

The 17 turns starting with D end with E. A gains 5 turns, D and E gain 6 each.

PlayerADE
Count131313

Then E leaves.

PlayerAD
Count1313

The two remaining players both have a count of 13, so the game ends. E's count does not enter that decision.

Input

The input contains one or more datasets. Each dataset is a single line holding two integers NN and TT separated by a space. NN (2≤N≤1002 \le N \le 100) is the initial number of players, and TT (2≤T≤1002 \le T \le 100) is the number of turns taken in one round. The line after the last dataset contains only 00.

Output

For each dataset print one line with two integers pp and cc separated by a space. At the moment the game ends, pp is the number of players still in the game and cc is the count they all share.

Examples1

  1. Example 1

    Input
    5 17
    7 10
    90 2
    0
    
    Expected output
    2 13
    5 3
    45 1