В 82-квартирном доме проводится проверка долгов жильцов по оплате коммунальных услуг. Для формирования сообщений о накопившемся долге выбираются номера квартир, долг которых больше среднего по всему дому. Если долг квартиры равен среднему по дому, то номер квартиры включается в результирующий набор в том случае, когда средний долг больше минимального долга на 60%. Если долги у всех одинаковые, то выбирается первая половина (начиная с 1-й) квартир-должников и округляется в большую сторону (например, при пяти должниках будут выбраны первые 3 квартиры).
Программа должна выводить номера квартир-должников, подходящих по условию. Гарантируется, что максимальный долг не превышает 3000 рублей и каждая квартира во входных данных присутствует только один раз.
Описание входных и выходных данных.
На вход программы сначала вводится число квартир-должников N. В каждой из следующих N строк находятся сведения о долге одной из квартир в формате:
<�Фамилия> <�Имя> <�квартира> <�долг>,
где <�Фамилия> — строка, состоящая не более чем из 20 символов, <�Имя> — строка, состоящая не более чем из 15 символов, <�квартира> — целое положительное число от 1 до 82, <�долг> — положительное вещественное число. <�Фамилия> и <�Имя>, <�Имя> и <�квартира>, <�квартира> и <�долг> разделены одним пробелом.
Пример входных данных:
6
Иванов Иван 1 100.00
Петров Николай 2 800.00
Ветров Алексей 3 400.00
Садовой Руслан 4 300.00
Горин Иван 5 0.00
Лебедев Алексей 6 1000.00
Пример выходных данных для приведённого выше примера входных данных:
2
3
6
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N квартирах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Программа на языке PascalABC 1.8. Программа эффек- тивна по времени и по памяти.
const F=82;
var cnt: array[1..F] of real; c: char;
z, min, midl: real; i, flt, N: integer;
begin
for i := 1 to F do cnt[i] := 0;
readln(N);
midl := 0; min := 3000;
for i := 1 to N do
begin
repeat read(c);
until c = ’ ’; {конец фамилии}
repeat read(c);
until c = ’ ’; {конец имени}
readln(flt, z); {номер квартиры, задолженность}
if z < min then min := z;
midl := midl + z; cnt[flt] := z
end;
midl := midl/N;
flt := 0; i := 1;
if min = midl then
while flt < ((N div 2) + (N mod 2)) do
begin
if cnt[i] > 0 then
begin
write (i, ’ ’); flt := flt + 1
end;
i := i + 1
end
else
for i := 1 to F do
begin
if cnt[i] > midl then write (i, ’ ’);
if (cnt[i]=midl) and (cnt[i]>min*0.6) then
write (i, ’ ’)
end
end.