На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС. Напишите эффективную по времени работы и по используемой... | Яндекс.Репетитор

Задание#T25738

На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС.

Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. На вход программе в первой строке подается число данных о стоимости бензина. В каждой из последующих строк находится информация в следующем формате:

<Компания> <Улица> <Марка> <Цена>

где <Компания> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Марка> – одно из чисел – 92, 95 или 98, <Цена> – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. <Компания> и <Улица>, <Улица> и <Марка>, а также <Марка> и <цена> разделены ровно одним пробелом. Пример входной строки:

Синойл Цветочная 95 2250

Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0.

Пример выходных данных:

12 1 0

Показать разбор

Содержание верного ответа и указания по оцениванию

(допускаются иные формулировки ответа, не искажающие его смысла)

Программа читает все входные данные один раз, не запоминая их в массиве, размер которого соответствует числу АЗС или диапазону цен. Во время чтения данных определяются минимальная цена каждой марки бензина и количество АЗС, продающих его по этой цене. Для этого используются 6 переменных или соответствующие массивы (например, для удобства из 8 элементов каждый, см. программу на языке Бейсик).

Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой марки бензина минимальная цена отмечена ровно на одной АЗС).

Ниже приведены примеры решения задания на языках Бейсик и Паскаль.

Допускаются решения, записанные на других языках программирования. При оценивании решений на других языках программирования необходимо учитывать особенности этих языков программирования.

Пример правильной и эффективной программы

var
  min, ans: array[92..98] of integer;
  c: char;
  i, k, N, b: integer;
begin
  for i:=92 to 98 do
    begin
      min[i]:=3001;{допустимо и другое число, >3000}
      ans[i]:=0;
    end;
  readln(N);
  for i:=1 to N do
  begin
    repeat
      read(c);
    until c=' '; {считана компания}
    repeat
      read(c);
    until c=' '; {считана улица}
    readln(k,b);
    if min[k] > b then
      begin
        min[k]:=b;
        ans[k]:=1
      end else
    if min[k] = b then ans[k]:=ans[k]+1;
  end;
  {если бензина какой-то марки не было,
  ans[i] осталось равным 0}
  writeln(ans[92],' ', ans[95],' ', ans[98])
end.

Критерии оценки

4 баллаПрограмма работает верно для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве, размер которого соответствует числу (количество данных мониторинга) или диапазону цен (3000).
Программа просматривает входные данные один раз, используя для нахождения ответа два массива из 3-х (8-и) элементов каждый (как в примерах программ) или 6 соответствующих переменных.
Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку).

3 баллаПрограмма работает верно, но входные данные или только цены запоминаются в массиве, в том числе возможно в массиве (трех массивах) с индексами от 0 до 3000, обозначающем количество АЗС, продающих бензин по соответствующей цене, или входные данные считываются несколько раз. Возможно, вместо алгоритма поиска минимума используется сортировка всех цен. Допускается наличие от одной до трех синтаксических ошибок: Возможно, в принципиально верно организованном вводе данных есть одна ошибка. Три балла также выставляется, если в эффективной программе, удовлетворяющей критериям выставления 4 баллов, есть одна ошибка, в результате которой программа работает не верно на некоторых (не типичных) наборах входных данных (например, все цены на одну из марок бензина равны 3000).

2 баллаПрограмма работает в целом верно, эффективно или нет, но, в реализации алгоритма содержатся до двух ошибок (неверная инициализация переменных, в частности значения минимума, возможно программа не верно работает, если минимальное значение равно 3000, выход за границу массива, перевод символов в числа, используется знак “<” вместо “<=”, “or” вместо “and” и т.п.). Возможно, некорректно организовано считывание входных данных. Возможно, не для всех марок бензина ответ находится верно. Допускается наличие от одной до пяти синтаксических ошибок, описанных выше.

1 баллПрограмма, возможно, неверно работает при некоторых входных данных. Возможно, программа не определяет или неверно определяет, что бензина какой-то марки не было. Или минимальная цена марки бензина считается верно, а количество соответствующих АЗС – нет. При использовании сортировки допущены ошибки в ее реализации. Допускается до 4 различных ошибок в реализации алгоритма, в том числе описанных в критериях присвоения двух баллов. Допускается наличие от одной до семи синтаксических ошибок, описанных выше.

0 балловЗадание не выполнено или выполнено неверно

Это задание в разделах:

ЕГЭ-2010 - Архив

Задание#T25738

Это задание в разделах:

Рекомендованные задания