TopCoder SRM#679(Div2)(2/3)

maksyuki 发表于 比赛 分类,标签:

250 Problem Statement

You have two favorite music bands. Each of them has just recorded a new album. You have bought both albums.

You know the durations (in seconds) of songs on each of the album. You are given these duration in vector <int>s durations1 and durations2. Elements of durations1 are the durations of songs on one of the album, elements of durations2 correspond to the songs of the other album.

You only have a limited amount of time before you have to leave for work. This amount of time is given in the int minutes. (Note that the durations are given in seconds while this time is given in minutes.) Given this time, you want to listen to as many different songs as possible. However, there is a constraint: as you are a fan of both bands, you have to listen to at least T different songs from each album.

Each song only counts if you listened to it from its beginning to its end. You can play the songs in any order you like. Selecting the next song to play and switching between albums takes zero time.

If the input data is such that it is impossible to listen to T different songs from each album in the time you have, return -1. Otherwise, return the largest number of different songs you can listen to.
Class: ListeningSongs
Method: listen
Parameters: vector <int>, vector <int>, int, int
Returns: int
Method signature: int listen(vector <int> durations1, vector <int> durations2, int minutes, int T)
(be sure your method is public)





500 Problem Statement

Some teams have competed in a programming contest. Each team has made one or more submissions. Each submission received some positive score. The total score of a team is the sum of the scores of all their submissions. The scoreboard is computed by sorting the teams according to their total scores. If multiple teams are tied, they are sorted lexicographically, with smaller names being higher in the scoreboard. The team on the top of the scoreboard is winning. (Only one team is winning at any moment, even if there are multiple teams tied for the winning total score.)

The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:
TeamName is the name of the team
N is the number of submissions they made
the values S1 through SN are the scores of those submissions
the values T1 through TN are times in minutes: submission Si was made after Ti minutes of the contest have elapsed
Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.

You are given a vector <string> scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.

You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.

You know that the duration of the contest was an integer between 1 and 10^9, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.

Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a vector <int> with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.
Class: ContestScoreboard
Method: findWinner
Parameters: vector <string>
Returns: vector <int>
Method signature: vector <int> findWinner(vector <string> scores)
(be sure your method is public)