#P8012. Gold Coins Partition

    ID: 21196 Type: Default 1000ms 256MiB

Gold Coins Partition

Gold Coins Partition

A pile of gold coins is given. A person partitions the coins as evenly as possible into N groups and takes one of the groups, leaving O coins behind. The phrase "as evenly as possible" means that the coins are divided into N piles such that:

  • Each pile contains an integer number of coins.
  • The difference between the coin counts of any two piles does not exceed 1.

It is guaranteed that the person takes one of the smallest piles. In other words, if the coins are distributed such that some piles have \( k \) coins and the remaining \( r \) piles have \( k+1 \) coins (where \( 0 \le r < N \) and \( k = \lfloor X/N \rfloor \)), the taken pile has \( k \) coins. Given the numbers N and O, please determine the minimum and maximum possible number of coins \( X \) that could have originally been present.

The relation can be expressed as:

[ X - \lfloor X/N \rfloor = O ]

Let \( k = \lfloor X/N \rfloor \). Then \( X = O + k \) and we have the constraint:

[ k(N-1) \le O < k(N-1) + N ]

If we denote:

[ k_{\min} = \left\lfloor\frac{O-N}{N-1}\right\rfloor + 1, \quad k_{\max} = \left\lfloor\frac{O}{N-1}\right\rfloor, ]

then the answers are:

[ X_{\min} = O + k_{\min}, \quad X_{\max} = O + k_{\max}. ]

</p>

inputFormat

The input contains two integers N and O separated by space, where N is the number of groups and O is the number of coins left after one group is taken.

outputFormat

Output two integers separated by a space: the minimum and maximum possible total number of coins \( X \) that could have originally been present.

sample

2 5
9 10