Подготовка к ЕГЭ. Разбор решения задания С4

Подготовка учащихся к ЕГЭ Решение задач повышенной сложности С4 Разбор задач на конкретном примере, с пояснениями по основным моментам алгоритма решения 2016-2017уч.г.

Хитрости применённые в программе • Работа с данными «Время», в программе они описываются как  • • Char: ­ символьный ввод времени преобразуется в числовое  десятичное значение времени, для удобства определения  промежутков времени; ­ запись «:» в показании времени аннулируется повторным  считыванием символа, например  время 12 : 23  с помощью  оператора READ (c, c1) считываются символы отвечающие за  часы, следующий оператор READ (c, с, c1) содержит три  параметра, один из которых повторяется и за счёт этого  считывается в «с» сначала «:», а затем в эту­же переменную  считывается символ отвечающий за количество десяток в записи  минут, при этом значение  «:» теряется безвозмездно.

За­да­ние 27 № 4571.        На вход про­грам­ме по­да­ют­ся све­де­ния о пас­са­жи­рах, же­ ла­ю­щих сдать свой багаж в ка­ме­ру хра­не­ния на за­ра­нее из­вест­ ное время до по­лу­но­чи. В пер­вой стро­ке со­об­ща­ет­ся число  пас­са­жи­ров N, ко­то­рое не мень­ше 3, но не пре­вос­хо­дит 1000;  во вто­рой стро­ке – ко­ли­че­ство ячеек в ка­ме­ре хра­не­ния М, ко­ то­рое не мень­ше 10, но не пре­вос­хо­дит 1000. Каж­дая из сле­ду­ ю­щих N строк имеет сле­ду­ю­щий фор­мат:       <Фа­ми­лия> <время сдачи ба­га­жа> <время осво­бож­де­ния  ячей­ки>, где <Фа­ми­лия> – стро­ка, со­сто­я­щая не более чем из  20 не­про­бель­ных сим­во­лов; <время сдачи ба­га­жа> – через  двое­то­чие два целых числа, со­от­вет­ству­ю­щие часам (от 00 до  23 – ровно 2 сим­во­ла) и ми­ну­там (от 00 до 59 – ровно 2 сим­во­ ла); <время осво­бож­де­ния ячей­ки> имеет тот же фор­мат.

<Фа­ми­лия> и <время сдачи ба­га­жа>, а также <время сдачи ба­га­жа>  и  <время  осво­бож­де­ния  ячей­ки>  раз­де­ле­ны  одним  про­бе­лом.  Время  осво­бож­де­ния боль­ше вре­ме­ни сдачи.              Све­де­ния от­сор­ти­ро­ва­ны в по­ряд­ке вре­ме­ни сдачи ба­га­жа. Каж­до­му  из пас­са­жи­ров в ка­ме­ре хра­не­ния вы­де­ля­ет­ся сво­бод­ная ячей­ка с ми­ни­ маль­ным но­ме­ром. Если в мо­мент сдачи ба­га­жа сво­бод­ных ячеек нет, то  пас­са­жир ухо­дит, не до­жи­да­ясь осво­бож­де­ния одной из них. Тре­бу­ет­ся  на­пи­сать про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ ва­ния,  на­при­мер  Borland  Pascal  7.0),  ко­то­рая  будет  вы­во­дить  на  экран  для  каж­до­го  пас­са­жи­ра  номер  ему  предо­став­лен­ной  ячей­ки  (можно  сразу после ввода дан­ных оче­ред­но­го пас­са­жи­ра). Если ячей­ка пас­са­жи­ ру не предо­став­ле­на, то его фа­ми­лия не пе­ча­та­ет­ся.

При­мер вход­ных дан­ных: 3                                            { число пассажиров } 10                                          {число ячеек в камере} Ива­нов 09:45 12:00 Пет­ров 10:00 11:00 Си­до­ров 12:00 13:12   Ре­зуль­тат ра­бо­ты про­грам­мы на этих вход­ных дан­ных: Ива­нов 1 Пет­ров 2 Си­до­ров 1

