Zadanie Poddrzewo potyczki algorytmiczne

Question

Mam problem z takim zdaniem: https://szkopul.edu.pl/problemset/problem/w9_OeHLYqjDZ3e_0QBG8Fj1U/site/?key=statement

Podejrzewam, że wejdzie tu jakiś zachłan, ale nie wiem jak do tego podejść. Nie znalazłem nigdzie w internecie rozwiązania.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

I to jaki ładny zachłan wejdzie!

Jak na div A to zadanie jest całkiem proste. Co musi posiadać każde drzewo?

Comments

To nie kończy zadania?

---

Tak, to jest wzorcówka

---

Pozwolę sobie przez chwilę poużałać się nad sobą.

Po pierwsze to wyobraziłem sobie twoją minę i reakcję, gdy zobaczyłeś to pytanie i pisałeś: "I to jaki ładny zachłan wejdzie!" albo, gdy zapytałem: "Ale żeby jakoś od liści symulować powstawanie drzewa?", odpisałeś: "Może...". Ja bym się popłakał ze śmiechu. Jestem dumny z siebie, że zagwarantowałem Ci rozbawienie.

A tu kodzik mający 35 linii.

#include <iostream>

using namespace std;

int n = 0, wczytana_liczba = 0, idx_1 = -1, idx_2 = -1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        if (wczytana_liczba == 1)
        {
            if (idx_1 == -1)
                idx_1 = i + 1;
            else
                idx_2 = i + 1;
        }
    }

    if (idx_1 == -1)
        cout << "2" << '\n' << "2" << '\n' << "1 2" << '\n';
    else if (idx_2 == -1)
        cout << "1" << '\n' << "2" << '\n' << "1 2" << '\n';
    else
        cout << "0" << '\n' << "2" << '\n' << "1" << ' ' << "2" << '\n';

    return 0;
}

Dzięki!

---

Żebyś wiedział ile razy ja zapewne ubawiłem swojego mentora w taki własnie sposób :) No ale cóż, tak się własnie człowiek uczy. To takie zadanie typowe na CF div. B. Możesz próbować brać udział w contestach na CF i nauczysz się szybko wpadać na takie pomysły.

btw na sio2 są solvy do zadań z PA

---

Chyba zaczną brac udział w codeforces-ach. Nie wiem, jakieś zaćmienie mózgu miałem dzisiaj.... To jest prawda, takie przykłady uświadamiają, jak jeszcze daleka droga przedemną....

A propo solvów z PA, to faktycznie są, na przyszłość może to być dobry pomysł.....