1 - Nesusedni

ZadatakRešenje

Vremensko ograničenje	Memorijsko ograničenje
200ms	256MB

Programer Pera ima omiljeno slovo $c_{1}$ (jedno od malih slova engleskog alfabeta) i poseduje $a_{1}$ komada ovog slova. Programerka Petra takođe ima svoje omiljeno slovo $c_{2}$ (jedno od malih slova enegleskog alfabeta, različito od Petrovog) i $a_{2}$ komada svog slova.

Pera i Petra su rešili da naprave string u kome će se naći svih $a_{1} + a_{2}$ njihovih slova ali takav da u njemu ne postoje dva ista susedna slova. Odredite bilo koji string koji zadovoljava ove uslove ili konstatujte da takav string ne postoji.

Opis ulaza

U prvom redu standardnog ulaza se nalaze Perino i Petrino slovo $c_{1}$ i $c_{2}$ , redom, bez razmaka. U narednom redu se nalaze dva prirodna broja $a_{1}$ i $a_{2}$ , razdvojena razmakom, koja predstavljaju broj komada slova koje poseduju Pera i Petra, redom.

Opis izlaza

U prvom redu ispisati string koji zadovoljava sve uslove iz zadatka. Ukoliko ima više rešenja, ispisati bilo koje. Ukoliko rešenje ne postoji, ispisati 'nemoguce' (bez navodnika).

Primer 1

Ulaz

ab
2 2

Izlaz

baba

Primer 2

Ulaz

nm
4 10

Izlaz

nemoguce

Objašnjenja primera

U prvom primeru su iskorišćena 2 slova 'a' i 2 slova 'b' i ne postoje dva ista susedna slova - dakle, string je validan. String 'abab' je takođe validno rešenje za ovaj primer. U drugom primeru, ma kako rasporedili 4 slova 'n' i 10 slova 'm', uvek će postojati dva susedna ista slova pa traženi string ne postoji.

Ograničenja

$c_{1}$ i $c_{2}$ su međusobno različita mala slova engleskog alfabeta
$1 \leq a_{1}, a_{2} \leq 50.000$

Test primeri su podeljeni u 3 disjunkne grupe:

U test primerima vrednim $20$ poena važi $c_{1} =$ ' $a$ ', $c_{2} =$ ' $b$ ' i $1 \leq a_{1}, a_{2} \leq 3$ .
U test primerima vrednim $40$ poena važi $1 \leq a_{1}, a_{2} \leq 1.000$
U test primerima vrednim $40$ poena nema dodatnih ograničenja.

Autor	Tekst i test primeri	Analiza rеšenja	Testiranje
Nikola Milosavljević	Nikola Milosavljević	Nikola Milosavljević	Vladimir Milovanović

Kako imamo tačno 2 različita slova, jedini način da string ne sadrži dva ista susedna slova je da se slova pojavljuju naizmenično u stringu tj. $c_{1} c_{2} c_{1} c_{2} \dots$ ili $c_{2} c_{1} c_{2} c_{1} \dots$ . Ovo je moguće ako i samo ako je $| a_{1} - a_{2} | \leq 1$ . Zaista, ako je $| a_{1} - a_{2} | > 1$ , "istrošićemo" jedno slovo u naizmeničnom pojavljivanju pre kraja stringa. Sa druge strane, ako je $a_{1} = a_{2}$ , imamo 2 moguća rešenja (bilo koje slovo može biti prvo), a ako je $| a_{1} - a_{2} | = 1$ , rešenje je jedinstveno jer moramo početi (i završiti) slovom koje se pojavljuje više puta.

Složenost algoritma je $O (a_{1} + a_{2})$ , zbog ispisa.

01_nesusedni.cpp
#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); // uvek dodati ovu liniju ako se radi sa cin/cout umesto sa scanf/printf (iako nije neophodna za ovaj zadatak)

    char c1, c2;
    int a1, a2;

    cin >> c1 >> c2;
    cin >> a1 >> a2;

    if (abs(a1 - a2) > 1)
    {
        cout << "nemoguce" << "\n";
        return 0;
    }

    if (a1 < a2)
    {
        char tmp = c1;
        c1 = c2;
        c2 = tmp;
    }

    for (int i = 0; i < a1 + a2; i++)
    {
        if (i % 2 == 0)
            cout << c1;
        else
            cout << c2;
    }

    cout << "\n";
    return 0;
}