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

Разбирается решение олимпиадной задачи 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.

Желаю удачи!