Connection Status:
Competition Arena > WakingUp

WakingUp

SRM 616 · 2013-12-22 · by tourist

SRM 616 · 2013-12-22 · by tourist · Simple Math, Simulation
Class Name: WakingUp
Return Type: int
Method Name: maxSleepiness
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Alex is sleeping soundly. At any minute T, his sleepiness can be characterized by an integer. Initially, at minute 0, Alex's sleepiness is some unknown integer S.

Unfortunately, there are several repeatedly ringing alarms disturbing him.

Starting from minute 1, the following happens each minute. First, Alex's sleepiness increases by D. Then some of the alarms ring, decreasing Alex's sleepiness.

Formally, alarms' characteristics are given in three int[]s period, start and volume. The i-th alarm rings at minutes start[i], start[i] + period[i], start[i] + 2 * period[i], etc., and each time it rings, Alex's sleepiness instantly decreases by volume[i]. If several alarms ring at the same minute, their effects are added up, so each of them decreases Alex's sleepiness by its volume.

While Alex's sleepiness is positive, he's still sleeping. Once it becomes less than or equal to zero, Alex immediately wakes up. Note that Alex's initial sleepiness can be non-positive. In that case he just wakes up at minute 0.

You are given the int[]s period, start, volume, and the int D. Return the largest possible value of S (Alex's initial sleepiness) such that he will wake up at some moment. If he is guaranteed to wake up for all possible values of S, return -1 instead.

Notes

  • It is possible to prove that the answer for any test case fits into a 32-bit signed integer type.

Constraints

  • period will contain between 1 and 50 elements, inclusive.
  • period, start and volume will contain the same number of elements.
  • Each element of period will be between 1 and 10, inclusive.
  • start[i] will be between 1 and period[i], inclusive.
  • Each element of volume will be between 1 and 1000, inclusive.
  • D will be between 1 and 100, inclusive.
Examples
0)
{2, 3}
{1, 2}
{3, 4}
3
Returns: 2

There are two alarms. The first alarm rings every 2 minutes, starting from minute 1, and has volume 3. The second alarm rings every 3 minutes, starting from minute 2, and has volume 4. Here is what would happen for S = 2: At minute 0, Alex's sleepiness is 2. At minute 1, Alex's sleepiness increases to 5. Then the first alarm rings, decreasing his sleepiness to 2. At minute 2, Alex's sleepiness increases to 5. Then the second alarm rings, decreasing his sleepiness to 1. At minute 3, Alex's sleepiness increases to 4. Then the first alarm rings, decreasing his sleepiness to 1. At minute 4, Alex's sleepiness increases to 4. No alarm rings at this minute. At minute 5, Alex's sleepiness increases to 7. Then both alarms ring, decreasing his sleepiness to 0, so he wakes up. It can be proven that for any larger S, Alex will never wake up.

1)
{1}
{1}
{17}
17
Returns: 0

For any positive S, Alex will never wake up. It's better not to fall asleep.

2)
{1}
{1}
{23}
17
Returns: -1

Each minute Alex's sleepiness decreases by 6. That means he will wake up at some moment, regardless of the initial sleepiness.

3)
{9, 2, 5, 5, 7}
{6, 1, 4, 1, 6}
{71, 66, 7, 34, 6}
50
Returns: 78
4)
{5, 6, 5, 3, 8, 3, 4}
{1, 1, 3, 2, 6, 3, 3}
{42, 85, 10, 86, 21, 78, 38}
88
Returns: -1

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

Coding Area

Language: C++17 · define a public class WakingUp with a public method int maxSleepiness(vector<int> period, vector<int> start, vector<int> volume, int D) · 157 test cases · 2 s / 256 MB per case

Submitting as anonymous