SuperCon'96 Cntest Exercise
Contest Exercise: "Cafeteria Problem"
There is a cafeteria where you can choose from some set menus. Each kind of
dish is served at an independent counter respectively.
The guests are queuing for each set menu in front of the entrance.
The guests follow the guidance of the manager at the entrance. That is;
A guest proceeds to the entrance and receives a tray after called by
the manager, then goes around the counters in the order specified by the
manager and goes to the exit with the completed set on the tray.
Problem:
Write a program which guides the guests as the manager in order to shorten
the time that all the guests complete their sets and reach the exit.
Conditions:
- Set Menu
-
A-set Hamburger(3) + Salad(2) + Bread(1) + Soup(2) + Milk(1)
B-set Fried prawn(4) + Rice(2) + Milk(1) + Fruit(1)
C-set Beef steak(5) + Salad(2) + Rice(2) + Soup(2) + Fruit(1)
D-set Bread(1) + Salad(2) + Fruit(1) + Milk(1) + Soup(2)
-
* each figure in the parentheses indicates serving time
- Number of waiting guests for each set
- A-set: 1000 persons, B-set: 750 persons
C-set: 500 persons, D-set: 500 persons
- Capacity of each queue in each counter
- 4 persons
The Contest was performed with the following hardware/software conditions:
-
Cray C916/12256 (Clock 4 nsˇ¤12 CPUsˇ¤2GB Memories)
CPUs: 9
Memory: 128 MB
Running mode: dedicated to one job at a time
Compiler options: nothing
- the inner most loop can be vectorized.
- No autotasking, but directives can be allowed to be added
into source codes.
Results: 6540 unit time
TAKADA Masanori and TATEISHI Daisuke(NADA High School)
We are waiting for your challenge next year 1997
For more information or comments, send an e-mail: office@cc.titech.ac.jp.