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

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

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

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В некотором царстве, в некотором государстве жил-был царь, и была у него дочь — Василиса Прекрасная. Многие хотели жениться на ней, но она всем отказывала. Надоело это царю, рассердился он и повелел: "Первый, кто решит мою задачку, получит Василису Прекрасную в жёны". Решил тогда Иванушка-дурачок счастья попытать. Пришёл к царю, а тот ему и говорит: "Вот тебе программка, введи ей N чисел, она тебе и выведет на ком жениться. Даю тебе день на размышления". Посмотрел Иванушка на программу ту и запечалился: буквы какие-то непонятные, значки всякие, тут не только дурак, но и умный голову сломает. А между тем время кончается. Так и не придумал Иванушка ничего.
А программка та была вот такая:
На языке CНа языке Pascal
 #include <stdio.h>  
 long c;
 long A[N];
 
 long P(long l, long r)
 {
  long x=A[l],
       i=l-1,
       j=r+1,
       t;
  while(1)
  {
   do{--j; ++c;}
   while(A[j]>x);
   do{++i; ++c;}
   while(A[i]<x);
   if(i<j)
   {
    t=A[i];
    A[i]=A[j];
    A[j]=t;
   }
   else return j;
  }
 }
 
 void Q(long l, long r)
 {
  long n;
  if(l<r)
  {
   n=P(l,r);
   Q(l,n);
   Q(n+1,r);
  }
 }
 
 int main(void)
 {
  c=0;
  for(long i=0; i<N; ++i)
   scanf("%ld", &A[i]);
  Q(0,N-1);
  if(c==(N*N+3*N-4)/2)
   printf
   ("Василиса Прекрасная");
  else printf
   ("Кощей Бессмертный");
  return 0;
 }
 var A:array [1..N] of 
longint;
     c:longint;
     i:integer;
 function 
P(l,r:longint):longint;
 var i,j,t,x:longint;
 begin
  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 P:=j; exit end
  end
 end;
 
 procedure Q(l,r:longint);
 var n:longint;
 begin
  if l<r then
  begin
   n:=P(l,r);
   Q(l,n);
   Q(n+1,r)
  end
 end;
 
 begin
  c:=0;
  for i:=1 to N do 
read(A[i]);
  Q(1,N);
  if c=(N*N+3*N-4) div 2 
then
   writeln
   ('Василиса Прекрасная')
  else writeln
   ('Кощей Бессмертный');
 end.

Теперь, когда вы знаете программу, вы можете попытаться помочь Иванушке.

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

В первой строке содержится положительное число N ≤ 1000.

Результат

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

Пример

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