KTH Challenge 2020


2020-04-25 01:00 AKDT

KTH Challenge 2020


2020-04-25 05:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -182 days 13:41:38

Time elapsed


Time remaining


Problem A
AI Jeopardy

Picture by QIHAN Technology
The robot revolution is finally here, albeit not quite in the highly explosive way envisioned in various science fiction books and movies. It seems that, perhaps due to a small typo in the AI source code, the robots are not taking our lives but instead taking our livelihoods. One early job market fatality in this revolution was the (somewhat niche) occupation as jeopardy player: already in 2011 the Watson computer defeated two legendary but inferior human jeopardy champions.

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 consists of a single integer $X$ ($1 \le X \le 10^{100}$).


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
5 2
Sample Input 2 Sample Output 2
2020 1
Sample Input 3 Sample Output 3
0 0