Valentine's Day '15 P1 - #1 BABE - DMOJ: Modern Online Judge

Valentine's Day '15 P1 - #1 BABE

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

bobhob314

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$ ~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$ ~K_i~ minutes to break out and escape. After $K_i$ ~K_i~ minutes of wooing has occurred, group $i$ ~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$ ~1 \dots G~ inclusive, where $G$ ~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$ ~P~ $(1 \le P \le 500)$ ~(1 \le P \le 500)~.
Lines $1 \dots P+1$ ~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$ ~P+1 \dots P+G+1~: $K_i$ ~K_i~ for each cage $(0 \le K_i \le 500)$ ~(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

8
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
1
1
5

Sample Output

1
3

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.

Gone!

Comments

0

sunnylancoder commented on Aug. 25, 2017, 7:13 p.m. ← edited →

After $K_i$ ~K_i~ minutes of wooing has occurred, group $i$ ~i~ leaves, such that they cannot be wooed immediately thereafter. Gone. Poof. Kerplooie.

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

0

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

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

-12
bobhob314 commented on Feb. 16, 2015, 10:46 p.m.
Steps to enlightenment:

Publish problems you don't know anything about

Learn about them the following day

turn on the lights and buy winterfresh lifesavers to reach in "light" & mint

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