Поиск по этому блогу

среда, 15 февраля 2017 г.

Маршрутное такси

Разбирается решение олимпиадной задачи I Всероссийской заочной олимпиады школьников по информатике 2006/2007 учебный год. Буду рад, если кому-нибудь из коллег или школьников, материал будет полезен в подготовке к олимпиадам.

Задача

В час пик на остановку одновременно подъехали три маршрутных такси, следующие по одному маршруту, в которые тут же набились пассажиры. Водители обнаружили, что количество людей в разных маршрутках разное, и решили пересадить часть пассажиров так, чтобы в каждой маршрутке было поровну пассажиров. Требуется определить, какое наименьшее количество пассажиров придется при этом пересадить.

Формат входных данных
Во входном файле записано три натуральных числа, не превосходящих 100 - количества пассажиров в первой, второй и третьей маршрутках соответственно.
Формат выходных данных
В выходной файл выведите одно число - наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).
Примеры
b_in.txt
b_out.txt
1 2 3
1
99 100 100
IMPOSSIBLE
Решение.
Находим общее количество пассажиров и проверяем, делится ли оно на 3 нацело. Если да – начинаем работать, в противном случае– выдаем сообщение "impossible". Находим среднее значение (sp). Далее определяем разность количества пассажиров в каждом такси со средним значением, р1, р2, р3 соответственно и упорядочиваем эти разности по возрастанию (в р1 теперь точно не хватает, а в р2 – лишние). Досаживаем в р1 до среднего (пока эта разность не станет равной р1=0), уменьшая при этом р3 и считаем количество пересаженных (Р). Здесь может случиться две ситуации: первая, в р3 еще остались лишние (т.е. в р2 тоже не хватало) мы их добавляем к Р; вторая, р3 >0 (т.е. не хватает), значит оставшиеся пассажиры находятся в р2 и мы их добавляем к пересаженным (Р).
var
            m, n, k,P,p1,p2,p3,s, sp:integer;
            f,f1:text;
begin
{Открываем файлы для чтения исходных данных b_in.txt и записи результата b_out.txt }
            assign(f, ‘b_in.txt’);
                reset(f);
                assign(f1,’ b_out.txt’);
                rewrite(f1);
            reladln(m,n,k);
            s:=m+n+k;{Находим общее количество пассажиров}
            {Проверяем на кратность 3}
            if s mod 3 <>0 then
                        Write(f1,’ IMPOSSIBLE’)
                 else
     begin
{Находим среднее число пассажиров, переводя результат в целое число с помощью функции trunk()}
                        sp:=trunc((m+n+k)/3);
{Находим разности пассажиров}
                        p1 = m – sp; p2 = n – sp; p3 = k – sp;
{Упорядочиваем разности}
If p1>p2 then begin s:=p1; p1:=p2; p2:=s; end;
                        If p2>p3 then begin s:=p2; p2:=p3; p3:=s; end;
                        If p1>p2 then begin s:=p1; p1:=p2; p2:=s; end;
{Обнуляем количество пересадок}
                        P:=0;
{ Досаживаем в р1 до среднего из р3}
                        Repeat
                          p1:=p1+1;
                          p3:=p3-1;
                          P:=P+1;
                        Until p1=0;
                        If p3 > 0 then P = P + p3 else P = P + p2;
{Выводим результат – количество пересадок}
                        Write(f1,P);
                 end;
{Закрываем файлы}
            close(f); close9f1);
end.

Желаю удачи!

Комментариев нет:

Отправить комментарий