Programowanie i algorytmy

Schody do nieba, autostrada do piekła

To czy trafisz do nieba, czy do piekła, zależy od twoich dobrych uczynków, które stworzą ci odpowiednie schody. Każdy dobry uczynek, to kolejny stopień takich schodów. Natomiast złe uczynki tworzą schody do piekła. Każdy kolejny zły uczynek przybliża cię do wiecznego potępienia. Na twoje szczęście (lub nie) musisz wymazać z pamięci jeden uczynek. Dopiero po tym fakcie będzie zdecydowane, gdzie trafisz: do nieba, jeśli maksymalna liczba dobrych uczynków z rzędu będzie nie mniejsza niż maksymalna liczba złych uczynków.

Schody do nieba, to spójny podciąg reprezentujący wysokości stopni schodów. Taki ciąg musi być niemalejący i musi składać się z co najmniej dwóch różnych liczb. Liczba schodów, to liczba różnych liczb w tym podciągu.

Schody do piekła, to spójny podciąg reprezentujący wysokość  stopni schodów. Taki podciąg musi być nierosnący i składać się z co najmniej dwóch różnych liczb. Liczba schodów, to liczba różnych liczb w podciągu.

W danym ciągu znajdują się schody do nieba, jeśli maksymalna długość schodów do nieba jest nie mniejsza niż długość schodów do piekła (po usunięciu jednego wyrazu w ciągu).

Napisz program, który określi, czy zasłużyłeś na niebo, czy piekło, jeśli wiesz, że musisz z ciągu usunąć jedną liczbę i zależy ci, aby trafić do nieba.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę zestawów danych (n < 1001).

Każdy zestaw składa się z dwóch wierszy. W pierwszym wierszu jedna liczba t określająca długość ciągu (t < 10001), następnie w drugim wierszu t liczb naturalnych dodatnich, gdzie żadna jest nie większa niż milion. Gwarantuje się, że każdy ciąg zawiera co najmniej trzy różne liczby.

Wyjście

Dla każdego zestawu danych napis niebo, jeśli trafisz do nieba, w przeciwnym razie pieklo.

Przykład

Wejście:
2
12
1 2 3 2 3 5 7 6 5 3 4 6
10
9 8 7 6 5 4 3 2 3 2

Wyjście:
niebo
pieklo

Szkic rozwiązania

Rozwiązanie liniowe. W tym zadaniu należy rozpatrzeć kilka sytuacji. Najważniejsze z nich przedstawię na przykładach.

  1. 1 2 3 4 6 5 4 3 2 1 – przypadek, gdy ciąg malejący jest o 1 dłuższy od rosnącego i długość ta wystąpiła tylko raz. Po usunięciu dowolnego wyrazu z tego ciągu idziemy do nieba.
  2. 1 2 3 4 6 5 4 3 2 1 6 5 4 3 2 1 – w tym przypadku idziemy do piekła, ponieważ usunięcie jednego wyrazu z ciągu malejącego nic nie zmieni
  3. 1 2 3 6 5 6 5 4 3 2 – usunięcie pierwszej szóstki sprawi, że pójdziemy do nieba
  4. 1 2 7 10 8 9 8 7 6 5 – usunięcie liczby dziesięć sprawi, że pójdziemy do nieba

Dodatkowo dołączam test, który zatrzymał chociaż na chwilę każdego.

To zadanie jest łatwe!

Jak to mówią "Reklama dźwignią handlu!". Skoro tu jesteś, to przemówiła do ciebie nazwa zadania i masz nadzieję, że jest ona prawdziwa. Niestety, reklamy i spoty nie zawsze mówią prawdę i często czujemy się oszukani przez system. Czytając to zastanawiasz się, czy autor jest uczciwy i rzeczywiście umieścił łatwe zadanie, czy tylko chciał, aby ilość odwiedzin tej strony była większa? Przekonaj się sam czytając treść zadania:

Sprawdź, czy istnieje taki podciąg (niekoniecznie spójny) pierwszego ciągu, który jest równoważny drugiemu ciągowi.

Więcej

Wyszukiwarka

Firma "Fraktax" potrzebuje nowego wydajnego modułu do swojego najnowszego projektu - edytora tekstu, który będzie wyszukiwał liczbę wystąpień danej frazy. Firmie zależy, aby ich edytor był wydajniejszy, niż dostępne edytory na rynku. W tej chwili został ogłoszony przetarg na napisanie właśnie takiego modułu, więc jeśli chcesz do niego przystąpić, napisz swój moduł i sprawdź czy jest on wystarczająco wydajny.

