TopCoder Statistics - Problem Statement

Problem Statement

Bunnies like programming and they sometimes make useless devices.

One group of bunnies made a device called Converter. Converter has two fixed integers, n and z, and works as follows:

It receives a card on which an integer x is written. This card will not be returned.
It selects an integer y between 1 and n, inclusive, such that x + y^2 + z^3 is a multiple of n. If there is more than one such y, Converter allows the user to choose exactly one of them. If there is no such y, Converter will break and will never be usable again.
It returns a card on which the integer y is written.

Initially you have a card on which an integer start is written. Your goal is to get a card on which an integer goal is written. Return the minimum number of times you must use Converter in order to achieve the goal. If it is impossible to get such a card, return -1 instead.

Definition

Class:: BunnyConverter
Method:: getMinimum
Parameters:: int, int, int, int
Returns:: int
Method signature:: int getMinimum(int n, int z, int start, int goal)
(be sure your method is public)

Constraints

n will be between 1 and 500,000, inclusive.
z, start and goal will each be between 1 and n, inclusive.

Examples

5

1

5

3

Returns: 1

By using Converter once for a card with 5, you can choose 2 or 3 as y. For example, y = 3 can be chosen because 5 + 3^2 + 1^3 = 15 is a multiple of 5.
5

1

5

1

Returns: 2

By using Converter once for a card with 5, you can choose 2 or 3 as y. By using Converter once for a card with 3, you can choose 1 or 4 as y.
6

2

3

4

Returns: -1

You will never get a card with 4.
7

7

7

7

Returns: 0
499979

499979

499976

3

Returns: 249988
1

1

1

1

Returns: 0
2

1

1

2

Returns: 1
2

2

1

2

Returns: -1
2

2

2

2

Returns: 0
3

3

1

2

Returns: -1
3

3

2

1

Returns: 1
4

1

4

1

Returns: -1
500000

500000

500000

500000

Returns: 0
500000

19

17372

2

Returns: 6252
499979

499979

79820

3

Returns: 249987
499979

499979

499970

3

Returns: 1
499979

44929

499976

3

Returns: 124994
499559

499559

499557

2

Returns: 249778
251263

251263

246942

4321

Returns: 6210
289889

289889

52715

197000

Returns: 7541
422537

422537

90657

12338

Returns: 16160
163601

86663

75699

7467

Returns: 561
317717

317717

202497

30099

Returns: 1444
280811

280811

139851

210088

Returns: 14038
291509

249987

48928

29380

Returns: 189
109367

109367

97140

101740

Returns: -1
307009

20096

6325

250706

Returns: 130
212029

25385

198218

167015

Returns: -1
231893

231893

165849

44123

Returns: 19324
285697

256524

63069

77882

Returns: -1
383261

136783

140193

362113

Returns: 352
161267

161267

30024

27690

Returns: 3122
331973

331973

202016

298264

Returns: -1
403667

72555

216153

134524

Returns: 23
292025

60317

272338

261565

Returns: 49
426649

426649

212839

208445

Returns: 785
323849

323849

182551

246259

Returns: 884
242167

24153

24386

164985

Returns: 63
466652

230375

68757

209034

Returns: 1109
374107

374107

31387

120038

Returns: 83
275137

275137

241283

246477

Returns: 136
175611

175611

40641

36144

Returns: 65
360971

234798

189624

247187

Returns: 281
168307

168307

151428

110743

Returns: 98
29099

29099

9404

4835

Returns: 409
436528

436528

255888

123336

Returns: 4545
26453

24851

15969

11362

Returns: 14
463311

118732

25639

162492

Returns: 17
11

3

3

10

Returns: 2
477702

425218

261376

80424

Returns: 119
5540

3746

1088

4586

Returns: 31
1483

1198

919

903

Returns: -1
13333

3804

8829

8273

Returns: 26
1760

1149

42

28

Returns: 4
4331

2624

154

3392

Returns: -1
499979

478979

499976

3

Returns: -1
500000

500000

521

50000

Returns: -1

Statistics

Problem Statement for "BunnyConverter"

Problem Statement

Definition

Constraints

Examples