BIO/ADO question

[olamm2k]

Hi,

Did anyone else take part in the British Informatics Olympiad yesterday? I did the first two questions with no trouble, but the third I just couldn't see how to do, and it's bugging me.
Here it is (from memory):
A film company is producing a post-modernistic film where there is only one actor in each scene. In order for the actors to stay in character, all of their scenes are to be done in order and there is also a hierarchical system among the actors, so no junior actor can have shot more scenes than a senior actor at any one time.
Given that there may be between 1 and 8 actors, each with up to 8 scenes, write a program to display the number of possible shooting schedules, assuming the most senior actor is listed first when taking input for the program.
For example, with two actors, each with two scenes, there are 2 possible schedules (scenes to be shot in brackets):

Schedule 1: Actor 1 (1 2), Actor 2 (3 4)
Schedule 2: Actor 1 (1 3), Actor 2 (2 4)

NB: Actor 1 (1 4), Actor 2 (2 3) is not possible because this would mean that Actor 2 has shot two scenes while Actor 1 has only shot 1, and this would violate the seniority rule.


If something needs clarifying (it's a bit garbled, but the gist of it is there), then just ask. Any ideas?

[Pino]

Hi,

Did anyone else take part in the British Informatics Olympiad yesterday? I did the first two questions with no trouble, but the third I just couldn't see how to do, and it's bugging me.
Here it is (from memory):
A film company is producing a post-modernistic film where there is only one actor in each scene. In order for the actors to stay in character, all of their scenes are to be done in order and there is also a hierarchical system among the actors, so no junior actor can have shot more scenes than a senior actor at any one time.
Given that there may be between 1 and 8 actors, each with up to 8 scenes, write a program to display the number of possible shooting schedules, assuming the most senior actor is listed first when taking input for the program.
For example, with two actors, each with two scenes, there are 2 possible schedules (scenes to be shot in brackets):

Schedule 1: Actor 1 (1 2), Actor 2 (3 4)
Schedule 2: Actor 1 (1 3), Actor 2 (2 4)

NB: Actor 1 (1 4), Actor 2 (2 3) is not possible because this would mean that Actor 2 has shot two scenes while Actor 1 has only shot 1, and this would violate the seniority rule.


If something needs clarifying (it's a bit garbled, but the gist of it is there), then just ask. Any ideas?

Yes I did it, but it was last friday.

I did very bad though, I didnt bother with that question. I thought it was a programming challenege. But it was more of a logic paper :-/

How did you find the other questions?

[olamm2k]

I thought they weren't bad, actually. The first one took very little time once I remembered the routine I wrote a while back for finding the Highest Common Factor, and the second one was just a series of nested if statements. It was only that last one that stumped me...