Каждому компьютер!
Первоисточник: Командный чемпионат школьников Санкт-Петербурга по программированию
URL первоисточника: http://neerc.ifmo.ru/school/2000-2001/ru-olymp-team-spb-2000.rar
Задачу добавил: alef
Успешно сдано решений: 10
В новом учебном году на занятия в компьютерные классы Дворца Творчества Юных пришли учащиеся, которые были разбиты на N групп. В i-й группе оказалось Xi человек. Тут же перед директором встала серьезная проблема: как распределить группы по аудиториям. Во дворце имеется M>=N аудиторий, в j-й аудитории имеется Yj компьютеров. Для занятий необходимо, чтобы у каждого учащегося был компьютер и еще один компьютер был у преподавателя. Переносить компьютеры из одной аудитории в другую запрещается. Помогите директору! Напишите программу, которая найдет, какое максимальное количество групп удастся одновременно распределить по аудиториям, чтобы всем учащимся в каждой группе хватило компьютеров, и при этом остался бы еще хотя бы один для учителя. Формат входных данных На первой строке входного файла расположены числа N и M (1<=N<=M<=1000). На второй строке расположено N чисел - X1, X2, ..., XN (1<=Xi<=1000 для всех 1<=i<=N). На третьей строке расположено M чисел Y1, Y2, ..., YM (1<=Yj<=1000 для всех 1<=j<=M). Формат выходных данных Выведите на первой строке число P - количество групп, которые удастся распределить по аудиториям. На второй строке выведите распределение групп по аудиториям - N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. (Нумерация как групп, так и аудиторий, начинается с 1). Если i-я группа осталась без аудитории, i-е число должно быть равно 0. Если допустимых распределений несколько, выведите любое из них. Пример INPUT.TXT 3 4 5 3 4 3 5 3 6 OUTPUT.TXT 2 0 2 4