Connection Status:
Competition Arena > GUMIAndSongsDiv1

GUMIAndSongsDiv1

SRM 588 · 2013-06-25 · by semiexp

SRM 588 · 2013-06-25 · by semiexp · Brute Force, Greedy, Sorting
Class Name: GUMIAndSongsDiv1
Return Type: int
Method Name: maxSongs
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Gumi loves singing. She knows N songs. The songs are numbered 0 through N-1. She now has some time and she would love to sing as many different songs as possible.
You are given a int[] duration. For each i, duration[i] is the duration of song i in Gumi's time units.
Gumi finds it difficult to sing songs with quite different tones consecutively. You are given a int[] tone with the following meaning: If Gumi wants to sing song y immediately after song x, she will need to spend |tone[x]-tone[y]| units of time resting between the two songs. (Here, || denotes absolute value.)
You are also given an int T. Gumi has T units of time for singing. She can start singing any song she knows immediately at the beginning of this time interval. Compute the maximal number of different songs she can sing completely within the given time.

Constraints

  • duration and tone will each contain between 1 and 50 elements, inclusive.
  • duration and tone will contain the same number of elements.
  • Each element of duration will be between 1 and 100,000, inclusive.
  • Each element of tone will be between 1 and 100,000, inclusive.
  • T will be between 1 and 10,000,000, inclusive.
Examples
0)
{3, 5, 4, 11}
{2, 1, 3, 1}
17
Returns: 3

There are four songs. Two songs have tone 1 and their durations are 5 and 11, respectively. One song has tone 2 and its duration is 3. One song has tone 3 and its duration is 4. Gumi has 17 units of time to sing. It is impossible for Gumi to sing all four songs she knows within the given time: even without the breaks the total length of all songs exceeds 17. Here is one way how she can sing three songs: First, she sings song 0 in 3 units of time. Second, she waits for |2-3|=1 unit of time and then sings song 2 in 4 units of time. Finally, she waits for |3-1|=2 units of time and then sings song 1 in 5 units of time. The total time spent is 3+1+4+2+5 = 15 units of time.

1)
{100, 200, 300}
{1, 2, 3}
99
Returns: 0

In this case, T is so small that she can't sing at all.

2)
{1, 2, 3, 4}
{1, 1, 1, 1}
100
Returns: 4

There is plenty of time, so she can sing all of 4 songs.

3)
{9, 11, 13, 17}
{2, 1, 3, 4}
20
Returns: 1
4)
{87,21,20,73,97,57,12,80,86,97,98,85,41,12,89,15,41,17,68,37,21,1,9,65,4,
 67,38,91,46,82,7,98,21,70,99,41,21,65,11,1,8,12,77,62,52,69,56,33,98,97}
{88,27,89,2,96,32,4,93,89,50,58,70,15,48,31,2,27,20,31,3,23,86,69,12,59,
 61,85,67,77,34,29,3,75,42,50,37,56,45,51,68,89,17,4,47,9,14,29,59,43,3}
212
Returns: 12

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

Coding Area

Language: C++17 · define a public class GUMIAndSongsDiv1 with a public method int maxSongs(vector<int> duration, vector<int> tone, int T) · 172 test cases · 2 s / 256 MB per case

Submitting as anonymous