Две несложные олимипадные задачи по программированию с математическим содержанием

Задача "Трамвай"

Трамвайная линия имеет вид прямой. Петя живет в N трамвайных остановках от метро. Метро находится у нулевой остановки, в точке с координатой 0.

Выходя из метро, Петя хочет попасть домой как можно быстрее, но он очень не любит ждать трамвай на остановке. Поэтому, если, подходя к очередной трамвайной остановке, он не видит трамвая, то идет пешком вдоль трамвайной линии. Если в какой-то момент Петя видит трамвай, то он может принять решение вернуться на остановку или продолжить свое движение к следующей остановке. Петя идет со скоростью U, трамвай едет со скоростью V. Нужно найти минимальное расстояние L, которое должно просматриваться перед нулевой остановкой, чтобы он мог идти со своей скоростью в сторону дома, не опасаясь, что трамвай его обгонит между остановками.

Формат входных данных

Во входном файле находятся три числа — N, U и V (N 1000, U и V — положительные вещественные), за которым будет следовать N вещественных чисел — X₁, X₂, ..., X_n ( 0 < X₁ < X₂ < ...< X_n < 10⁶), разделенных пробелами.

Формат выходных данных

В выходной файл ваша программа должна вывести число L с точностью до 10^-4.

Примеры

Решение

Рассмотрим положение Пети в некоторый момент, когда он находится в некоторой точке между остановками. Если он видит трамвай в этот момент, то у него есть два варианта: дойти до следующей остановки или вернуться на предыдущую. Чтобы минимизировать расстояние, необходимо выбрать из двух этих вариантов лучший. Понятно, что Петя должен оказаться на остановке одновременно с трамваем (ожидание нам ни к чему; если его исключить, то можно уменьшить дистанцию). Таким образом, нужно определить время, за которое трамвай доедет до предыдущей и до следующей остановки. Проделаем то же самое для Пети — посчитаем время его прихода на следующую остановку и на предыдущую. После этого можно выбрать лучший из этих двух вариантов и, решив уравнение, определить расстояние, которое должно просматриваться перед нулевой остановкой.

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

Здесь i — номер предыдущей остановки, а dist — расстояние, на которое Петя отдалился от предыдущей остановки. Из первого уравнения выразим dist:

и подставим его во второе уравнение:

перенесем все слагаемые с L в левую часть, а остальные — в правую:

теперь можно выразить L:

Таким образом, для любой пары последовательных остановок мы получили формулу для определения расстояния до нулевой остановки, на которое должен видеть Петя, чтобы не упустить трамвай. Так как трамвай может появиться в любой момент, то для получения окончательного ответа нужно перебрать все пары последовательных остановок и выбрать наибольшее из всех получившихся L. Из условия задачи можно понять, что L не может быть меньше нуля, т.е. в начале программы следует записать туда 0.

var
   x : array[0..1000] of double;
   i, n : longint;
   l, maxl, u, v : double;
begin
   read(n, u, v);
   x[0] := 0;
   maxl := 0;
   for i := 1 to n do  read(x[i]);
   for i := 0 to n - 1 do
    begin
      l := ((x[i + 1] - x[i])/u * v - (x[i] + x[i + 1]))/2;
      if l > maxl then maxl := l
    end;
   write(maxl:0:4)
end.

Дана последовательность, состоящая из 2N натуральных чисел. Известно, что все числа этой последовательности можно разбить на пары таким образом, что сумма чисел во всех парах будет одинаковой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары
1 + 99 = 77 + 23.

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

Первая строка содержит натуральное число M — количество тестов в файле. Первая строка каждого теста содержит число 2N — количество чисел в последовательности. В каждой из последующих 2N строчек содержится целое число от 1 до 109 — элементы последовательности (1 N 50 000).

Формат выходных данных

Ответом на тест является символ 1, если входную последовательность можно разбить на пары, произведения в которых были бы одинаковыми, и 0 в противном случае. Ответ на каждый тест следует выводить в отдельной строке.

Пример

Решение

Нам необходимо научиться решать задачу для одного теста, а затем просто запустить это решение для всех M тестов.

Обозначим сумму чисел за X. Допустим, у нас есть две разных пары чисел (Y, X — Y) и (Z, X — Z). Произведения этих чисел также должны быть равны, т.е.

.Y х (X - Y) = Z x (X - Z)

Перенесем X в левую часть:

X х (Y - Z) = (Y² - Z²) = (Y + Z) x (Y-Z)

По поставленному нами условию Y Z, а значит, мы можем разделить обе части на (Y - Z), после чего получим равенство X = Y + Z, т.е. Y и Z образуют пару, что противоречит поставленному условию (пары должны быть различны).

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

Будем делать это следующим образом: заведем массив из двух элементов, в котором будем хранить встретившиеся числа. Если очередное число уже есть в массиве, то не будем предпринимать никаких действий, иначе добавим его в массив. Если количество элементов в какой-то момент стало больше двух, то следует запомнить, что ответ должен быть 0 и считать оставшиеся числа массива, следя, чтобы нигде не произошло выходов за пределы массива.

Один из вариантов такой реализации приведен ниже:

var
   x : array[1..2] of longint;
   nownum, m, n, i, j, k, c : longint;
   flag, bad : boolean;
begin
   read(m);
   for k := 1 to m do
    begin
      // идем по всем тестам
     read(n);
     nownum := 0; // пока нет встретившихся чисел
     bad := false;
     // ничего плохого не случилось
     for i := 1 to n do
        begin
           read(c);
          flag := false;
          // не нашли среди имеющихся
         for j := 1 to nownum do
           // идем по имеющимся
           if x[j] = c then flag := true; // нашли
           if not flag then
               begin // не нашли
                    inc(nownum);
                    // увеличиваем количество встретившихся различных
                   if nownum > 2 then
                      begin
                         // больше двух
                        dec(nownum);
                        // чтобы не выйти за пределы - уменьшим
                        bad := true
                        // случилось плохое - переполнились
                     end
                 x[nownum] := c;
                 // запомним, что за число встретили
             end
       end;
      if bad then writeln(0)  // выводим ответ
             else writeln(1)
   end
end.