Важно
Решение задач
Разделы информатики

Разбор задачи C4 (демо ЕГЭ 2006)

Вступительные испытания в некоторый вуз состоят из трех экзаменов: математика (максимальный балл – 9), информатика (максимальный балл – 9), литература (максимальный балл – 5). На вход программе подаются сведения о сдаче этих экзаменов абитуриентами. В первой строке вводится количество абитуриентов N, во второй – количество мест K (K < N) на которые эти абитуриенты претендуют. Каждая из следующих N строк имеет следующий формат: <Фамилия> <оценка1> <оценка2> <оценка3>, где <Фамилия> – строка, состоящая не более, чем из 20 символов, оценки – числа от 0 до максимальной оценки по предмету соответственно. (Ноль ставится в случае, если экзамен не сдавался, например, после полученной на предыдущем экзамене двойки. Все баллы, большие 2, считаются удовлетворительными). Пример входных строк:

Иванов 8 9 3

Петров 2 0 0

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

Решение:

Чтобы было понятно, что такое полупроходной балл, рассмотрим пример.

Пусть есть 60 абитуриентов и 20 мест. Максимальный суммарный балл =9+9+5=23. После сдачи экзаменов 18 человек набрали сумму баллов ≥22. Еще 4 человека набрали 21 балл. 20-18=2, т.е. мест осталось 2, а абитуриентов 4. Поэтому при равных суммарных баллах примут только 2-х человек, а остальные 2-е не поступят.

Получается, 22 - проходной балл , а 21 - полупроходной.

Алгоритм программы такой:

  • Считывая очередную запись, подсчитываем сумму баллов школьника. В массиве, хранящем количество школьников по баллам, находим элемент, индекс которого равен полученной сумме, и увеличиваем его на 1. Если школьник сдает какой-либо экзамен на 2, то сумма его баллов для удобства приравнивается 0 или 1 - для Бейсика.
  • Затем, начиная с балла=23 (максимальный), считаем суммарное количество абитуриентов по баллам из массива, уменьшая индекс. Т.е. мы складываем количество абитуриентов с баллами: 23, 22, 21, 20... Делаем это до тех пор, пока количества мест K ≥ суммарного количества абитуриентов и сумма их баллов ≥9.(9 - минимально возможный балл). Индекс 1-го элемента массива, который не войдет в сумму - это полупроходной балл.
  • Если проходной балл набрали <K абитуриентов, то программа выведет количество абитуриентов, набравших полупроходной балл. Если проходной балл набрали ровно К абитуриентов, то программа выведет: "полупроходной балл отсутствует".

Программа написана на языках:

  • Паскаль (среда разработки Turbo Pascal 7.0),
  • Бейсик (среда разработки Quick Basic 4.5),
  • Алгоритмический язык (среда разработки Кумир 1.9.0).
  • Си (среда разработки Borland C++ 3.1),

Чтобы прочесть комментарии к программе, наведите мышью на соответствующую строку. Строки, снабженные комментарием, выделены фиолетовым цветом.

Напротив названия языка программирования в скобках содержатся ссылки на скачку исходников и ехе (исполняемых файлов).

Паскаль (исходник+exe-файл)Бейсик (исходник)
var masSumAb:array[0..23] of integer;
   c:char;
   i,K,N,mark1,mark2,mark3,sumMark,sumAb:integer;
begin
   readln(N);
   readln(K);
   for i:=0 to 23 do masSumAb[i]:=0;
   for i:=1 to N do
   begin
      repeat
        read(c)
      until c=' ';
     readln(mark1,mark2,mark3);
     if (mark1<3)or(mark2<3)or(mark3<3) then
        sumMark:=0
      else sumMark:=mark1+mark2+mark3;
      masSumAb[sumMark]:=masSumAb[sumMark]+1
   end;
   sumAb:=masSumAb[23];
    i:=23;
    while ((sumAb+masSumAb[i-1])<=K) and (i>9) do
    begin
      i:=i-1;
      sumAb:=sumAb+masSumAb[i]
    end;
   write(char(13)+char(10));
   if (sumAb<K)and(i>9) then
      writeln('poluprochodnoi ball nabrali ',
                  masSumAb[i-1],' chelovek')
    else writeln('poluprochodnoi ball otsutstvuet');
readln
end.		 DIM masSumAb(23) AS INTEGER
DIM i,j,K,N,mark1,mark2,mark3,sumMark,sumAb AS INTEGER
DIM str AS STRING
FOR i = 1 TO 23
    masSumAb(i) = 0