По­яс­не­ние. •      Про­грам­ма верно чи­та­ет вход­ные дан­ные, сразу за­по­ми­ ная толь­ко время окон­ча­ния хра­не­ния ба­га­жа в мас­си­ве, со­ от­вет­ству­ю­щем  ячей­кам  ка­ме­ры  хра­не­ния.  Под­хо­дя­щая  ячей­ка  опре­де­ля­ет­ся  путём  по­сле­до­ва­тель­но­го  про­смот­ра  эле­мен­тов  этого  мас­си­ва  до  пер­во­го  сво­бод­но­го  или  та­ко­ го, в ко­то­ром за­пи­са­но время окон­ча­ния хра­не­ния, не пре­ вос­хо­дя­щее те­ку­ще­го вре­ме­ни сдачи оче­ред­но­го ба­га­жа. В  слу­чае  удач­но­го  вы­бо­ра  ячей­ки  фа­ми­лия  и  номер  ячей­ки  рас­пе­ча­ты­ва­ют­ся.  Баллы  на­чис­ля­ют­ся  толь­ко  за  про­грам­ му,  ко­то­рая  ре­ша­ет  за­да­чу  хотя  бы  для  част­но­го  слу­чая.  Время  можно  как  пе­ре­во­дить  в  ми­ну­ты,  так  и  хра­нить  в  виде  стро­ки,  срав­ни­вая  затем  стро­ки  не­по­сред­ствен­но.  В  по­след­нем слу­чае упро­ща­ет­ся ввод дан­ных.

Пример программы на языке PascalABC                                   Описание переменных program tr;      var p      :   array[1..10] of integer;            c,c1  :   char;        i,j,N,K  :   integer;          name  :   string; time1,time2 :   integer;

begin readln(N,K);                                                        {ввод  количества пассажиров и ячеек хранения } for i:=1 to K do  p[i]:=0;                                     { Задание исходных данных содержимого ячеек} for i:=1 to N do                                        { Организация типовой работы с каждым пассажиром}     begin       name := '';                                                      {Исходное значение имени пассажира  ­ «пусто»}       repeat                            {Организация в цикле по символьного считывания фамилии пассажира}       read(c);                         {Считывания с клавиатуры, во время набора фамилии, одного символа }       name := name + c ;                          {«Склеивание» фамилии пассажира из набранных символов}       until c=' ';             {считана фамилия, концом операции  конкатенации служит знак пробел “  ”}       read(c,c1);                                                                      {считаны символы часа первого времени}       time1:=60*((ord(c)­ord('0'))*10+ ord(c1)­ord('0'));           {перевод часов из «60» в «10» систему}         read(c,c,c1);                                                     {пропущено двоеточие, и считаны символы минут}       time1:=time1+(ord(c)­ord('0'))*10+ord(c1)­ord('0');         {перевод минут из «60» в «10» систему}        read(c,c,c1);                                                                   {считаны символы часа второго времени}       time2:=60*((ord(c)­ord('0'))*10+ ord(c1)­ord('0'));           {перевод часов из «60» в «10» систему}         readln(c,c,c1);                                                   {пропущено двоеточие, и считаны символы минут}       time2:=time2+(ord(c)­ord('0'))*10+ord(c1)­ord('0');       {перевод минут из «60» в «10» систему}            for j:=1 to K do   if p[j] <= time1 then   begin      {организация поиска ближайшего времени}         p[j]:=time2;     writeln(name,' ',j);     break;        {вывод времени , указание ФИО и останов программы}                                                                          end;     end; end.

Разбор полетов • Задача решается «простыми» операторами, каждое действие в отдельности доступно для понимания. • Основной проблемой является подход к решению, который реализован через переход от времени к числам. • Дальнейшие действия сводятся к алгоритму «поиск минимального».