олимпиадная задача pascalabc. Задача 17 Детский праздник. Задача 17 Детский праздник
 Скачать 92.55 Kb.
|
|
Задача 17 Детский праздник Имя входного файла: INPUT.TXT Имя выходного файла: OUTPUT.TXT Максимальное время работы на каждом тесте: 10 секунд Организаторы детского праздника планируют надуть для него M воздушных шариков. С этой целью они пригласили N добровольных помощников, i-й среди которых надувает шарик за Ti минут, однако каждый раз после надувания Zi шариков устает и отдыхает Yi минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха). Формат входных данных В первой строке входного файла находятся числа M и N (0≤M≤1000, 1≤N≤20). Следующие N строк содержат по три целых числа — Ti, Zi и Yi соответственно (1≤Ti,Yi≤100, 1≤Zi ≤1000) Формат выходных данных Выведите в выходной файл на первой строке число T – время, за которое будут надуты все шарики. На второй строке выведите N чисел – сколько шариков, надует каждый из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них. Примеры
Алгоритм решения Для решения задачи применим жадный алгоритм. Жадный алгоритм – это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным. Будем по очереди добавлять шарики и отдавать для надувания следующий шарик тому помощнику, который надует шарик раньше всех. Эта схема приведет к оптимальному решению, так как мы выбираем каждый раз помощника с минимальным временем надувания. Алгоритм решения задачи выглядит примерно так: Заполняем данные по времени надувания, количеству шариков, надуваемых без перерыва и времени на отдых для каждого помощника. Задаем начальное время Рассчитываем время для каждого помощника на текущем шарике и запоминаем самое маленькое и помощника, увеличиваем количество шариков у выбранного помощника, проверяем – не пора ли отдыхать этому помощнику – если настало время отдыха, то увеличиваем его время на время отдыха, затем переходим к следующему шарику и снова отбираем минимальное время среди всех помощников. Повторяем цикл, пока не наберется нужное количество надутых шариков Блок-схема алгоритма  Программа (PascalABC.NET) program zadacha17; Const Mmax=1000; Nmax=20; Tmax=100; Ymax=100; Zmax=1000; var m,n:integer; //m - число шариков и n - число помощников i, j, k, min, time: integer; done, next, t, y, z: array [0..Nmax] of integer;//храним полученные результаты //next – массив, содержит момент окончания надувания помощником следущего шарика //done – массив, содержит количество шариков, надутых помощником //t - массив, содержит время надувания шариков помощниками //y - массив, содержит время отдыха помощников //z - массив, содержит число шариков, которые могут надуть помощники без перерыва Begin //Соединяемся с входным и выходным файлами //ввод и вывод по умолчанию из файла и в файл assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output); //заполняем массив с количеством помощников нулями for i:=0 to Nmax do done[i]:=0; // Задаем начальное время работы time := 0; //Вводим данные из файла read(m, n); //считываем число шариков и число помощников if m<>0 then //требуется надувать шары begin for i := 1 to n do begin read(t[i], z[i], y[i]); //считываем показатели по каждому из помощников next[i] := t[i]; end; Close(input); //заполняем массив с количеством помощников нулями for i:=0 to Nmax do done[i]:=0; // Задаем начальное время работы time := 0; for i := 1 to m do begin //Ищем того, кто закончит раньше min := MaxInt; //задаем минимум как самое большое целое for j := 1 to n do if next[j] < min then //если нашли меньше begin k := j; //запоминаем индекс min := next[j]; //запоминаем минимум end; //Обновляем время работы time := next[k]; //Добавляем помощнику новый шарик inc(done[k]); //Обновляем время окончания им работы next[k] := next[k] + t[k]; //Учитываем отдых (проверяем, сколько шариков надул помощник if done[k] mod z[k] = 0 then //если пора отдыхать next[k] := next[k] + y[k]; //то увеличиваем общее время на время отдыха end; end; //Выводим ответ writeln(time); //выводим время for i := 1 to n do write(done[i], ' '); //выводим количество шариков, надутых каждым помощником Close(output); end. Тесты:     |