1082 Timus answer/Решение задачи 1082


№1082
http://acm.timus.ru/problem.aspx?space=1&num=1082
ЖМИ ДАЛЕЕ>>>


РЕШЕНИЕ:

PASCAL

{A}
Var
 I,N: Longint;
Begin
 Readln(N);
 For I:=1 to N do begin
Write(I);
 IF I<>N then Write(' ');
 End;
end.

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
В некотором царстве, в некотором государстве жил-был царь, и была у него дочь — Василиса Прекрасная. Многие хотели жениться на ней, но она всем отказывала. Надоело это царю, рассердился он и повелел: "Первый, кто решит мою задачку, получит Василису Прекрасную в жёны". Решил тогда Иванушка-дурачок счастья попытать. Пришёл к царю, а тот ему и говорит: "Вот тебе программка, введи ей 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

Ярлыки: