TopCoder Statistics - Problem Statement

Problem Statement

In this problem we consider ordered pairs of positive integers. Given such a pair, you can now make zero or more steps. In each step, you can change your pair into a new pair of integers by adding one of them to the other. That is, if your current pair is (x, y), then your next pair will be either (x+y, y), or (x, x+y).

For example, you can start with (1, 2), change it to (3, 2), change that to (3, 5), and then change that again to (3, 8).

You are given four ints: a, b, c, and d. We are looking for a pair (x, y) such that:

It is possible to start with (x, y) and end with (a, b).
It is also possible to start with the same (x, y) and end with (c, d).

The number of steps needed to reach (a, b) may be different from the number of steps needed to reach (c, d).

If there is at least one such pair (x, y), return the largest possible value of x+y. Otherwise, return -1.

Definition

Class:: PairGame
Method:: maxSum
Parameters:: int, int, int, int
Returns:: int
Method signature:: int maxSum(int a, int b, int c, int d)
(be sure your method is public)

Constraints

a will be between 1 and 1,000,000, inclusive.
b will be between 1 and 1,000,000, inclusive.
c will be between 1 and 1,000,000, inclusive.
d will be between 1 and 1,000,000, inclusive.

Examples

1

2

2

1

Returns: 2

We have (1,1) -> (1,2) and (1,1) -> (2,1).
15

4

10

7

Returns: 7

Now we have (3,4) -> (7,4) -> (11,4) -> (15,4) and (3,4) -> (3,7) -> (10,7).
1

1

10

10

Returns: -1
1000

1001

2000

2001

Returns: 1001
10944

17928

7704

21888

Returns: 144
1

1

1

1

Returns: 2
736

184

828

552

Returns: -1
788

197

197

985

Returns: 394
596

596

596

596

Returns: 1192
664

166

332

332

Returns: -1
968

88

528

880

Returns: -1
315

945

315

315

Returns: 630
640

304

376

240

Returns: -1
45

63

306

279

Returns: 18
968

880

792

176

Returns: 264
490

90

420

204

Returns: -1
888

784

152

360

Returns: 16
246

942

246

666

Returns: 12
159

371

556

699

Returns: -1
595

595

595

595

Returns: 1190
640

640

440

920

Returns: -1
476

476

476

952

Returns: 952
996

390

811

539

Returns: -1
330

195

843

897

Returns: -1
702

702

702

351

Returns: -1
460

460

460

460

Returns: 920
505568

505568

505568

505568

Returns: 1011136
6423

6423

6423

6423

Returns: 12846
5

10

5

10

Returns: 15
517241

517241

517241

517241

Returns: 1034482
5912

4288

7632

7736

Returns: 16
57590

57590

57590

57590

Returns: 115180
117972

976320

760716

65088

Returns: 8136
243720

963472

101136

179168

Returns: -1
604608

604608

604608

604608

Returns: 1209216
90528

39744

78016

23552

Returns: -1
12

32

88

12

Returns: 12
852

923

923

568

Returns: 213
9351

9351

9351

9351

Returns: 18702
50142

902556

183854

802272

Returns: -1
79

79

79

79

Returns: 158
840

483

378

546

Returns: -1
72008

72008

72008

72008

Returns: 144016
60043

60043

60043

60043

Returns: 120086
927228

120756

548262

800082

Returns: -1
43

62

75

46

Returns: 2
17

17

17

17

Returns: 34
38896

79288

81158

93126

Returns: -1
66

66

66

66

Returns: 132
54

54

54

54

Returns: 108
848

848

848

848

Returns: 1696
4140

4230

300

3470

Returns: -1
994

994

994

994

Returns: 1988
16

16

16

16

Returns: 32
582

582

582

582

Returns: 1164
552707

552707

552707

552707

Returns: 1105414
938658

871611

670470

134094

Returns: -1
61

61

61

61

Returns: 122
26

26

60

100

Returns: -1
9

9

9

9

Returns: 18
90317

90317

