Problem F
AI Jeopardy
Nowadays, more and more of Jeopardy’s viewers are AIs themselves and as such the show is considering having categories on topics that are more popular with this new number-crunching viewer base. Focus group testing has revealed that AIs are particularly fond of the “Binomial Coefficients” category. The premise of this category is that the answer that contestants get is some positive integer $X$, and the contestants must respond with a question of the form “What is $n$ choose $k$?” (and this is a correct response if the binomial coefficient $n$ choose $k$ equals $X$).
Write an AI to play this new Jeopardy category. If there are several different possible solutions for $n$ and $k$, the AI should choose the most elegant solution, having the smallest value of $n$, and of those with the smallest $n$ it should choose the one with the smallest value of $k$.
Input
Input consists of a single integer $X$ ($1 \le X \le 10^{100}$).
Output
Output two non-negative integers $n$ and $k$ such that the binomial coefficient $n$ choose $k$ equals $X$, with ties between multiple solutions broken as explained above.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 |
5 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2020 |
2020 1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 |
0 0 |
