Prank

SRM 384 · 2007-12-19 · by lovro

SRM 384 · 2007-12-19 · by lovro · Simple Math

Show categories

Class Name: Prank

Return Type: int[]

Method Name: realWeight

Arg Types: (int)

Problem Statement

Jane tries her best to stay fit. Knowing this, her sister decided to play a prank on Jane: after Jane's old scale broke down, her sister got her a new scale that shows the square of a person's weight, instead of the real weight.

Not noticing the change, Jane has been using the scale for a while. One morning she screamed "Oh no! I gained apparentGain pounds!". Given an int apparentGain (the difference between the square of Jane's current weight and the square of her previous weight), return a int[] containing Jane's possible real weights after the latest measurement, sorted in ascending order.

All weights (displayed and real, previous and current) are positive integers.

Constraints

apparentGain will be between 1 and 100000, inclusive.

Examples

233
Returns: {117 }

If Jane had previously weighed 116 pounds, the scale would have shown 116^2 = 13456. If she gained 1 pound, the scale would show 117^2 = 13689, for an apparent gain of 13689 - 13456 = 233.

15
Returns: {4, 8 }

Assuming in this example Jane is actually a small animal, she could have gone from 1 to 4 or from 7 to 8.

1440
Returns: {38, 39, 42, 46, 49, 53, 66, 77, 94, 123, 182, 361 }

100000
Returns: {325, 350, 550, 665, 1025, 1270, 2510, 3133, 5005, 6254, 12502, 25001 }

This is the largest input.

93301
Returns: {3595, 46651 }

Watch out for overflow!

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

Coding Area

Language: C++17 · define a public class Prank with a public method vector<int> realWeight(int apparentGain) · 69 test cases · 2 s / 256 MB per case