RememberWordsEasy

SRM 721 · 2017-08-30 · by cgy4ever

SRM 721 · 2017-08-30 · by cgy4ever · Math

Show categories

Class Name: RememberWordsEasy

Return Type: String

Method Name: isPossible

Arg Types: (int, int, int, int)

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.

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"

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

Coding Area

Language: C++17 · define a public class RememberWordsEasy with a public method string isPossible(int d1, int d2, int w1, int w2) · 125 test cases · 2 s / 256 MB per case