NEXT i
INPUT N
INPUT K
FOR i=1 TO N
  LINE INPUT str
   j=1
   c$=MID$(str, j, 1)
   WHILE NOT (c$=" ")
     j=j+1
     c$=MID$(str,j,1)
   WEND
  str=MID$(str,j+1,5)
   mark1=ASC(MID$(str,1,1))-ASC("0")
   mark2=ASC(MID$(str,3,1))-ASC("0")
   mark3=ASC(MID$(str,5,1))-ASC("0")
  IF (mark1<3) OR (mark2<3) OR (mark3<3) THEN
    sumMark=1
  ELSE sumMark=mark1+mark2+mark3
  END IF
  masSumAb(sumMark)=masSumAb(sumMark)+1
NEXT i
sumAb=masSumAb(23): i=23
WHILE (sumAb+masSumAb(i-1)<=K) AND (i>9)
   i=i-1
   sumAb=sumAb+masSumAb(i)
WEND
PRINT
IF (sumAb<K) AND (i>9) THEN
  PRINT "poluprochodnoi ball nabrali ";
            masSumAb(i-1);" chelovek"
ELSE PRINT "poluprochodnoi ball otsutstvuet"
END IF
END
Алгоритмический язык (исходник)Си (исходник+exe-файл)
алг
нач
   целтаб masSumAb[0:23]
   лит str
   сим c
   цел i,j,K,N,mark1,mark2,mark3,sumMark,sumAb
   ввод N
   ввод K
   нц для i от 0 до 23
      masSumAb[i]:=0
    кц
   нц для i от 1 до N
     ввод str
       j:=1
       нц
         c:=str[j]
         j:=j+1
       кц при c=" "
     mark1:=код(str[j])-код("0")
       mark2:=код(str[j+2])-код("0")
       mark3:=код(str[j+4])-код("0")
     если mark1<3 или mark2<3 или mark3<3
         то sumMark:=0
         иначе sumMark:=mark1+mark2+mark3
       все
       masSumAb[sumMark]:=masSumAb[sumMark]+1
   кц
   sumAb:=masSumAb[23]
    i:=23
    нц пока sumAb+masSumAb[i-1]<=K и i>9
      i:=i-1
      sumAb:=sumAb+masSumAb[i]
    кц
   вывод нс
   если sumAb<K и i>9
      то вывод "poluprohodnoi ball nabrali ",
                      masSumAb[i-1]," chelovek"
      иначе вывод "poluprohodnoi ball otsutstvuet"
    все
кон 		#include <stdio.h>
#include <string.h>
#include <conio.h>
void main()
{
    int masSumAb[24];
    int N,K,i,mark1,mark2,mark3,sumMark,sumAb;
    char name[21];
    scanf("%d",&N);
    scanf("%d",&K);
    for(i=0;i<24;i++) masSumAb[i]=0;
    for(i=0;i<N;i++){
      scanf("%s%d%d%d",name,&mark1,&mark2,&mark3);
      if((mark1<3)||(mark2<3)||(mark3<3)) sumMark=0;
        else sumMark=mark1+mark2+mark3;
        masSumAb[sumMark]++;
    }
    sumAb=masSumAb[23];
     i=23;
     while(((sumAb+masSumAb[i-1])<=K)&&(i>9)){
       i=i-1;
       sumAb+=masSumAb[i];
     }
    printf("\n");
    if((sumAb<K)&&(i>9))
       printf("poluprochodnoi ball nabrali: %d chelovek",
                 masSumAb[i-1]);
     else printf("poluprochodnoi ball otsutstvuet");
    getch();
}

Рассмотрим 2 случая работы программы:

  • полупроходного балла нет;
  • полупроходной балл есть.
Работа программы при отсутствии полупроходного балла:

Задача С4 ЕГЭ по информатике 2006 выполнение программы на Паскале, Бейсике и Си, когда полупроходного балла нет

Выполнение программы в Кумире, когда полупроходного балла нет

В данном случае поступили абитуриенты: Иванов (23 балла), Смирнов (23 балла) и Сидоров (21 балл). Остальные абитуриенты набрали <21 балла, поэтому полупроходного балла нет.
Работа программы, когда полупроходной балл есть:

Выполнение программы на Паскале, Бейсике и Си, когда полупроходной балл есть

Выполнение программы в Кумире, когда полупроходной балл есть

В данном случае мы добавили к предыдущему примеру еще одну запись: "Мухина 8 9 4". В результате получили, что поступили 2-е человек, набравших 23 балла: Иванов и Смирнов. А еще 2-е набрали полупроходной балл, равный 21-у: Сидоров и Мухина. Свободных мест - 3, а претендующих абитуриентов - 4.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В, 2012-2015. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта