Want to try solving this problem? You can submit your code online if you log in or register.
You are the long-suffering director of finance for the Australasian
Academy of Aesthetic Arts, Astounding Acts of Acrobatics and Algebra. Week in,
week out, the Academy organises increasingly elaborate and expensive arts events
while you struggle to scrape together enough money to make ends meet.
The big thing this month is Machinations Infernal, a modern dance routine involving D dancers and H hula hoops. Each dancer is assigned a unique number between 1 and D, and starts off holding some number of hula hoops (possibly none). The dance routine is performed as a sequence of T throws where each throw is of the form "dancer i throws a hula hoop to dancer j" (where i and j represent different dancers). Each throw is performed in the order specified, one after another. No hoops may be thrown unless it is part of the routine.
For a dancer to throw a hula hoop, they clearly must hold at least one hoop at that instant. You have been tasked with determining how many hula hoops are needed at the start of the dance such that every dancer has one to throw when required by the routine. As everyone knows, hula hoops are very expensive, so you must determine the minimum number of hula hoops required for the dance routine.
For example, consider the following dance routine consisting of five dancers and eight throws.
1 → 3 |
2 → 3 |
2 → 1 |
5 → 2 |
3 → 5 |
1 → 4 |
3 → 4 |
4 → 5 |
One way to begin the routine is to give one hoop to dancer 1, two hoops to dancer 2, and one hoop to dancer 5. Dancers 3 and 4 begin with no hoops. The following table shows how many hoops each dancer has after each step of the dance.
Dancer | |||||
1 | 2 | 3 | 4 | 5 | |
Initial set-up | 1 | 2 | 0 | 0 | 1 |
1 → 3 | 0 | 2 | 1 | 0 | 1 |
2 → 3 | 0 | 1 | 2 | 0 | 1 |
2 → 1 | 1 | 0 | 2 | 0 | 1 |
5 → 2 | 1 | 1 | 2 | 0 | 0 |
3 → 5 | 1 | 1 | 1 | 0 | 1 |
1 → 4 | 0 | 1 | 1 | 1 | 1 |
3 → 4 | 0 | 1 | 0 | 2 | 1 |
4 → 5 | 0 | 1 | 0 | 1 | 2 |
With these four hoops, every dancer always has a hoop to throw when required and this in fact uses the fewest number of hoops possible.
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
Your program should read from the file dancein.txt. The first line of this file will consist of the integers D and T separated by a single space. The following T lines describe the throws in the dance routine, in the order they must be performed. Each of these lines will be of the form `a_{i} b_{i}', specifying that dancer a_{i} throws a hula hoop to dancer b_{i}.
Your program should write to the file danceout.txt. Your output file should consist of a single integer: the minimum number of hula hoops required for the dance.
5 8 1 3 2 3 2 1 5 2 3 5 1 4 3 4 4 5
4
The sample input corresponds to the example on the previous page.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.
Privacy
statement
© Australian Mathematics Trust 2001-2021
Page generated: 26 October 2021, 12:59am AEDT