Connection Status:
Competition Arena > AliceGameEasy

AliceGameEasy

SRM 639 · 2014-08-25 · by dreamoon

SRM 639 · 2014-08-25 · by dreamoon · Greedy
Class Name: AliceGameEasy
Return Type: long
Method Name: findMinimumValue
Arg Types: (long long, long long)
Problem Statement

Problem Statement

Alice and Kirito just played a game. The game consisted of a finite (possibly empty) sequence of turns. You do not know the exact number of turns. The turns were numbered starting from 1. In each turn, exactly one of our two players won. The winner of turn i scored i points.

You are given two longs x and y. Find out whether it is possible that at the end of the game Alice had exactly x points and Kirito had exactly y points. If it is possible, return the smallest number of turns Alice could have won. If the given final result is not possible, return -1 instead.

Constraints

  • x and y will be between 0 and 1,000,000,000,000(10^12), inclusive.
Examples
0)
7
14
Returns: 2

This final result is possible. One possibility is that Alice won turns 1, 2, and 4 (for 1+2+4 = 7 points) and Kirito won turns 3, 5, and 6 (for 3+5+6 = 14 points). However, there are also some other possibilities in which Alice only won two of the six turns, so the correct answer is 2.

1)
10
0
Returns: 4

There must have been four turns and Alice must have won all four of them.

2)
932599670050
67400241741
Returns: 1047062

Watch out for integer overflow.

3)
7
13
Returns: -1
4)
0
0
Returns: 0

Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AliceGameEasy with a public method long long findMinimumValue(long long x, long long y) · 65 test cases · 2 s / 256 MB per case

Submitting as anonymous