Finále

A: Barikády

Řešení (Zadání úlohy)

Zjednodušení zadání

Co vlastně chceme zařídit? Dostaneme výšky barikád a chceme, aby v nich byl nějaký zub. Tedy chceme takové výšky barikád, aby celou dobu nebyly jen buď rostoucí, nebo jen klesající. Nabízí se nám tedy pohlížet na celý problém jako na způsob, jak uspořádat posloupnost N čísel a1, a2, …, aN tak, aby nebyla rostoucí ani klesající, tedy aby byla neseřazená.

Lehká verze

Pro lehkou verzi si můžeme rozmyslet to, že se nám stačí podívat jen na první 3 prvky z posloupnosti. Protože jsou všechny různé, tak je určitě můžeme uspořádat tak, aby tvořily zub – tedy aby např. a1 > a2, ale a2 < a3. Pak už zbývá jen N - 3 zbylých prvků, ale ty prostě jen vypíšeme tak, jak jsme je dostali. Jestliže máme méně než 3 prvky, vypíšeme -1 jako neúspěch a skončíme.

Těžká verze

Pro těžší verzi už to nepůjde tak jednoduše, protože nemáme zaručeno, že budou první tři prvky unikátní. Samozřejmě ale můžeme udělat to, že prostě najdeme nějaké tři unikátní prvky, přesuneme je na začátek a uděláme s nimi to samé jako v lehké verzi. O něco jednodušším řešením je ale posloupnost čísel nejprve seřadit nějakým vhodným řadícím algoritmem. Potom rozpoznáme případy, kdy máme méně než 3 prvky, nebo když jsou všechny prvky stejné. Jestli ano, vypíšeme -1 jako neúspěch a skončíme.

V opačném případě máme určitě alespoň dva různé prvky a dostatečně dlouhou posloupnost. Dále jen vhodně prohodíme prvky tak, abychom dostali zub. Máme-li alespoň tři různé prvky, třeba a1, a2 a aN, pak nám stačí prohodit a2 a aN, abychom dostali zub, protože je posloupnost seřazená a prvky jsou různé, platí a1 < a2 < aN. Máme-li jen dva různé prvky, třeba a1 je různé od a2 = … = aN, potom nám stačí prohodit a2 a a1, abychom dostali zub, protože platí, že a1 < a2 = aN.

Obě zmíněná řešení běží v lineárném čase a prostoru vzhledem k velikosti vstupu, tedy O(N) v případě, že použijeme vhodný řadící algoritmus jako např. radix sort. Řešení s pomalejšími řadícími algoritmy v čase O(N log N) bylo ale také akceptováno.

Ukázkový program (Python)

def vymen(pole, i, j):
    # Vymeni prvky v poli na indexech i a j
    tmp = pole[j]
    pole[j] = pole[i]
    pole[i] = tmp

def solve():
    N = int(input())
    A = [int(input()) for i in range(N)]

    # Seradime posloupnost
    A.sort()

    if N <= 2 or A[0] == A[N - 1]:
        # Posloupnost ma malo prvku nebo jsou vsechny stejne
        print("-1")
        return

    # Vime, ze se prvni a posledni prvky navzajem lisi,
    # hledame tedy jak vytvorit zub
    if A[1] == A[N - 1]:
        # Posloupnost vypada nasledovne:
        # 0111111111....11111
        #  ^

        # Tedy prehodime prvni prvek v posloupnosti, cimz dostaneme:
        # 1011111111....11111

        vymen(A, 1, 0)
    else: # A[1] != A[N - 1]
        # Mame tri odlisne prvky -- A[0], A[1] a A[N-1] 
        # a zaroven vime, ze A[0] < A[1] < A[N-1]
        # Prehodime tedy A[N-1] s A[1].

        vymen(A, 1, N-1)

    # Vypiseme posloupnost s mezerou mezi prvky
    print(" ".join(map(str, A)))

def main():
    T = int(input())
    for i in range(T):
        solve()

Ukázkový program (C++)

#include <algorithm>
#include <iostream>
#include <vector>

void solve() {
  int N;
  std::cin >> N;

  std::vector<int> A{};

  for (int i = 0; i < N; ++i) {
    int x;
    std::cin >> x;
    A.emplace_back(x);
  }

  std::sort(A.begin(), A.end());

  if (N <= 2 || A[0] == A[N - 1]) {
    std::cout << "-1" << std::endl;
    return;
  }

  if (A[1] == A[N - 1]) {
    std::swap(A[1], A[0]);
  } else {
    std::swap(A[1], A[N - 1]);
  }

  for (int i = 0; i < N; ++i) {
    auto &&x = A[i];
    if (i == N - 1) {
      std::cout << x << std::endl;
    } else {
      std::cout << x << ' ';
    }
  }
}

int main() {
  int T;
  std::cin >> T;

  for (int i = 0; i < T; ++i) {
    solve();
  }
}

Ukázkový program (Haskell)

module Main where

import           Control.Monad
import           Data.List
import           Data.Array.Unboxed

-- Vymeni dva prvky v poli
swap :: (IArray a e, Ix i) => i -> i -> a i e -> a i e
swap i j arr = arr // [(j, x_i), (i, x_j)]
 where
  x_i = arr ! i
  x_j = arr ! j

-- Vyresi jednu instanci problemu a mozna vrati pole s resenim
solve :: UArray Int Int -> Maybe (UArray Int Int)
solve arr
  | len <= 2 || first == last = Nothing
  | otherwise = Just $ swap second (if first == last then start else end) arr
 where
  (start, end ) = bounds arr
  (first, last) = (arr ! start, arr ! end)
  len           = rangeSize (start, end)
  second        = range (start, end) !! 1

-- Nacte vstup jako pole
loadInput :: IO (UArray Int Int)
loadInput = do
  n_line <- getLine
  let n = read n_line :: Int

  inputs <- replicateM n getLine
  let sorted = sort . map read $ inputs

  return . listArray (0, n - 1) $ sorted

main :: IO ()
main = do
  line <- getLine
  let t = read line :: Int

  replicateM_ t $ do
    arr <- loadInput
    case solve arr of
      Nothing       -> putStrLn "-1"
      Just solution -> putStrLn . unwords . fmap show . elems $ solution

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)