TopCoder Statistics - Problem Statement

Problem Statement

For Fox Ciel it is the beginning of a new school year. Her school year will consist of two semesters. The first semester contains d1 days and the second semester contains d2 days. Surprisingly, there are no breaks during or between the semesters: the entire school year consists of d1+d2 consecutive days of classes.

Fox Ciel is taking an English class during both semesters. For the class she needs to learn a lot of new words: exactly w1 words during the first semester and exactly w2 words during the second semester.

Ciel can learn arbitrarily many words on any single day. However, she does not like to change her workload too much. Therefore, the number of words she will learn on any two consecutive days must differ by at most one.

Formally, suppose the days of the school year are numbered from 1 to d1+d2. Suppose that Ciel will learn x[i] words on day i. Ciel will be happy if the numbers x[i] have the following properties:

x[1] + ... + x[d1] is exactly equal to w1
x[d1+1] + ... + x[d1+d2] is exactly equal to w2
for each valid i, | x[i+1] - x[i] | is at most 1

You are given the ints d1, d2, w1, and w2. Return "Possible" if there is a schedule that makes Ciel happy, or "Impossible" if there is no such schedule.

Definition

Class:: RememberWordsEasy
Method:: isPossible
Parameters:: int, int, int, int
Returns:: String
Method signature:: String isPossible(int d1, int d2, int w1, int w2)
(be sure your method is public)

Constraints

d1 will be between 1 and 1,000,000, inclusive.
d2 will be between 1 and 1,000,000, inclusive.
w1 will be between 0 and 1,000,000, inclusive.
w2 will be between 0 and 1,000,000, inclusive.

Examples

2

3

7

18

Returns: "Possible"

The school year has 2+3 = 5 days. Ciel needs to learn exactly 7 words during the first semester and exactly 18 words during the second semester. The only valid way to do so is to learn 3, 4, 5, 6, and 7 words during the five days of the school year. Note that 3+4 = 7 and 5+6+7 = 18.
1

1

3

5

Returns: "Impossible"

Here the school year has just 1+1 = 2 days. Ciel must learn 3 words on the first day and 5 words on the second day. However, |3 - 5| is more than 1, so Ciel will not be happy with this schedule.
3

5

300

500

Returns: "Possible"

One possible solution is to learn 100 words every day.
100

1

0

2

Returns: "Impossible"
1000000

1000000

1000000

1000000

Returns: "Possible"
74116

839

121

9489

Returns: "Possible"
9532

503

4929

8

Returns: "Possible"
4149

5827

85434

5556

Returns: "Possible"
7100

5746

8850

8140

Returns: "Possible"
89979

53535

96535

521

Returns: "Possible"
5912

47

289

9

Returns: "Possible"
32987

944

75855

94546

Returns: "Possible"
4

6792

2

41610

Returns: "Possible"
5972

8568

5

2143

Returns: "Possible"
6118

44

3953

59

Returns: "Possible"
29756

9483

6813

3035

Returns: "Possible"
9092

179

2897

4

Returns: "Possible"
47

1360

220

218

Returns: "Possible"
8350

37094

9

7

Returns: "Possible"
975

3

994

0

Returns: "Possible"
680

660

79

60

Returns: "Possible"
9370

3333

253

812

Returns: "Possible"
72

625

358

9

Returns: "Possible"
576

466

5601

764

Returns: "Possible"
9046

5

361

5

Returns: "Possible"
8969

611

193

7089

Returns: "Possible"
89

5

9

6

Returns: "Possible"
13331

6155

3757

11655

Returns: "Possible"
1276

459

52

6052

Returns: "Possible"
100

9618

5

370

Returns: "Possible"
594

7218

72

25

Returns: "Possible"
96772

3328

6

4349

Returns: "Possible"
8909

6068

164

728

Returns: "Possible"
4856

754

15606

7

Returns: "Possible"
564

21

85882

776

Returns: "Possible"
82

7135

5913

5413

Returns: "Possible"
972

5221

5

4556

Returns: "Possible"
65407

8421

839

52224

Returns: "Possible"
624

927

2

674

Returns: "Possible"
82762

378

9661

2

Returns: "Possible"
8032

608

2681

419

Returns: "Possible"
933

8184

8203

1

Returns: "Possible"
22266

1248

5895

52

