TASK
2 -Tickets
The Hellenic Broadcasting
Company (HBC) wants to modernize its teletext
broadcasting system. The HBC has a number of equal size information teletext pages that are broadcasted in D channels concerning ticket
information of the Hellenic Railway Organisation.
Additionally, HBC through a thorough investigation revealed the popularity
(probability of viewing a page) of all Teletext
pages. Based on these data, the manager of HBC has to decide which pages will
be broadcasted on each channel, so that the average delay of viewing a page is minimised. The pages of the channel are cyclically
broadcasted in a round-robin fashion, e.g. for a channel with 3 pages A, B, C,
the broadcasting order is A,B,C,A,B,C,A,… . However,
because of the used information system, all pages have an Internal Code (IC),
which are given based on their popularity in decreasing order. The IC is a
unique identifier for each page. For example, for three channels that serve 10
pages totally (i.e. IC ranges from 1 to 10), channel D1 can only serve pages with IC in the
range [1..M1] (where M1 ≥ 1), channel D2 can
only serve pages with IC in the range [M1+1..M2] (where M2 ≥ M1 + 1), and channel D3 can only serve pages with IC in the
range [M2 + 1..10]. Given the
number of channels, the number of pages and the popularity of each page, your
task is to calculate the maximum IC page broadcasted
from each channel to minimize the average delay of viewing a page.
Input
Your program should read the input from a file "tickets.in". The first line of the file contains an integer D representing the number of channels (where 1 ≤ D ≤ 20) and the second line contains an integer L representing the number of pages (where 1 ≤ L ≤ 300). Each of the next L lines contains a single real number in the range [0..1], which depicts the popularity of the page. These popularities are given in decreasing order.
Output
Your program should write
the output into a file "tickets.out" with D lines. Each line should contain a
single integer denoting the maximum page IC
J served from each channel (for 1 ≤ J ≤ L ).
Example
|
tickets.in |
tickets.out |
In this example, the
average delay value is 0.96591156199652 resulting from the following page
distribution:
|
Channel |
1 |
2 |
3 |
4 |
|
Pages |
1 |
2,3 |
4,5 |
6,7,8 |
Format : In both input and output files, all numbers in
a line are separated with a single space and all lines terminate with a newline character.