• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z zadaniem C++

0 głosów
91 wizyt
pytanie zadane 10 kwietnia w Algorytmy przez jpor3 Nowicjusz (170 p.)

Cześć!

Rozwiązywałem właśnie zadanie Zapałki (https://szkopul.edu.pl/problemset/problem/ZLG7FB_afACLMh8-zsupw5zV/site/?key=statement) z V OIG. Rozwiązałem zadanie poprzez obserwację, że trzeba znaleźć takie miejsce, w którym zapałki zwrócone są do siebie główkami, a następnie policzyć ile zapałek jest źle odwróconych (obliczenie przez sumy prefiksowe, żeby było szybciej). Jeżeli brak jest takiego miejsca to zakładam, że takie miejsce jest na pozycji 0 lub ile_jest_zapałek-1 (tablice od 0) w zależności od tego, które jest mniejsze. Dostaję 82 punkty i w dwóch testach wychodzi błąd:

  • 2b wiersz 1: wczytano '19', a oczekiwano '18'
  • 9 wiersz 1: wczytano '488601', a oczekiwano '487340'

Udało mi się znaleźć w internecie oficjalne opracowanie i pseudokod i wydaje mi się, że jest zgodny z tym co wymyśliłem. Spędziłem nad tym trochę czasu, ale zupełnie nie rozumiem dlaczego tak się dzieje. Link do zadania i opracowania w pdfie: http://docplayer.pl/docview/25/5384524/#file=/storage/25/5384524/5384524.pdf, str. 14-16.

#include <iostream>
#include <algorithm>

using namespace std;

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

    int ile_zapalek, zapalki[1000100] = {}, w_prawo[1000100] = {}, w_lewo[1000100] = {}, minl = 2000000;

    cin >> ile_zapalek;

    for(int i=0; i<ile_zapalek; i++) //wczytuje i obliczam ile jest zle odwroconych od 0
    {
        cin >> zapalki[i];
        if(i==0) 
            w_prawo[i] = 1 - zapalki[i];
        else
            w_prawo[i] = w_prawo[i-1] + 1 - zapalki[i];
    }

    for(int i=ile_zapalek-1; i>=0; i--) //obliczam ile jest zle odwroconych od ile_zapalek-1 (tablice od 0)
    {
        if(i==ile_zapalek-1) 
            w_lewo[i] = zapalki[i];
        else
            w_lewo[i] = w_lewo[i+1] + zapalki[i];
    }

    for(int i=ile_zapalek-2; i>=0; i--) //szukam najlepszego miejsca
    {
        if(zapalki[i]==1 && zapalki[i+1]==0)
            minl = min(minl, w_prawo[i] + w_lewo[i+1]);
    }

    if(minl==2000000) //jezeli poprzednia petla nie zwroci nic mniejszego to minl sie nie zmienilo
    //jesli nie ma takiego miejsca to sprawdzam czy mniejsze jest przyjecie ze punkt jest w 0 (w_lewo jest 1, bo w_lewo sprawdzam jako i+1, a prawo jako i) czy w ile_zapalek-1
    {
        minl = w_prawo[ile_zapalek-1];
        if(minl>w_lewo[1]) minl = w_lewo[1];
    }

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

Może osoba, która ma większą wiedzę ode mnie zechciałaby mi pomóc?

1 odpowiedź

0 głosów
odpowiedź 10 kwietnia przez Whistleroosh Nałogowiec (29,580 p.)
Usuń tego ifa z 38. linii. Może być tak, że minl będzię różne od 2000000, ale w_prawo[ile_zapalek-1] lub w_lewo[0] będzie mimo to mniejsze od minl. Dodatkowo tam chyba powinno być w_lewo[0]
komentarz 10 kwietnia przez jpor3 Nowicjusz (170 p.)
Dzięki wielkie. W końcówce musi być w_lewo[1], bo na początku może być zarówno 10 jak i 00, a ogień i tak przejdzie.

Podobne pytania

0 głosów
2 odpowiedzi 425 wizyt
0 głosów
2 odpowiedzi 154 wizyt
pytanie zadane 10 listopada 2016 w Algorytmy przez BlueWee Użytkownik (730 p.)
+1 głos
1 odpowiedź 47 wizyt
pytanie zadane 13 września w Algorytmy przez barekwa Nowicjusz (130 p.)
Porady nie od parady
Odznacz odpowiedź zieloną fajką, jeśli uważasz, że jest ona najlepsza ze wszystkich i umożliwiła ci rozwiązanie problemu.Najlepsza odpowiedź

85,170 zapytań

133,979 odpowiedzi

297,038 komentarzy

56,286 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...