Omówienie zadania Usuwanie (I etap XXXII OI)

Rozwiązanie dla \(a,b\leq 10\)

W tym podzadaniu możemy rozważyć wszystkie możliwe scenariusze ruchów usuwania liczb z planszy. Aby to zrealizować, rozważymy wszystkie możliwe permutacje liczb \(a,a+1,\ldots,b\) i dla każdej z nich będziemy próbować usunąć pary sąsiednich elementów - pierwszy z drugim, trzeci z czwartym itd.

Aby to zrealizować, możemy użyć funkcji next_permutation z biblioteki standardowej C++. Funkcja ta zmienia kolejność elementów w zadanym kontenerze na następną w porządku leksykograficznym permutację. Dodatkowo wartość zwracana przez tę funkcję jest zmienną logiczną równą false, gdy przekazana jej permutacja jest ostatnią w kolejności leksykograficznej, oraz true w przeciwnym przypadku. Dzięki temu możemy łatwo iterować po wszystkich permutacjach za pomocą pętli do...while.

Całe rozwiązanie można więc wyrazić następującym programem w języku C++:

int main()  {
    int a, b;
    cin >> a >> b;

    vector<int> elementy;
    for (int i = a; i <= b; i++)
        elementy.push_back(i); // Dodajemy wszystkie liczby na planszy.

    int max_usunietych = 0;
    do {
        int usuniete = 0;
        for (int i = 0; i + 1 < (int)elementy.size(); i += 2) {
            if ((elementy[i] + elementy[i + 1]) % 2 == 0) // Sprawdzamy, czy suma jest parzysta.
                usuniete += 2;
        }

        max_usunietych = max(max_usunietych, usuniete);
    } while(next_permutation(elementy.begin(), elementy.end())); // Generujemy kolejną permutację, jeśli istnieje.

    cout << max_usunietych << "\n";
}

Takie rozwiązanie działa w złożoności \(O(n\cdot n!)\), przy czym \(n=b-a+1\) jest liczbą elementów na początkowej planszy, i pozwala zaliczyć pierwsze podzadanie.

 

Rozwiązanie dla \(a,b\leq 1\,000\,000\)

W drugim podzadaniu nie możemy już pozwolić sobie na przeglądanie wszystkich permutacji, ponieważ jest ich zdecydowanie zbyt wiele. Musimy więc dokonać pewnej obserwacji. Zauważmy, że jeśli suma pewnych dwóch liczb całkowitych jest parzysta, to albo obie liczby są parzyste, albo obie są nieparzyste. Wnioskujemy więc, że możemy rozważać liczby parzyste i nieparzyste osobno, ponieważ nie możemy usunąć pary składającej się z liczby parzystej i nieparzystej.

Niech \(x\) będzie liczbą liczb parzystych spośród liczb \(a,a+1,\ldots,b\), a \(y\) liczbą liczb nieparzystych spośród tych liczb. Zauważmy, że możemy wykonać co najwyżej \(\lfloor x/2 \rfloor\) ruchów usuwania par liczb parzystych, gdzie \(\lfloor t \rfloor\) oznacza największą liczbę całkowitą mniejszą lub równą \(t\). Analogicznie możemy wykonać co najwyżej \(\lfloor y/2 \rfloor\) ruchów usuwania par liczb nieparzystych. Wnioskujemy stąd, że możemy usunąć co najwyżej \(2\cdot\lfloor x/2 \rfloor\) liczb parzystych i \(2\cdot\lfloor y/2 \rfloor\) liczb nieparzystych, gdyż każda operacja usunięcia usuwa dokładnie dwie liczby.

Trudność w zadaniu polega teraz na wyznaczeniu wartości \(x\) i \(y\). Możemy to zrobić, iterując po liczbach od \(a\) do \(b\) i zliczając, ile jest liczb parzystych i nieparzystych. Takie rozwiązanie zaimplementowane w języku C++ wygląda następująco:

int main()  {
    int a, b;
    cin >> a >> b;

    int parzyste = 0, nieparzyste = 0;

    for (int i = a; i <= b; i++) {
        if (i % 2 == 0) // Sprawdzamy, czy liczba jest parzysta.
            parzyste++;
        else
            nieparzyste++;
    }

    cout << 2 * (parzyste / 2) + 2 * (nieparzyste / 2) << "\n";
}

Takie rozwiązanie działa w złożoności \(O(n)\), przy czym znów \(n=b-a+1\) oznacza liczbę elementów na początkowej planszy, i pozwala zaliczyć drugie podzadanie. Przypomnijmy, że w języku C++ dzielenie liczb całkowitych zwraca wynik zaokrąglony w kierunku 0 (czyli zaokrąglony w dół w przypadku liczb dodatnich), co pozwala nam na zastosowanie zapisu takiego jak wyżej.

Rozwiązanie dla \(a=1\)

W trzecim podzadaniu mamy dodatkowe ograniczenie, że \(a=1\). To pozwoli nam wyznaczyć wartości \(x\) i \(y\) znacznie szybciej niż w poprzednim podzadaniu. Rozważmy dwa przypadki w zależności od parzystości liczby \(b\):

