Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1877

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1877

Sansa's Snow Castle

 

By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

Robin: "What are you doing?"
Sansa: "I'm building my home, Winterfell."

Sansa is building a snow castle at the garden of The Eyrie. The snow castle is meant to resemble the actual castle of Winterfell.

The snow castle can be described as a sequence of N snow towers, numbered from 1 to N from the left to the right. The height of tower i (1 ≤ i ≤ N) is equal to hi centimeters.

Sansa says the castle is beautiful if it consists on a sequence of K "peaks" alternated with K-1 "valleys", like the actual castle of Winterfell. In other words, the castle is beautiful if there is a sequence of K towers T1 < T2 < ... < TK such that:

  • The heights of the towers in the interval [1,T1] are in ascending order;
  • There is a "valley" in the interval [Ti,Ti+1], for all 1 ≤ i < K;
  • The heights of the towers in the interval [TK,N] are in descending order.

There is a "valley" in an interval [A, B] if B ≥ A+2 and there is some tower J, A ≤ J ≤ B, such that the heights of the towers in the interval [A,J] are in descending order, and the heights of the towers in the interval [J,B] are in ascending order.

Help Sansa to determine whether her castle is beautiful or not!

 

Input

 

The first line contains two integers N  and K (1 ≤ N ≤ 1000, 1 ≤ K ≤ N). The second line contains N integers h1, h2, ..., hN (1 ≤ hi ≤ 100), the heights of the towers, in centimetres. The first and the last tower will always be 1 centimeter high. No two consecutive towers will have the same height.

 

Output

 

Print a line containing the word beautiful if the given castle is beautiful, or the word ugly otherwise.

 

 

 

Input Samples Output Samples

9 3
1 2 3 2 4 3 1 2 1

beautiful

 

 

 

5 3
1 2 1 2 1

ugly

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming


n, k = [int(x) for x in input().split()]
e = [int(x) for x in input().split()]
p = v = 0

a = ''
for c, i in enumerate(e[1:]):
   if i > e[c]:
      if a == 'd': v += 1
      a = 's'
   elif i < e[c]:
      if a == 's': p += 1
      a = 'd'

print('beautiful') if k == p == v+1 else print('ugly')
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
9 3
1 2 3 2 4 3 1 2 1

Output

x
–
+
cmd
beautiful
Advertisements

Demonstration

Previous
#1876 Beecrowd Online Judge Solution 1876 Rabiola Solution in C, C++, Java, Js and Python
Next
#1880 Beecrowd Online Judge Solution 1880 Renzo and the Palindromic Decoration Solution in C, C++, Java, Js and Python