C4 (высокий уровень, время – 55 мин)
C4 (высокий уровень, время – 55 мин)
Тема: Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из 30-50 строк) или последовательности чисел.
Что нужно знать:
· символьная строка – это цепочка символов, которая может обрабатываться как единое целое
· для обращения к символу с номеромi строки s используется запись s[i], это говорит о том, что строка – особый вариант массива, в котором хранятся символы
· знак сложения при работе с символьными строками означает сцепку, объединение двух строк в одну (добавление второй строки в конец первой), например:
s := '123' + '456'; { получили '123456' }
· с помощью функции Ord можно получить код символа; цифры имеют коды от 48 (цифра 0) до 57 (цифра 9), например
k := Ord('1'); { получили 49 }
то же самое можно сделать с помощью преобразования типа (привести char к integer)
k := integer('1'); { получили 49 }
· с помощью функции Chr можно сделать обратный переход: получить символ по его коду, например
c := Chr(49); { получили символ '1' }
то же самое можно сделать с помощью преобразования типа (привести integer к char)
c := char(49); { получили символ '1' }
· для работы со строками в наиболее распространенных Паскаль-средах (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) используют стандартные функции (здесь s – это переменная типа string, символьная строка; n и r – целые переменные)
| n := Length(s); | записать длину строки s в целую переменную n |
| s1 := Copy(s, 2, 5); | записать в символьную строку s1 подстроку строки s, которая начинается с символа с номером 2 и состоит из 5 символов (важно – не со 2-го по 5-ый символ!) |
| n := Pos('Вася', s); | записать в целую переменную n номер символа, с которого в строке s начинается подстрока 'Вася' (если ее нет, в переменную n записывается 0); так же можно искать отдельные символы (важно: сначала указываем, что ищем, а потом – где) |
| n := StrToInt(s); | преобразовать строку s в целое число и записать результат в переменную n (PascalABC, Delphi) |
и процедуры
| Delete(s, 2, 5); | удалить из строки s5 символов, начиная со второго |
| Insert('Вася', s, 3); | вставить в строку s фрагмент 'Вася', начиная с третьего символа (между 2-м и 3-м) |
| Val(s, n, r); | преобразовать строку s в целое число и записать результат в переменную n; если при этом произошла ошибка, в переменной r будет номер ошибочного символа, если все нормально – ноль |
· структура (в Паскале она называется «запись», record) – это сложный тип данных, который может включать в себя несколько элементов – полей; поля могут иметь различный тип
· записи в Паскале объявляются с помощью ключевого слова record; в простейшем случае можно выделить память под одну запись так:
Var x: record
name: string;
code: integer;
end;
эта запись состоит из двух полей: символьной строки name и целого числа code
· записи очень удобны для работы, когда все данные в целом представляют собой единый блок информации, например, данные об ученике; если не использовать записи, было бы нужно выделять в памяти отдельно символьную строку и отдельно целую переменную, причем эти данные внешне были бы никак не связаны, поэтому программа с записями часто получается логичнее и понятнее как для автора, так и для того, кто будет в ней разбираться
· для обращения к полям записи используют точку, например x.name означает «поле name записи x»
· можно сразу объявить массив записей:
var Info: array[1..100] of record
name: string;
code: integer;
end;
это 100 одинаковых записей, имеющих общее имя Info и расположенных в памяти рядом; в каждой структуре есть поля nаme и code; чтобы работать с полями записи с номером k используют обращения вида Info[k].name и Info[k].code
Сложность алгоритмов:
· обозначение 
говорит о том, что при увеличении в 2 раза размера массива данных количество операций тоже увеличивается примерно в 2 раза (для больших N)
· сложность имеет алгоритм с одним или несколькими простыми (не вложенными!) циклами в каждом из которых выполняется N шагов (как при поиске минимального элемента)
· количество операций для алгоритма, имеющего сложность , вычисляется по формуле 
, где a и b – некоторые постоянные
· если в одном алгоритме решения задачи используется несколько циклов от 1 до N, а во втором – только один цикл, то алгоритм с одним циклом, как правило, эффективнее (хотя оба алгоритма имеют сложность , постоянная 
в каждом случае своя, для алгоритма с несколькими циклами она будет больше)
· для алгоритма, имеющего сложность 
, количество операций пропорционально квадрату размера массива, то есть, если N увеличить в 2 раза, то количество операций увеличивается примерно в 4 раза (например, в программе используется два вложенных цикла, в каждом из которых N шагов); сложность имеют простые способы сортировки массивов: метод «пузырька», метод выбора
· при больших N функция 
растет значительно быстрее, чем 
, поэтому алгоритм, имеющий сложность всегда менее эффективен, чем алгоритм сложности
· иногда встречаются алгоритмы сложности 
(три вложенных цикла от 1 до N), при больших N они работают медленнее, чем любой алгоритм сложности , то есть, менее эффективны
· для многих задач известны только алгоритмы экспоненциальной сложности, когда размер массива входит в показатель степени, например 
, для больших N такие задачи не решаются за приемлемое время (например, «взламывание» шифров)
Пример задания:
На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат:
<Фамилия> <Инициалы> <номер школы>
где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:
Иванов П.С. 57
Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.
Begin
for k:=1 to 99 do C[k]:=0;
readln(N);
for i:=1 to N do begin
readln(s); { читаем очередную строку }
{ выделяем часть после второго пробела }
p := Pos(' ', s);
Delete(s, 1, p+5);
{ определяем номер школы k }
Val(s, k, r);
C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы }
end;
Min := N;
for k:=1 to LIM do
if (C[k] <> 0) and (C[k]<Min) then Min := C[k];
for k:=1 to LIM do
if C[k] = Min then writeln(k);
End.
| На что обратить внимание: · внимательно читайте условие, убедитесь, что вы понимаете смысл каждой строчки; для каждой мелочи постарайтесь определить, зачем она добавлена в условие, что она дает для решения задачи, что ограничивает, что не разрешает делать · определите, какая именно информация из условия нужна для решения задачи, а какая – не нужна · определите, что именно требуется вывести на экран в результате работы программы · начинайте составлять программу с больших блоков, записывая ее сначала на псевдокоде, а потом уточняя детали · проверяйте «крайние» варианты (например, возможность выхода за границы массива) · проверьте, правильно ли заданы (и заданы ли вообще) начальные значения для всех переменных · будьте внимательны, когда в массиве есть «мертвые» элементы, которые не нужно учитывать; проверяйте, что в этом случае ваши алгоритмы (например, поиск минимального элемента) работают правильно · проверьте, правильно ли расставлены операторные скобки begin-end, ограничивающие тело цикла; их обязательно нужно ставить, если в теле цикла несколько операторов · при использовании функции Pos не забывайте, что первый параметр – что ищем (образец), а второй – где ищем · чтобы эксперту было легче понять вашу программу (особенно, если она получилась «нестандартной»), пишите комментарии; объясняйте, что хранится в основных переменных · если это возможно, желательно работать только с целыми числами; этим вы избежите проблем, связанных с округлением и неточностью хранения дробных вещественных чисел в памяти компьютера |
Еще пример задания:
На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:
<Фамилия> <Имя> <оценки>,
где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом. Пример входной строки:
Иванов Петр 4 5 3
Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех худших, то следует вывести и их фамилии и имена.
Repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ' '; { пока не прочитали пробел }
7) затем также читаем из входного потока имя, до пробела, и записываем его в конец того же поля name:
Repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ' '; { пока не прочитали пробел }
заметьте, что эти два цикла одинаковы, поэтому ввод имени и фамилии можно записать в виде вложенного цикла так:
Info[i].name := ''; { пустая строка }
for k:=1 to 2 do
Repeat
read ( c );
Info[i].name := Info[i].name + c;
until c = ' '; { пока не прочитали пробел }
8) важно! обратите внимание, что для организации внутреннего цикла используется другая переменная, k (а не i, потому что i – переменная главного цикла, она обозначает номер текущего ученика)
9) теперь во входном потоке остались три числа, которые мы можем последовательно считывать в целую переменную mark, а затем – добавлять к полю Info[i].sum:
Info[i].sum := 0;
for k:=1 to 3 do begin
read(mark);
Info[i].sum := Info[i].sum + mark;
end;
readln;
10) последняя команда readln пропускает все оставшиеся символы до новой строки (из этой мы прочитали все, что нужно)
11) вот полный цикл ввода данных, после его окончания все исходные данные будут записаны в первые N записей массива Info:
for i:=1 to N do begin
{ ввод имени и фамилии }
Info[i].name := '';
for k:=1 to 2 do
Repeat
read(c);
Info[i].name := Info[i].name + c;
until c = ' ';
{ ввод и суммирование оценок }
Info[i].sum := 0;
for k:=1 to 3 do begin
read(mark);
Info[i].sum := Info[i].sum + mark;
end;
readln;
end;
Поиск трех худших данных:
12) теперь нужно придумать, как за один проход по массиву найти три худших результата;
13) как бы мы решили эту задачу, если бы нам нужно было просмотреть столбик чисел и найти три минимальных? можно сделать, например, так:
o на бумажке вести записи в три столбика, в первом записывать минимальное число, в втором – следующее по величине, в третьем – «третье минимальное»
o сначала пишем первое число в первый столбик, оно – минимальное, потому что других мы не еще видели; пусть это число 14:
| минимум | второе | третье |
o пусть следующее число – 12; оно меньше минимального, поэтому его нужно записывать в первый столбец, а «старое» минимальное число «переедет» во второй столбец
| минимум | второе | третье |
| | ||
o пусть дальше идет число 10 – теперь оно станет минимальным, его нужно записывать в первый столбец; при этом 12 «переедет» из первого столбца во второй, а 14 – из второго в третий
| минимум | второе | третье |
| | ||
| | | |
o пусть следующее число – 11; оно больше минимального, но меньше «второго», поэтому его нужно поставить во второй столбец; число 12 из второго столбца перемещается в третий, а число 14 из третьего столбца удаляется из кандидатов в «три минимальных»
| минимум | второе | третье |
| | ||
| | | |
| | | |
o просмотрев таким образом весь столбик чисел, за один проход (!) можно найти три минимальных элемента
o остается только переложить этот алгоритм на язык программирования
14) выделим в памяти три целых переменных: min1 (минимальный), min2 («второй минимальный»), min3 («третий минимальный»), в виде начальных значений запишем в каждую из них число, заведомо превышающее максимальную возможную сумму трех оценок, например, 20 (>5+5+5)
15) полный цикл поиска выглядит так:
min1 := 20; min2 := 20; min3 := 20;
for i:=1 to N do begin
if Info[i].sum < min1 then begin { новый min1 }
min3 := min2; min2 := min1;
min1 := Info[i].sum;
End
else if Info[i].sum < min2 then begin { новый min2 }
min3 := min2;
min2 := Info[i].sum;
End
else if Info[i].sum < min3 then { новый min3 }
min3 := Info[i].sum;
end;
16) обратим внимание на два момента: во-первых, когда переезжают два элемента, сначала нужно перемещать второй на место третьего, а потом – первый на место второго:
min3 := min2;
min2 := min1;
эти операторы нельзя менять местами, иначе «старое» значение min2 будет потеряно;
во-вторых, если проверять условие Info[i].sum < min2 нужно только тогда, когда очередная сумма не меньше, чем min1, поэтому каждый следующий условный оператор стоит в else-блоке предыдущего, то есть, выполняется только тогда, когда предыдущий не сработал
17) итак, мы нашли три минимальных результата, и остается вывести на экран фамилии и имена тех, у кого сумма баллов меньше или равна min3:
for i:=1 to N do
if Info[i].sum <= min3 then
writeln(Info[i].name);
18) на всякий случай приведем полную программу, она получилась довольно длинная
const LIM = 100;
var Info: array[1..LIM] of record
name: string;
sum: integer;
end;
i, k, N, mark, min1, min2, min3: integer;
c: char;
Begin
readln(N);
{ ввод исходных данных }
for i:=1 to N do begin
Info[i].name := '';
for k:=1 to 2 do
Repeat
read(c);
Info[i].name := Info[i].name + c;
until c = ' ';
Info[i].sum := 0;
for k:=1 to 3 do begin
read(mark);
Info[i].sum := Info[i].sum + mark;
end;
readln;
end;
{ поиск трех минимальных }
min1 := 20; min2 := 20; min3 := 20;
for i:=1 to N do begin
if Info[i].sum <min1 then begin
min3 := min2; min2 := min1;
min1 := Info[i].sum;
End
else if Info[i].sum <min2 then begin
min3 := min2;
min2 := Info[i].sum;
End
else if Info[i].sum <min3 then
min3 := Info[i].sum;
end;
{ вывод результата }
for i:=1 to N do
if Info[i].sum <= min3 then
writeln(Info[i].name);
End.
19) эту задачу можно решить и без записей, используя два массива: массив символьных строк name и массив целых чисел sum, они объявляются так:
var name: array[1..MAX] of string;
sum: array[1..MAX] of integer;
после этого в приведенной программе нужно заменить везде Info[i].name на name и Info[i].sum на sum.
| На что обратить внимание: · в исходных данных выделите то, что не нужно для решения задачи; при чтении эти части можно просто пропускать; · если нам не нужны фамилия и имя отдельно, можно хранить их вместе, в виде одной строки · если нас интересует только сумма оценок, не нужно хранить их в памяти по отдельности · если можно при решении задачи обойтись без вещественных чисел, сделав все вычисления только с целыми числами – нужно поступить именно так (иначе снимут баллы), поскольку операции с вещественными числами во многих случаях случаев выполняются неточно · алгоритм сложности (например, сортировку) нужно использовать только тогда, когда нет алгоритма сложности ; как правило, в задачах ЕГЭ такой алгоритм всегда можно (попытаться) найти; за неэффективный алгоритм при оценке решения будут сняты баллы |
| За что снимают баллы: · программа работает не для всех исходных данных, не обрабатывает некоторые частные случаи · неверно реализован алгоритм поиска минимального элемента, сортировки и т.п. · неэффективность алгоритма: o используется алгоритм, имеющий сложность , когда есть алгоритм сложности o используется несколько проходов по массиву, когда достаточно одного o лишний расход памяти ( используются дополнительные массивы или размер массива определен неверно) o используются операции с вещественными числами, когда можно все решить в целых числах · переменная не описана или описана неверно · переменным не присвоены нужные начальные значения (например, не обнуляются счетчики) или присвоены неверные значения · нет вывода результата в конце программы · перепутаны знаки < и >, логические операции or и and · применяется недопустимая операция, например, div или mod для вещественных чисел · неверно расставлены операторные скобки begin-end · в цикле for используется вещественная переменная (Паскаль) · в цикле while или repeat не изменяется переменная цикла, из-за чего происходит зацикливание · синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов); чтобы получить 4 балла, при абсолютно верном решении нужно сделать не более одной синтаксической ошибки; на 3 балла – до трех ошибок, на 2 балла – до пяти и на 1 балл – до семи ошибок |
Задачи для тренировки[2]:
1) На вход программы подается 366 строк, которые содержат информацию о среднесуточной температуре всех дней 2008 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен. Требуется написать программу на языке Паскаль или Бейсик, которая будет выводить на экран информацию о месяце (месяцах), среднемесячная температура у которого (которых) наименее отклоняется от среднегодовой. В первой строке вывести среднегодовую температуру. Найденные значения для каждого из месяцев следует выводить в отдельной строке в виде: номер месяца, значение среднемесячной температуры, отклонение от среднегодовой температуры.
2) На вход программы подается текст на английском языке, заканчивающийся точкой (другие символы “.” в тексте отсутствуют). Требуется написать программу, которая будет определять и выводить на экран английскую букву, встречающуюся в этом тексте чаще всего, и количество там таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть файл содержит следующую запись:
It is not a simple task. Yes!
Чаще всего здесь встречаются буквы I, S и T(слово Yes в подсчете не учитывается, так как расположено после точки). Следовательно, в данном случае программа должна вывести два символа, разделенных пробелом: I 3
3) На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке. Например, пусть на вход подаются следующие символы:
Fhb5kbfыshfm.
В этом случае программа должна вывести
b2
f3
h2
kl
ml
s1
4) На вход программы подаются фамилии и имена учеников. Известно, что общее количество учеников не превосходит 100. В первой строке вводится количество учеников, принимавших участие в соревнованиях, N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя>
Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов. При этом <Фамилия> и <Имя> разделены одним пробелом. Примеры входных строк:
Иванова Мария
Петров Сергей
Требуется написать программу, которая формирует и печатает уникальный логин для каждого ученика по следующему правилу: если фамилия встречается первый раз, то логин – это данная фамилия, если фамилия встречается второй раз, то логин – это фамилия, в конец которой приписывается число 2 и т.д. Например, для входной последовательности
Иванова Мария
Петров Сергей
Бойцова Екатерина
Петров Иван
Иванова Наташа
будут сформированы следующие логины:
Иванова
Петров
Бойцова
Петров2
Иванова2
5) На городской олимпиаде по информатике участникам было предложено выполнить 3 задания, каждое из которых оценивалось по 25-балльной шкале. Известно, что общее количество участников первого тура олимпиады не превосходит 250 человек. На вход программы подаются сведения о результатах олимпиады. В первой строке вводится количество участников N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> – строка, содержащая три целых числа, разделенных пробелом, соответствующих баллам, полученным участником за каждое задание первого тура. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Примеры входных строк:
Петрова Ольга 25 18 16
Калиниченко Иван 14 19 15
Напишите программу, которая будет выводить на экран фамилию и имя участника, набравшего максимальное количество баллов. Если среди остальных участников есть ученики, набравшие такое же количество баллов, то их фамилии и имена также следует вывести. При этом имена и фамилии можно выводить в произвольном порядке.
6) На вход программы подаются сведения о результатах соревнований по школьному многоборью. Многоборье состоит из соревнований по четырем видам спорта, участие в каждом из которых оценивается баллами от 0 до 10 (0 баллов получает ученик, не принимавший участия в соревнованиях по данному виду спорта). Победители определяются по наибольшей сумме набранных баллов. Известно, что общее количество участников соревнований не превосходит 100.
В первой строке вводится количество учеников, принимавших участие в соревнованиях, N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> - строка, содержащая четыре целых числа, разделенных пробелом, соответствующих баллам, полученным на соревнованиях по каждому из четырех видов спорта. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Примеры входных строк:
Иванова Мария 5 8 6 3
Петров Сергей 9 9 5 7
Напишите программу, которая будет выводить на экран фамилии и имена трех лучших участников многоборья. Если среди остальных участников есть ученики, набравшие то же количество баллов, что и один из трех лучших, то их фамилии и имена также следует вывести. При этом имена и фамилии можно выводить в произвольном порядке.
7) В некотором вузе абитуриенты проходят предварительное тестирование, по результатам которого могут быть допущены к сдаче вступительных экзаменов в первом потоке. Тестирование проводится по двум предметам, по каждому предмету абитуриент может набрать от 0 до 100 баллов. При этом к сдаче экзаменов в первом потоке допускаются абитуриенты, набравшие по результатам тестирования не менее 30 баллов по каждому из двух предметов. На вход программы подаются сведения о результатах предварительного тестирования. Известно, что общее количество участников тестирования не превосходит 500.
В первой строке вводится количество абитуриентов, принимавших участие в тестировании, N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> – строка, содержащая два целых числа, разделенных пробелом, соответствующих баллам, полученным на тестировании по каждому из двух предметов. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Примеры входных строк:
Ветров Роман 68 59
Анисимова Екатерина 64 88
Напишите программу, которая будет выводить на экран фамилии и имена абитуриентов, потерпевших неудачу, то есть не допущенных к сдаче экзаменов в первом потоке. При этом фамилии должны выводиться в алфавитном порядке.
8) На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат:
<Фамилия> <Инициалы> <телефон>
где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> – семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «–». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом. Пример входной строки:
Иванов П.С. 555-66-77
Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами. Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.
9) На вход программе сначала подается число участников олимпиады N. В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>
где <Фамилия> – символьная строка (не более 20 символов), <Имя> – символьная строка (не более 15 символов), <класс> – число от 7 до 11, <баллы> – целое число набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом. Пример входной строки:
Семенов Егор 11 225
Победителем олимпиады становится участник, набравший наибольшее количество баллов, при условии, что он набрал более 200 баллов. Если такое количество баллов набрали несколько участников, то все они признаются победителями при выполнении условия, что их доля не превышает 20% от общего числа участников.
Победителем олимпиады не признается никто, если нет участников, набравших больше 200 баллов, или больше 20% от общего числа участников набрали одинаковый наибольший балл.
Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять фамилию и имя лучшего участника, не ставшего победителем олимпиады. Если таких участников несколько, т.е. если следующий за баллом победителей один и тот же балл набрали несколько человек, или, если победителей нет, а лучших участников несколько (в этом случае именно они являются искомыми), то выдается только количество искомых участников. Гарантируется, что искомые участники (участник) имеются.
Программа должна выводить через пробел фамилию и имя искомого участника или их количество. Пример выходных данных (один искомый участник):
Семенов Егор
Второй вариант выходных данных (несколько искомых участников):
10) В молочных магазинах города Х продается сметана с жирностью 15, 20 и 25 процентов. В городе X был проведен мониторинг цен на сметану. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждого вида сметаны, сколько магазинов продают ее дешевле всего. На вход программе сначала подается число магазинов N. В каждой из следующих N строк находится информация в следующем формате:
<Фирма> <Улица> <Жирность> <Цена>
где <Фирма> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Жирность> – одно из чисел – 15, 20 или 25, <Цена> – целое число в диапазоне от 2000 до 5000, обозначающее стоимость одного литра сметаны в копейках. <Фирма> и <Улица>, <Улица> и <Жирность>, а также <Жирность> и <Цена> разделены ровно одним пробелом. Пример входной строки:
12 10 0
11) Школьная олимпиада по информатике проводилась для учеников 7-11-х классов, участвующих в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 70 баллов. Для определения призеров олимпиады сначала отбираются 25% участников, показавших лучшие результаты. Если у последнего участника, входящего в 25%, оказывается такое же количество баллов, как и у следующих за ним в итоговой таблице, все они считаются призерами только тогда, когда набранные ими баллы больше половины максимально возможных; иначе все они не считаются призерами.
Напишите эффективную по времени работы и по используемой памяти программу, которая по результатам олимпиады будет определять минимальный балл призера олимпиады, и количество призеров было в каждой параллели (среди 7-х, 8-х, 9-х, 10-х и 11-х классов отдельно). Гарантируется, что хотя бы одного призера по указанным правилам определить можно.
На вход программе сначала подается число участников олимпиады N. В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>
где <Фамилия> – строка, состоящая не более, чем из 30 символов, <Имя> – строка, состоящая не более, чем из 15 символов, <класс> – число от 7 до 11, <баллы> – целое число от 0 до 70 набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом. Пример входной строки:
Семенов Сидор 11 66
Программа должна выводить в первой строке минимальный балл призера, а в следующей – число призеров по всем параллелям отдельно.
Пример выходных данных:
1 5 8 12 22
12) В некотором вузе абитуриенты проходили предварительное тестирование, по результатам которого они могут быть допущены к сдаче вступительных экзаменов в первом потоке. Тестирование проводится по трём предметам, по каждому предмету абитуриент может набрать от 0 100 баллов. При этом к сдаче экзаменов в первом потоке допускаются абитуриенты, набравшие по результатам тестирования не менее 30 баллов по каждому из трёх предметов, причём сумма баллов должна быть не менее 140. На вход программы подаются сведения о результатах предварительного тестирования. Известно, что общее количество участников тестирования не превосходит 500.
В первой строке вводится количество абитуриентов, принимавших участие в тестировании, N. Далее следуют N строк, имеющих следующий формат:
<Фамилия> <Имя> <Баллы>
Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов, <Баллы> – строка, содержащая два целых числа, разделенных пробелом – баллы, полученные на тестировании по каждому из трёх предметов. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Пример входной строки:
Романов Вельямин 48 39 55
Напишите программу, которая будет выводить на экран фамилии и имена абитуриентов, допущенных к сдаче экзаменов в первом потоке. При этом фамилии должны выводиться в алфавитном порядке.
13) На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего.
На вход программе в первой строке подается число данных N о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате:
<Компания> <Улица> <Марка> <Цена>
где <Компания> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Марка> – одно из чисел – 92, 95 или 98, <Цена> – целое число в диапазоне от 1000 до 3000, обознача