Вы не зарегистрированы

Авторизация



Разбор задач С4

24 replies
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.

О задаче С4 нужно знать следующее:

1. Минимум синтаксических ошибок. Две разные синтаксические ошибки - минус балл.

2. Требование эффективности алгоритма. Следовательно, минимум использования памяти и минимум проходов по массивам.

Начнем с такой задачки. Это ЕГЭ-2008.

На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат: <Фамилия> <Инициалы> <телефон>, где <Фамилия> - строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> - семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «-». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом. Пример входной строки:

Иванов П.С. 555-66-77

Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами.

Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.

 

Теперь решение на Паскале:

var
 c: set of byte;
 n, i, k, j, l: byte;
 b: char;
 begin
 assign (input, 'input.txt'); reset (input);
 assign (output, 'output.txt'); rewrite (output);
 readln (n);    {количество сотрудников}
 k:=0;    {счетчик подразделений}
 c:=[ ];    {множество для хранения номеров подразделений}
 for i:=1 to n do
    begin
     j:=0;
     while j<>2 do
        begin
         read (b);
         if b='-' then j:=j+1;
        end;
     readln (l); {считываем номер подразделения}
     if not (l in c) {если он еще не встречался}
        then
         begin
            k:=k+1; {прибавляем единицу к счетчику}
            c:=c+[l]; {помещаем номер подразделения во множество}
         end;
     end;
    writeln (n/k:5:3); {находим среднее количество сотрудников в подразделении}
    close (input);
    close (output);
 end.
 

Сразу хочу отметить, что это решение предложено одним из моих учеников, за что ему отдельное Браво!

Небольшой комментарий. Здесь не нужно хранить фамилии и имена, не нужно хранить полные номера телефонов. Следовательно, нам интересны только последние две цифры телефона, которые мы отсекаем и анализируем. Всего различных двузначных чисел 100 штук - от 00 до 99. Следовательно для их хранения нам можно завести множество.

Смотрем на последние две цифры телефона. Если они уже встречались, мы просто пропускаем их. Если телефон до этого не встречался, то мы помещаем его в множество и прибавляем единицу к счетчику подразделений.

После обработки списка делим количество всех сотрудников на количество подразделений.

 

Лапшева Елена, Саратов
Людмила Ивановна Балясова
Фото пользователя Людмила Ивановна Балясова
На сайте с: 25/10/2008
Баллы: 119
Пользователь в офф-лайн. Последнее посещение 4 years 19 недель назад.
На: Разбор задач С4

 

Елена Евгеньевна! Спасибо за задачу и ее решение. Уважаю, когда организована в программе работа с файлами!!!

Привожу текст еще одной задачи С4 с ЕГЭ 2008:

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: <Фамилия>< Инициалы>< номер школы>, где <Фамилия> - строка, состоящая на более чем из 20 символов, <Инициалы> - строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> -  не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки: Иванов П.С. 57
Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, из каких школ было меньше всего участников олимпиады ( но из этих школ был хотя бы один участник).

Её решение (один из вариантов) мы разбирали на областном семинаре по профильному обучению.

Может кто-то найдет более красивое решение.

 

С уважением Людмила Балясова
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
На: Разбор задач С4

Вот мое решение.

Я создала одномерный массив, где индексы элементов - номера школ, а значения элементов - количество учеников, выступавших от этой школы.

Первый цикл - обнуление массива.

Второй цикл - считывание входных данных и заполнение массива.

Третий цикл (while) - поиск первой школы (с минимальным номером), котороя предоставила хотя бы одного ученика.

Четвертый цикл - посик минимального, но не нулевого элемента массива.

Пятый цикл - вывод номеров элементов массива, чье значение равняется минимальному (но не нулевому).

Мое решение - три прохода по массиву (если не считать ввода данных).

var
 a: array [1..99] of integer;
 i, k, n, m: integer;
 s, t: string;
begin
 assign (input, 'input.txt'); reset (input);
 assign (output, 'output.txt'); rewrite (output);
 readln (n);
 for i:=1 to 99 do
   a[i]:=0;
 for i:=1 to n do
  begin
   readln (s); {считываем строку}
   k:=length (s); {определяем ее длину}
   t:=s[k-1]+s[k]; {отрезаем последние два символа - это или двузначное число, или пробел и однозначное число}
   val (t, m, k); {переводим строку в число - номер школы}
   a[m]:=a[m]+1; {прибавляем единицу к количеству детей от данной школы}
  end;
  i:=1;
  while a[i]=0 do i:=i+1; {ищем первую участвующую школу}
  m:=a[i];
  for k:=i to 99 do
   if (a[k]<>0) and (a[k]<m) {поиск минимального ненулевого элемента}
    then m:=a[k];
  for i:=1 to 99 do
   if a[i]=m then write (i:3); {вывод результата}
 close (input);
 close (output);
end.
 

 

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
На: Разбор задач С4

Почему за первоначальное минимальное значение берется 99, а если от каждой из кол выступало по 100 учеников и более? Ваше решение тогда не пройдет...

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
На: Разбор задач С4

Очередная задача из ЕГЭ-2008.

На вход программе подаются сведения обо всех учениках некоторой средней школы. В первой строке сообщается количество учеников N, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <класс>, где <Фамилия> - строка, состоящая не более чем из 20 символов, <Имя> - строка, состоящая не более чем из 15 символов, <класс> - год обучения (от 1 до 12) и латинская заглавная буква (от «A» до «Z») без пробела. <Фамилия> и <Имя>, а также <Имя> и <класс> разделены одним пробелом. Пример входной строки:
Иванов Петр 10А
В рамках одной параллели классы нумеруются буквами подряд, начиная с «А». В некоторых параллелях классов может не быть совсем.
Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию о параллелях (годе обучения) с наибольшем количеством классов. Программа должна выводить на экран в первой строке количество классов в искомых параллелях, а во второй строке – номера этих параллелей в порядке возрастания через пробел. Например:
4
1  3  7 11

