1 задача

 

 

 

Задача 1 «Призы»

Формат входного файла

Первая строка входного файла содержит число n (2 ≤ n ≤ 100 000). Вторая строка этого файла содержит n целых чисел: a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹).

Формат выходного файла

Выходной файл должен содержать одну строку, содержащую n – 1 целых чисел: для каждого k от 2 до n должна быть выведена ценность приза, который достанется Петру, если он наберет k баллов.

Пример входных и выходных файлов

prizes.in	prizes.out
5 1 3 4 2 5	1 3 3 4

Решение задачи основано на классическом алгоритме поиска второго максимума в массиве. По мере ввода ценности очередного приза из входного файла будем вычислять две переменные: m1 –первый максимум и m2 - второй максимум и выводить в .выходной файл значение m2, т.к. по условию задачи перед получением приза Петром ведущий убирает один из призов, очевидно самый ценный, а значит Петру гарантированно достается второй максимум.

Приведем код решения на языке PABC

{основная идея: после ввода очередного приза}

{находить 2 максимума и выводить второй из них}

program prizes_1;

 var m1, m2, a: longint;

    i, n: longint;

    fin, fout: text;

  begin

    assign(fin, 'prizes.in');

    assign(fout, 'prizes.out');

    reset(fin);

    rewrite(fout);

    readln(fin, n);{количество призов}

    read(fin, m1, а);{считываем первые 2}

    if а > m1 then

  begin m2:=m1; m1:=a end;

    write(fout, m2,' ');{выводим первый результат}

    for i:=3 to n do {считываем остальные}

      begin

        read(fin, a);

        if a>=m1 then begin m2:=m1; m1:=a end

        else if a>m2 then m2:=a;

        write(fout, m2,' ');{выводим остальные}

      end;

    close(fin);

    close(fout);

end.

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