ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Championship. March 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Gaby Ivanushka

Time limit: 1.0 second
Memory limit: 64 MB
Once upon a time there lived a tsar that has a daughter — Beautiful Vasilisa. There were many of the young men that wanted to marry her but she repelled all suitors. The tsar was tired of her jigs, he got angry and issued an order: "The first who solves my puzzle, will marry Vasilisa!" Ivanushka decided to try his fortune. He came to the tsar and the tsar told him: "This is a program for you. Input N numbers and the program will tell you who you should marry. I give you a day to think." Ivanuska looked at the program and got upset: there were unknown letters, omnifarious symbols. The time passed. Ivanushka has thought out nothing.
The program was as follows.
The C programThe Pascal program
 #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
   ("Beutiful Vasilisa");
  else printf
   ("Immortal Koshcei");
  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
   ('Beutiful Vasilisa')
  else writeln
   ('Immortal Koshcei');
 end.

Now you know this program. You may try to help Ivanushka.

Input

The first line of an input contains a positive number N ≤ 1000.

Output

You are to write to an output N numbers in one line. The tsar's program given those numbers should output a message "Beautiful Vasilisa" The numbers should be separated with a space. If several variants are possible choose any you like.

Sample

inputoutput
3
3 7 19
Problem Author: Nikita Shamgunov
Problem Source: The 3rd high school children programming contest, USU, Yekaterinburg, Russia, March 4, 2001
To submit the solution for this problem go to the Problem set: 1082. Gaby Ivanushka