Решение на Паскале

var
a: array [1..12] of char;
i, j, n, m, err: integer; k: char;
s, t: string;
begin
assign (input, 'input.txt');
assign (output, 'output.txt');
reset (input);
rewrite (output);
readln (n);
for i:=1 to 12 do a[i]:=' '; {В этом массиве мы будем хранить последнюю букву для каждой параллели}
for i:=1 to n do begin
readln (s);
j:=length (s); {Так как номер параллели и буква - это последние символы, то нам не интересно все остальное}
k:=s[j]; {Это буква класса}
j:=j-1;
t:='';
while s[j]<>' '
do begin
t:=s[j]+t;
j:=j-1;
end;
val (t, m, err); {Номер параллели}
if a[m] < k then a[m]:=k; {Если встретилась более "старшая" буква, записываем ее в массив в элемент, соответствующий параллели}
end;
k:=a[1]; {Ищем "максимальную" букву}
for i:=1 to 12 do
if a[i] > k
then
k:=a[i];
m:=ord(k)-ord('A')+1; {Находим количество классов в самой длинной параллели}
writeln (m);
for i:=1 to 12 do
if a[i]=k then write (i:3); {Выводим номера этих параллелей}
close (input);
close (output);
end.
 

Лапшева Елена, Саратов
Людмила Ивановна Балясова
Фото пользователя Людмила Ивановна Балясова
На сайте с: 25/10/2008
Баллы: 119
Пользователь в офф-лайн. Последнее посещение 4 years 19 недель назад.
Язык программирования С++

 


При решении заданий части С можно использовать, в том числе, и язык программирования С.

 Для интересующихся информация об очень полезной книге.
Книга написана Бьерном Страуструпом - автором языка программирования C++ — и является каноническим изложением возможностей этого языка.
Помимо подробного описания собственно языка, на страницах книги вы найдете доказавшие свою эффективность подходы к решению разнообразных задач проектирования и программирования. Многочисленные примеры демонстрируют как хороший уровень стиль программирования на С-совместимом ядре C++, так и современный объектно-ориентированный подход к созданию программных продуктов. Третье издание бестселлера было существенно переработано автором. Результатом этой переработки стала большая доступность книги для новичков. В то же время текст обогатился сведениями и методиками программирования, которые могут оказаться полезными даже для опытных специалистов по C++. Не обойдены вниманием и нововведения языка: стандартная библиотека шаблонов (STL), пространства имен (namespaces), механизм идентификации типов во время выполнения (RTTI), явные приведения типов (cast-операторы) и другие. Настоящее специальное издание отличается от третьего добавлением двух новых приложений (посвященных локализации и безопасной обработке исключений средствами стандартной библиотеки), многочисленными уточнениями в тексте, а также исправлением множества опечаток. Книга адресована программистам, использующим в своей повседневной работе C++. Она также будет полезна преподавателям, студентам и всем, кто хочет ознакомиться с описанием языка «из первых рук».

Скачать книгу можно http://av-school.ru/down/o-103.html
 

 

С уважением Людмила Балясова
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
Очередная задача

На вход программе подаются сведения о пассажирах, забронировавших по интернету авиабилеты (только тех, у кого время бронирования еще не истекло). В первой строке задано текущее время: через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа). Во второй строке сообщается количество пассажиров N, которое не меньше 3, но не превосходит 1000. Каждая из следующих N строк имеет следующий формат: <Фамилия> <время окончания брони>, где <Фамилия> - строка, состоящая не более чем из 20 символов, <время окончания брони> - через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа). <Фамилия> и <время окончания брони> разделены одним пробелом. Сведения отсортированы в порядке времени, когда производилось бронирование. Все значения времени относятся к текущим суткам.
Требуется написать эффективную программу, которая в хронологическом порядке (то есть в порядке возрастания значения времени окончания брони) выедет фамилии пассажиров, у которых в ближайшие 3 часа текущего дня закончится броня.
Пример входных данных:
10:00
3
Иванов 13:00
Петров 10:00
Сидоров 13:12
Результаты работу программы для этого примера:
Петров
Иванов

Решение можно посмотреть здесь.

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
На: Очередная задача

С водом данных - тот же вопрос, что и в предыдущей задаче. Длина фамилии? Время перевести в целое число.

А теперь про сортировку. Вы "Аркаша" слишком торопитесь и не читаете условие задачи внимательно. Нужно отсортировать в порядке времени как закончится броня, а не по времени бронирования. Будьте внимательны при прочтении условия задачи!!! ;)

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
На: Разбор задач С4

А я не знаю Бейсик. ;)

Проблема в этой задаче - считать данные, так как поле Фамилия - неизвестной длины. Номер телефона содержит в себе знаки "-", следовательно его нельзя считать одним махом. Нужно вычленять из него последние две цифры и преобразовывать его в число. Может быть, в Бейсике это так легко, как у Вас, но я что-то в этом сомневаюсь. :)

То есть я хочу сказать, что в задачах С4 самой большой проблемой является организация ввода данных!

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
Очередная задача С4

Не разбор, а скорее просто решение очередной задачи С4 я привожу здесь.

Лапшева Елена, Саратов
Елена Евгеньевна Лапшева
Фото пользователя Елена Евгеньевна Лапшева
На сайте с: 17/12/2008
Баллы: 71
Пользователь в офф-лайн. Последнее посещение 8 лет 49 недель назад.
Очередная задача С4

Вот здесь разобрано решение очередной задачи С4 из ЕГЭ-2008.

Лапшева Елена, Саратов
ЕГЭ по информатике