Valentine's Day '15 P1 - #1 BABE

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Valentine's Day 2015 Contest

To celebrate Valentine's Day, the Ice King has kidnapped everyone he knows for a wooing session! He has captured P organisms including princesses and non-princesses. Unfortunately, the Ice King only swings one way: toward princesses. He also doesn't have that much wooing time, as Slime Princess is melting out of her cage and Turtle Princess is very slowly biting her cage bars. The Ice King directs Gunter, Gunther, and Günter to arrange the kidnappees in a row. The penguins put each consecutive line of princesses in a cage together and toss out the non-princesses. They are free to go now and catch up on the latest episode of The Walking Dead.

The Ice King can only woo one cage of princesses at a time and each wooing session lasts for one minute. Since the Ice King recently bought a pair of ice skates (made of ice), his transportation time between cages is nil. Each cage of princesses takes K_i minutes to break out and escape. After K_i minutes of wooing has occurred, group i leaves, such that they cannot be wooed immediately thereafter. Gone. Poof. Kerplooie.

Help the Ice King woo as many princesses as possible by directing him to the next cage he should visit. Each group is numbered from left to right from 1 \dots G inclusive, where G is the number of groups. If there is a tie between which two groups should be wooed first, the group with more princesses should be wooed first. If that still ties, the group with the lower numbering wins.

Input Specification

  • First line: the single integer P (1 \le P \le 500).
  • Lines 1 \dots P+1: names of the Ice King's prisoners. Princesses will all have the word Princess in their name, surrounded by space characters on both sides. Kidnappees are listed in order from left to right (by Goonther). A kidnappee cannot be a princess if there is not exactly one instance of the word Princess in their name. A word is a non-empty string of non-whitespace characters surrounded by whitespace characters or the beginning or end of the line.
  • Lines P+1 \dots P+G+1: K_i for each cage (0 \le K_i \le 500). Cages are numbered from left to right.

Output Specification

Output all the groups that the Ice King could woo, in order, so that he woos the maximum number of princesses.

Sample Input

High Princess Bubblegum
Flame Princess of Flame Kingdom
Finn the Human
Lumpy Princess of Space
Jake the Dog
Breakfast Princess of Something Else
The Princess Embryo
The Princess Ghost

Sample Output


Explanation of Output for Sample Input

The groups are of size 2, 1, and 3. The Ice King should woo group 1 for the first minute because it has more princesses than group 2. The next minute, he should woo group 3 because group 2 has already escaped.



  • 0
    sunnylancoder  commented on Aug. 25, 2017, 7:13 p.m.
    "After ~K_i~ minutes of wooing has occurred, group ~i~ leaves, such that they cannot be wooed immediately thereafter. Gone. Poof. Kerplooie."

    Does "after K_i" mean that they stay in the time range [0, K_i] or does it mean [0, K_i)? For example, if K_1=0, does that mean group 1 leaves before any wooing occurs?

    • 0
      Phoenix1369  commented on Aug. 25, 2017, 7:30 p.m.

      Yes. In the sample, K_2 = 1 and as a result, group 2 left after the first minute.

  • -12
    bobhob314  commented on Feb. 16, 2015, 10:46 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.