Training Site
Sideways banner

Betty the Cat 2

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

Betty the cat has started going to the gym and is looking to grow her muscles. To help with her bulk, she has bought two types of creatine-filled cookie boxes: ones with A cookies per box, and ones with B cookies per box. Betty has an infinite number of these. When she opens a cookie box, she is morally obligated to eat all the cookies in the box.

Betty has a target cookie quota of K cookies a day. She wants to know: what is the closest amount she can get to her target cookie quota, and what is the minimum number of boxes she needs for this amount.

Note: If you're using a type-sensitive language such as C, C++, C# or Java, you should use 64-bit integer types to prevent integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.


The input will contain three space-separated integers A, B and K on a single line.


Output two numbers separated by a space - the smallest possible absolute difference between target and actual cookies consumed, and the minimum number of cookie boxes required to achieve this.


For all subtasks:

  • 1 \le A, B \le 1{,}000
  • 1 \le K \le 10^{18}


  • Subtask 1 (+10%): A = 1 and K \le 100{,}000
  • Subtask 2 (+25%): A = B and K \le 100{,}000
  • Subtask 3 (+40%): K \le 100{,}000
  • Subtask 4 (+25%): No further constraints.

Sample Explanation

  • In Sample 1, if Betty eats two boxes of two cookies and two boxes of three cookies, she meets her quota of ten cookies exactly. So, she is zero cookies off her quota and can achieve this with four boxes of cookies. This is the minimum amount of boxes possible.
  • In Sample 2, the best Betty can do is eat no cookies. This puts her three cookies off her quota of three.
  • In Sample 3, the best Betty can do is eat three boxes of eight cookies, totaling 24 cookies. This puts her one cookie off her quota of 23 cookies.
  • Sample Input 1

    2 3 10

    Sample Output 1

    0 4
  • Sample Input 2

    19 6 3

    Sample Output 2

    3 0
  • Sample Input 3

    8 8 23

    Sample Output 3

    1 3