Wejście

W pierwszym wierszu jedna liczba t określająca liczbę zdań do przeanalizowania (nie więcej niż 10000).

W drugim wierszu t zdań. Każde zdanie składa się z nie więcej niż 10000 znaków.

Następnie jedna liczba q - liczba zapytań (nie większa niż milion).

Każde zapytanie składa się z co najwyżej 20 znaków złożonych wyłącznie z małych lub dużych liter języka łacińskiego.

(plik z danymi do analizy nie przekracza 5 MB, żaden spójny podciąg tworzący wyraz złożony wyłącznie z małych lub dużych liter języka łacińskiego nie jest dłuższy niż 20 znaków. Znaki które mogą się pojawić: małe i duże litery języka łacińskiego, białe znaki, "?", "!", "-", ":","."  oraz ",")

Wyjście

Dla każdego zapytania liczba wystąpień szukanej frazy. Wielkość liter jest rozróżnialna.

Uwaga! Wolniejsze języki nie poradzą sobie z tym zadaniem.

Przykład

Wejście:
30
Stoi na stacji lokomotywa,
Ciezka, ogromna i pot z niej splywa:
Tlusta oliwa.
Stoi i sapie, dyszy i dmucha,
zar z rozgrzanego jej brzucha bucha:
Uch - jak goraco!
Puff - jak goraco!
Uff - jak goraco!
Wagony do niej podoczepiali
Wielkie i ciezkie, z zelaza, stali,
I pelno ludzi w kazdym wagonie,
A w jednym krowy, a w drugim konie,
A w trzecim siedza same grubasy,
Siedza i jedza tluste kielbasy,
A czwarty wagon pelen bananow,
A w piatym stoi szesd fortepianow,
W szostym armata - o! jaka wielka!
Pod kazdym kolem zelazna belka!
W siodmym debowe stoly i szafy,
W osmym sloo, niedzwiedz i dwie zyrafy,
W dziewiatym - same tuczone swinie,
W dziesiatym - kufry, paki i skrzynie,
A tych wagonow jest ze czterdziesci,
Sam nie wiem, co sie w nich jeszcze miesci.
Lecz chodby przyszlo tysiac atletow
I kazdy zjadlby tysiac kotletow,
I kazdy nie wiem jak sie wytezal,
To nie udzwigna, taki to ciezar.
Nagle - gwizd!
Brumbrumbrumbrum
10
wagon
lokomotywa
i
I
brumbrum
brum
to
czterdziesci
aa
Sam

Wyjście:
3
1
65
3
2
3
7
1
0
1

Szkic rozwiązania

Przykładowe rozwiązanie. Rozwiązanie podzieliłem na kilka kroków.

  1. Wyodrębniamy wszystkie wyrazy składające się z małych lub dużych liter
  2. Każdy wyraz rozkładamy na podwyrazy np. algoliga
    • algoliga
    • lgoliga
    • goliga
    • oliga
    • liga
    • lga
    • ga
    • a
  3. Następnie sortujemy wszystkie rozłożone wyrazy.
  4. Dla każdego zapytania wykorzystujemy przeszukiwanie binarne do znalezienia pierwszego wystąpienia szukanej frazy oraz ostatniego. Różnica pozycji jest szukaną wartością.

Liczby doskonałe

Liczba doskonała to taka, której suma dzielników właściwych jest jej równa. Do zbioru liczb doskonałych należy liczba 6, ponieważ:

D6 = {1, 2, 3, 6}

6 = 1 + 2 + 3

lub 28:

D28 = {1, 2, 4, 7, 14, 28}

28 = 1 + 2 + 4 + 7 + 14

Ciekawostką jest, że nie udało się nikomu jeszcze znaleźć nieparzystej liczby doskonałej, nawet nie istnieje na to dowód, czy jest taka. Nie wiadomo także, czy takich liczb jest nieskończenie wiele. Jednym ze sposobów szukania ich, jest określanie sum dzielników liczb w danym przedziale i badanie ich właściwości, i takie jest twoje zadanie. Dla danego przedziału [a, b], znajdź najmniejszą liczbę naturalną należącą do tego przedziału, której suma dzielników jest równa n (pod uwagę bierzemy wszystkie dzielniki naturalne danej liczby).

Uwaga! Algorytm wzorocowy oparty jest na wczytywaniu scanf'em i wypisuwaniu printf'em w języku C++.

 

Więcej

Więcej artykułów…

  1. Kości zostały rzucone
  2. Sinusoida