Zadanie FlappyBird XXIV OI

Question

Cześć,

Robię zadanie FlappyBird z XXIV OI. https://szkopul.edu.pl/problemset/problem/eLy9p2a1VStZ4y9y-LdeB-8f/site/?key=statement

Pomysł:

Znajdujemy najniższy punkt, do którego możemy dolecieć i potem wzorem w O(1) wyliczam ile musze użyc operacji. Znajduję go mając dwie zmienne góra i dół i zauważam, że Bajtazar może dojśc na pola w zasięgu po skosie i pomiędzy nimi w tej samej parzystości co skosy góra i dół. Kod teorytycznie wyszedł bardzo prosty, ale już z 3 godzinę siedzę nad nim i nie widzę błędu. Na około 50 testów nie przechodzą 3 - 71pkt. I dają odpowiedź o jedną za mało.

Kod:

#include <iostream>
#include <vector>

using namespace std;

struct Przeszkoda
{
    long long x;
    long long gora;
    long long dol;
};

long long n = 0, x = 0, x_i = 0, a_i = 0, b_i = 0, gora = 0, dol = 0, wspolrzedne_x = 0, wyn = 0;
vector<Przeszkoda> przeszkody;

bool czy_mozna_przejsc_przeszkody ()
{
    for (int i = 0; i < n; ++i)
    {
        gora += (przeszkody[i].x - wspolrzedne_x);
        dol -= (przeszkody[i].x - wspolrzedne_x);
        wspolrzedne_x = przeszkody[i].x;

        if (przeszkody[i].gora <= dol)
        {
            return false;
        }
        if (przeszkody[i].dol >= gora)
        {
            return false;
        }

        // Teraz normalizujemy
        if (dol <= przeszkody[i].dol)
        {
            if (dol % 2 == przeszkody[i].dol % 2)
            {
                dol = przeszkody[i].dol + 2;
            }
            else
            {
                dol = przeszkody[i].dol + 1;
            }
        }
        if (gora >= przeszkody[i].gora)
        {
            if (gora % 2 == przeszkody[i].gora % 2)
            {
                gora = przeszkody[i].gora - 2;
            }
            else
            {
                gora = przeszkody[i].gora - 1;
            }
        }
        if (dol >= przeszkody[i].gora || gora <= przeszkody[i].dol)
        {
            return false;
        }
    }
    return true;
}

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

    cin >> n >> x;

    if (n == 0)
    {
        cout << "0" << "\n";
        return 0;
    }

    for (int i = 0; i < n; ++i)
    {
        cin >> x_i >> a_i >> b_i;
        przeszkody.push_back({x_i,b_i,a_i});
    }

    if (czy_mozna_przejsc_przeszkody() == true)
    {
        long long ile_r;
        long long ile_skok;
        if (dol >= 0)
        {
            ile_r = przeszkody[n-1].x;
            ile_skok = dol;
            wyn = (ile_r - ile_skok) / 2 + ile_skok;
        }
        else
        {
            ile_r = przeszkody[n-1].x - (abs(dol));
            wyn = ile_r / 2;
        }
        cout << wyn << "\n";
    }
    else
    {
        cout << "NIE" << "\n";
    }

    return 0;
}

Widzi ktoś błąd?

Wizualizacja pomysłu: 

Tak jak jest w omówieniu na kanale OI

Z góry bardzo dziękuję za pomoc.

Answer 1

Sprawdziłem w swoim starym rozwiązaniu do tego zadania i u mnie wzór na ilość stuknięć to było:

(przeszkody[n-1].x+dol)/2

Ale nawet pod podmianie Twój kod dostaje 71pkt, czyli zmienna dol jest źle liczona

Comments

Ok dzięki, czyli bład jest w funkcji czy_mozna_przejsc_przeszkody.

---

Całkiem dużo ifów jest w tej funkcji i przez to trudno wyłapać błąd. Dlatego zawsze lepiej unikać takiego rozbijania problemu na tyle przypadków. Ja miałem to zrobione tak, że liczyłem po prostu przecięcie przedziałów (dol, gora), (przeszkody[i].dol+1, przeszkody[i].gora-1) i wtedy problem jest tylko gdy przedział powstały po przecięciu jest jednoelementowy. Wtedy trzeba skorzystać z tej "normalizacji"

---

Okazało się, że cały kod był dobry, tylko c++ mnie oszukiwał i pisał np, że -7 % 2 == -1, a nie -7 % 2 == 1, więc musiałem wziąść moduły i przeszło na 100pkt. Teraz mam nadzieję, że zapamiętam jak działa modulo w c++ dla ujemnych, bo kosztowało mnie to ponad 5 godzin :).

Ale masz rację, że niepotrzebnie tymi ifami tak zamąciłem.

Rozwiązanie już działające jakby ktoś się kiedyś męczył:

https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/flappy_bird.cpp

---

to bardzo dziwne bo w matematyce operacja modulo zawsze zwraca wartość dodatnią
https://www.mathcentre.ac.uk/resources/Engineering%20maths%20first%20aid%20kit/latexsource%20and%20diagrams/1_5.pdf

natomiast faktycznie operacja ta w C++ zwraca ujemną wartość dla negative numbers.
https://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo