Connection Status:
Competition Arena > MaximumMoves

MaximumMoves

SRM 770 · 2019-10-31 · by lazy_fox

SRM 770 · 2019-10-31 · by lazy_fox · Brute Force, Simple Math
Class Name: MaximumMoves
Return Type: long
Method Name: getMaximumMoves
Arg Types: (long long, long long)
Problem Statement

Problem Statement

You are given two nonnegative integers P and Q. Your task is to make the integers equal in as many steps as possible. In each step you can do one of two things:

  • Add any prime number to P.
  • Subtract any prime number from Q.

If it's not possible to make P and Q equal, return -1. Otherwise, return a nonnegative integer: the maximum (not minimum!) number of steps you can make.

Notes

  • Primes are positive integers with exactly two positive integer divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, ...
  • In particular, the numbers 0 and 1 are not prime numbers.

Constraints

  • P will be between 0 and 10^18, inclusive.
  • Q will be between 0 and 10^18, inclusive.
Examples
0)
5
9
Returns: 2

In one optimal solution we first subtract 2 from Q and then add 2 to P. After these two steps both numbers are equal (both are 7).

1)
5
10
Returns: 2

In one optimal solution we first subtract 2 from Q and then add 3 to P. After these two steps both numbers are equal (both are 8).

2)
5
6
Returns: -1

There's no way to make these P and Q equal.

3)
10
2
Returns: -1
4)
1000000000
121212121212451
Returns: 60605560606225

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

Coding Area

Language: C++17 · define a public class MaximumMoves with a public method long long getMaximumMoves(long long P, long long Q) · 46 test cases · 2 s / 256 MB per case

Submitting as anonymous