BOI’ 2005 RHODES Island – HELLAS 
3-8 September 2005
Bulgaria
Задача 2: Билети

Гръцката Компания за Радиоразпространение (ГКР) има намерение да модернизира системата си за телетекст. ГКР разполага с известен брой информационни телетекст страници с еднакъв размер, които се разпространяват по D канали channels в съответствие с информацията от билетите на Гръцките Държавни Железници. След щателно изследване ГКР обнародва популярността (вероятността за преглед на страницата) на телетекст страниците. Отчитайки тези данни, шефът на ГКР трябва да реши кои телетекст страници по кой канал да бъдат разпространявани, така че да се минимизира средното закъснение при преглеждане на страниците.  
Страниците по всеки канал се разпространяват циклично, т.е. за канал с три страници A, B, C, редът на разпространение е  A,B,C,A,B,C,A,… . Съгласно използвана информационна система, всички страници имат Internal Code (IC), в намаляващ ред на тяхната популярност. IC е уникален идентификатор за всяка страница. Например, за три канала, които обслужват общо 10 страници (т.е. IC приемат стойности от 1 до 10), канал D1 може да обслужва само страници с IC със стойности [1..M1] (M1≥1), канал D2 може да обслужва само страници с IC със стойности [M1+1..M2] (M2≥M1+1), и канал D3 може да обслужва само страници с IC със стойности [M2+1..10]. 
Напишете програма, която по зададен брой на каналите, брой на страниците и популярността на всяка страница, намира максималния IC за страниците, разпространявани от всеки канал, така че средното закъснение при преглеждане на страниците да е минимално.

Вход
Програмата чете входните данни от файл “tickets.in”. Първият ред съдържа цяло число D -  брой на каналите (1≤D≤20). Вторият ред съдържа цяло число L – брой на страниците (1≤L≤300). 
Всеки от следващите L реда съдържа едно реално число от интервала [0..1], което представя популярността на страницата. Популярностите са в намаляващ ред.

Изход
Програмата извежда във файл “tickets.out” D реда. Всеки ред съдържа цяло число, съответстващо на максималния IC на страница, обслужвана от всеки канал (1≤IC≤L).

Пример 
tickets.in
4
8
0.28390927493533
0.17355945737314
0.13014380192001
0.10610039157939
0.09055467526374
0.07955952705969
0.07131156575676
0.06486130611193	tickets.out
1
3
5
8

 
В този пример средното закъснение е  0,96591156199652, получен от следното разпределение на страниците: 

Канал	1	2	3	4	
Страница	1	2,3	4,5	6,7,8	

Формат: Във всеки от файловете числата в един ред са разделени с единичен интервал. Всички редове завършват с край на ред.

Време за изпълнение: 1 секунда.