1. Załóżmy, że \(b\) jest liczbą parzystą, czyli \(b=2k\) dla pewnej liczby całkowitej \(k\). Wówczas wszystkie liczby nieparzyste na planszy to \(1,3,\ldots,2k-1\), skąd widać, że jest ich dokładnie \(k\). Podobnie liczby parzyste to \(2,4,\ldots,2k\). Widzimy więc, że ich także jest dokładnie \(k\). Otrzymujemy więc wzory \[ x=k=\frac{b}{2} \qquad\text{oraz}\qquad y=k=\frac{b}{2}. \]
2. Załóżmy, że \(b\) jest liczbą nieparzystą, czyli \(b=2k+1\) dla pewnej liczby całkowitej \(k\). Wtedy liczby nieparzyste na planszy to \(1,3,\ldots,2k+1\), czyli jest ich dokładnie \(k+1\). Podobnie liczby parzyste to \(2,4,\ldots,2k\). Widzimy więc, że ich jest dokładnie \(k\). Tym razem otrzymujemy różne wzory \(x=k=(b-1)/2\) oraz \(y=k+1=(b+1)/2\).

Warto zauważyć, że w obu przypadkach prawdziwe są wzory \[ x=\left\lfloor\frac{b}{2}\right\rfloor \qquad\text{oraz}\qquad y=\left\lceil\frac{b}{2}\right\rceil, \] gdzie \(\lfloor t \rfloor\) oznacza największą liczbę całkowitą nie większą niż \(t\), a \(\lceil t \rceil\) oznacza najmniejszą liczbę całkowitą nie mniejszą niż \(t\). Możemy to łatwo uzasadnić. W przypadku 1. liczba \(b/2\) jest całkowita, a więc operacje \(\lfloor\cdot\rfloor\) i \(\lceil\cdot\rceil\) nie mają żadnego efektu. W przypadku 2. liczba \((b-1)/2\) jest największą liczbą całkowitą nie większą od \(b/2\), a \((b+1)/2\) to najmniejsza liczba całkowita nie mniejsza od \(b/2\).

 

Całe rozwiązanie możemy więc zapisać w języku C++ w następujący sposób:

int main()  {
    long long a, b;
    cin >> a >> b;

    long long parzyste = b / 2;
    long long nieparzyste = (b + 1) / 2;

    cout << 2 * (parzyste / 2) + 2 * (nieparzyste / 2) << "\n";
}

Zwróćmy uwagę na dwa istotne szczegóły dotyczące implementacji. Po pierwsze skorzystaliśmy z typu long long zamiast int, ponieważ wartość liczby \(b\) w tym podzadaniu może wychodzić poza zakres typu 32-bitowego ze znakiem (zakres ten jest ograniczony przez \(2^{31}-1\), czyli w przybliżeniu \(2\cdot 10^9\)). Po drugie, zwróćmy uwagę na to, że w przypadku 2. zastosowaliśmy zapis (b + 1) / 2 aby zaokrąglić w górę wynik dzielenia \(b/2\). Zainteresowany Czytelnik zechce sprawdzić, że w przypadku, gdy \(b\) jest liczbą nieujemną, takie wyrażenie zwraca dokładnie \(\lceil b/2 \rceil\) dzięki zastosowaniu reguł dzielenia liczb całkowitych w języku C++.

Czas działania tego rozwiązania nie jest zależny od wartości liczby \(b\), a więc otrzymujemy złożoność czasową \(O(1)\), co pozwala zaliczyć trzecie podzadanie.

Pełne rozwiązanie

Aby otrzymać pełne rozwiązanie, należy ułożyć ogólniejsze wzory na wartości \(x\) i \(y\). W tym celu możemy skorzystać z następującej obserwacji: liczba liczb parzystych pośród \(a,a+1,\dots,b\) jest równa różnicy liczby liczb parzystych pośród \(1,2,\dots,b\) oraz \(1,2,\dots,a-1\) i tak samo dla liczb nieparzystych. Możemy więc wykorzystać wzory z rozwiązania zakładającego, że \(a=1\), opisanego powyżej, aby wyprowadzić pożądane ogólniejsze wzory. Liczba liczb parzystych pośród \(1,2,\dots,b\) jest równa \(\left\lfloor \frac{b}{2}\right\rfloor\) i tak samo liczba liczb parzystych pośród \(1,2,\dots,a-1\) jest równa \(\left\lfloor\frac{a-1}{2}\right\rfloor\) (zwróćmy uwagę, że wzór ten działa także dla przypadku szczególnego \(a=1\)). Mamy więc \[ x=\left\lfloor \frac{b}{2}\right\rfloor - \left\lfloor\frac{a-1}{2}\right\rfloor \] i dla liczb nieparzystych mamy \[ y=\left\lceil \frac{b}{2}\right\rceil - \left\lceil\frac{a-1}{2}\right\rceil. \]

Całe rozwiązanie możemy więc zapisać w języku C++ w następujący sposób:

int main() {
    long long a, b;
    cin >> a >> b;

    long long parzyste = b / 2 - (a - 1) / 2; // Zaokrąglamy w dół b / 2 oraz (a - 1) / 2.
    long long nieparzyste = (b + 1) / 2 - (a - 1 + 1) / 2; // Zaokrąglamy w górę b / 2 oraz (a - 1) / 2.

    cout << 2 * (parzyste / 2) + 2 * (nieparzyste / 2) << "\n";
}

Widzimy, że czas działania tego rozwiązania nie zależy od wartości liczb \(a\) i \(b\). Otrzymujemy więc złożoność czasową \(O(1)\), co pozwala zaliczyć wszystkie podzadania.