90317

90317

Returns: 180634
140322

870870

381654

869232

Returns: 1638
85873

85873

85873

85873

Returns: 171746
116910

961260

844350

785895

Returns: -1
9063

1855

9593

3339

Returns: 212
98475

98735

71825

86190

Returns: -1
7289

7289

7289

7289

Returns: 14578
20462

83422

27545

97588

Returns: -1
104950

104950

104950

104950

Returns: 209900
185

185

185

185

Returns: 370
30

30

60

30

Returns: 60
89208

28944

51474

7524

Returns: -1
66206

94580

9458

85122

Returns: 37832
828156

828156

828156

828156

Returns: 1656312
7800

5800

8400

9600

Returns: -1
7

7

7

7

Returns: 14
19932

77916

4228

15100

Returns: -1
98399

98399

98399

98399

Returns: 196798
66

12

36

54

Returns: -1
2920

27590

67760

9110

Returns: 30
900274

450137

450137

450137

Returns: 900274
337413

430740

366129

524067

Returns: 14358
5544

6600

7788

6006

Returns: -1
303677

303677

303677

303677

Returns: 607354
18

34

9

90

Returns: -1
499

499

499

499

Returns: 998
6

6

6

6

Returns: 12
18410

67253

98370

8581

Returns: 3
2067

2067

2067

2067

Returns: 4134
7200

3600

7200

7200

Returns: -1
546295

218518

546295

109259

Returns: 218518
52248

731472

409276

104496

Returns: -1
9586

9586

9586

9586

Returns: 19172
8

4

10

48

Returns: -1
60788

5010

30227

51436

Returns: -1
61584

61584

61584

61584

Returns: 123168
6106

3124

1988

5964

Returns: -1
76422

76422

76422

76422

Returns: 152844
22800

54800

58200

48300

Returns: -1
8

8

8

8

Returns: 16
842450

842450

842450

842450

Returns: 1684900
6014

6014

6014

6014

Returns: 12028
49227

49227

98454

98454

Returns: -1
978129

978129

978129

978129

Returns: 1956258
295800

887400

347072

173536

Returns: -1
1

1000000

1

6

Returns: 7
1

1000000

1000000

1

Returns: 2
1000000

1

1

1000000

Returns: 2
1000000

1

500000

1

Returns: 500001
1000000

1

999999

2

Returns: 2
1000000

1

1000000

1

Returns: 1000001
2

1

4

2

Returns: -1
1000000

999999

1000000

999999

Returns: 1999999
1

1000000

1

10000

Returns: 10001
100

1

100

1

Returns: 101
1

1000000

1000000

2

Returns: -1
1

1000000

2

1000000

Returns: -1
2

2

4

4

Returns: -1
1000000

3

1000000

1

Returns: 2
1000000

1

1

1

Returns: 2
1

1000000

1000000

999983

Returns: 2
2

5

2

5

Returns: 7
999998

999999

999999

999999

Returns: -1
29

37

3

5

Returns: 2
1

999999

999999

1

Returns: 2
7

10

7

3

Returns: 10
1

1000000

1

1000000

Returns: 1000001
9999

1

10000

1

Returns: 10000
1

1

1

1000

Returns: 2
1

1

10

5

Returns: -1
6

6

2

2

Returns: -1
1000000

2

1

1000000

Returns: -1
2

2

2

1

Returns: -1
12345

94321

9153

15124

Returns: 7
2

999999

2

1000000

Returns: -1
10

10

1

2

Returns: -1
8

5

55

89

Returns: 13
1

1000000

999999

1000000

Returns: 2
100

5

100

5

Returns: 105
1000000

999999

999999

1000000

Returns: 2
1

1

1000000

999998

Returns: -1
1000000

1

1000000

2

Returns: -1
2

1000000

3

1000000

Returns: -1
3

5

46368

770545

Returns: 8
25

16

12

29

Returns: 7

Statistics

Problem Statement for "PairGame"

Problem Statement

Definition

Constraints

Examples