ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат школьников. Март 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

A. Иванушка-дурачок

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В некотором царстве, в некотором государстве жил-был царь, и была у него дочь — Василиса Прекрасная. Многие хотели жениться на ней, но она всем отказывала. Надоело это царю, рассердился он и повелел: "Первый, кто решит мою задачку, получит Василису в жёны". Решил тогда Иванушка-дурачок счастья попытать. Пришёл к царю, а тот ему и говорит: "Вот тебе программка, введи ей N чисел, она тебе и выведет, на ком жениться. Даю тебе день на размышления". Посмотрел Иванушка на программу ту и запечалился: буквы какие-то непонятные, значки всякие, тут не только дурак, но и умный голову сломает. А между тем время кончается. Так и не придумал Иванушка ничего.
А программка та была вот такая:

C++

#include <cstdio>

const int N = ...;

int A[N];

int Q(int l, int r)
{
    if (l >= r)
        return 0;

    int m;
    int c = 0;
    int x = A[l];
    int i = l - 1;
    int j = r + 1;
    while (true)
    {
        do
        {
            --j;
            ++c;
        }
        while (A[j] > x);

        do
        {
            ++i;
            ++c;
        }
        while (A[i] < x);

        if (i < j)
        {
            int t = A[i];
            A[i] = A[j];
            A[j] = t;
        }
        else
        {
            m = j;
            break;
        }
    }

    return c + Q(l, m) + Q(m + 1, r);
}

int main()
{
    for (int i = 0; i < N; ++i)
        scanf("%d", &A[i]);

    if (Q(0, N - 1) == (N * N + 3 * N - 4) / 2)
        printf("Vasilisa the Beautiful\n");
    else
        printf("Koschei the Immortal\n");
    return 0;
}

Pascal

const
    N = ...;

var
    A: array [1..N] of integer;

function Q(l, r: integer): integer;
var
    m, c: integer;
    i, j, t, x: integer;
begin
    if l >= r then
        exit;
    
    c := 0;
    x := A[l];
    i := l - 1;
    j := r + 1;
    while true do
    begin
        repeat
            dec(j);
            inc(c)
        until A[j] <= x;
        
        repeat
            inc(i);
            inc(c)
        until A[i] >= x;
        
        if i < j then
        begin
            t := A[i];
            A[i] := A[j];
            A[j] := t
        end
        else 
        begin
            m := j;
            break
        end
    end;        
    
    Q := c + Q(l, m) + Q(m + 1, r)
end;

var
    i: integer;

begin
    for i := 1 to N do 
        read(A[i]);
    
    if Q(1, N) = (N * N + 3 * N - 4) div 2 then
        writeln('Vasilisa the Beautiful')
    else 
        writeln('Koschei the Immortal')
end.

Python

def Q(l: int, r: int) -> int:
    if l >= r:
        return 0

    c = 0
    x = A[l]
    i = l - 1
    j = r + 1
    while True:
        while True:
            j -= 1
            c += 1
            if A[j] <= x:
                break

        while True:
            i += 1
            c += 1
            if A[i] >= x:
                break

        if i < j:
            A[i], A[j] = A[j], A[i]
        else:
            m = j
            break

    return c + Q(l, m) + Q(m + 1, r)


N = ...
A = [int(x) for x in input().split()][0:N]

if Q(0, N - 1) == (N * N + 3 * N - 4) / 2:
    print('Vasilisa the Beautiful')
else:
    print('Koschei the Immortal')
Теперь, когда вы знаете программу, вы можете попытаться помочь Иванушке.

Исходные данные

В единственной строке содержится целое число N — значение константы из программы царя (1 ≤ N ≤ 1000).

Результат

Выведите N целых чисел в пределах от −109 до 109, таких, что если ввести их в программу, данную царём, то она выдаст "Vasilisa the Beautiful". Числа должны быть разделены пробелами. Если возможно несколько вариантов, выведите любой.

Пример

исходные данныерезультат
3
3 7 19
Автор задачи: Никита Шамгунов
Источник задачи: Третье командное соревнование школьников Свердловской области по программированию, 4 марта 2001
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1082. Иванушка-дурачок