RememberWords | Topcoder Archive

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:: RememberWords
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,000, inclusive.
d2 will be between 1 and 1,000,000,000, inclusive.
w1 will be between 0 and 1,000,000,000, inclusive.
w2 will be between 0 and 1,000,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"
```

1000000000

1000000000

1000000000

1000000000

Returns: "Possible"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.