Returns: "Possible"
67

6378

20

3909

Returns: "Possible"
8776

47392

5092

17136

Returns: "Possible"
63

1

355

5

Returns: "Possible"
3634

6150

4

1

Returns: "Possible"
39

7205

3

9369

Returns: "Possible"
98416

981

3

765

Returns: "Possible"
285

5837

904

73

Returns: "Possible"
88032

4021

24452

11157

Returns: "Possible"
36663

4255

2

8

Returns: "Possible"
4

9090

439

91156

Returns: "Possible"
3702

478

1743

69031

Returns: "Possible"
50

506

160

7

Returns: "Possible"
618

8

22

886

Returns: "Impossible"
70476

5

6951

770

Returns: "Impossible"
10

7

3

412

Returns: "Impossible"
3

50

132

7917

Returns: "Impossible"
9

333

5583

3800

Returns: "Impossible"
71277

76

47

55608

Returns: "Impossible"
9130

1

18267

32968

Returns: "Impossible"
304

70396

93148

2130

Returns: "Impossible"
2

528

553

4

Returns: "Impossible"
17865

4

2302

7322

Returns: "Impossible"
2637

39

6281

5629

Returns: "Impossible"
60

8614

84153

1540

Returns: "Impossible"
661

8

9

6577

Returns: "Impossible"
18

151

9560

775

Returns: "Impossible"
37

4

57

1772

Returns: "Impossible"
29

75

2411

792

Returns: "Impossible"
2

56638

7909

6768

Returns: "Impossible"
2280

36

93

57155

Returns: "Impossible"
12

3638

83846

4

Returns: "Impossible"
4

7415

6690

6

Returns: "Impossible"
219

6349

99101

1

Returns: "Impossible"
111

964

64055

8

Returns: "Impossible"
2

83073

5440

60987

Returns: "Impossible"
8

54

3

2777

Returns: "Impossible"
2

48

49

6780

Returns: "Impossible"
5995

1

371

5399

Returns: "Impossible"
5

9042

27

3

Returns: "Impossible"
56

1

98

3847

Returns: "Impossible"
5

74884

8945

724

Returns: "Impossible"
1

7645

5434

7

Returns: "Impossible"
16356

9

8

95

Returns: "Impossible"
34

3

3

6815

Returns: "Impossible"
983

9

2540

52461

Returns: "Impossible"
3480

94

64

48715

Returns: "Impossible"
99395

10

5023

9191

Returns: "Impossible"
190

1

1

4880

Returns: "Impossible"
2691

26

1039

68289

Returns: "Impossible"
24

540

91499

4

Returns: "Impossible"
1618

94

40

39043

Returns: "Impossible"
9

39946

2817

2531

Returns: "Impossible"
7414

115

93

21981

Returns: "Impossible"
9

9156

8701

5

Returns: "Impossible"
8

7

2993

97

Returns: "Impossible"
7

6370

6706

17909

Returns: "Impossible"
94024

3

1

9574

Returns: "Impossible"
46944

10

4

57525

Returns: "Impossible"
897

5

980

295

Returns: "Impossible"
121

2

1543

287

Returns: "Impossible"
6

6

64108

9065

Returns: "Impossible"
9762

2

9092

998

Returns: "Impossible"
200

10

1000

1100

Returns: "Impossible"
567

234

88888

888888

Returns: "Impossible"
5

3

12

0

Returns: "Possible"
1

2

1

1

Returns: "Possible"
1

5

4

6

Returns: "Possible"
3

1

10

1

Returns: "Impossible"
1

4

0

10

Returns: "Possible"
100

1

0

1

Returns: "Possible"
1

1

1

1

Returns: "Possible"
1

1

1000

1000000

Returns: "Impossible"
1

1

6

1

Returns: "Impossible"
1

1

3

2

Returns: "Possible"
3

5

300

479

Returns: "Impossible"
3

50

5

1275

Returns: "Possible"
1

1

2

2

Returns: "Possible"
10

1

7

4

Returns: "Possible"
1

2

5

15

Returns: "Impossible"
2

2

47

74

Returns: "Impossible"
10

2

99

108

Returns: "Impossible"
4

4

6

10

Returns: "Possible"

Statistics

Problem Statement for "RememberWordsEasy"

Problem Statement

Definition

Constraints

Examples