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