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

Problem z zadaniem C++

VPS Starter Arubacloud
0 głosów
663 wizyt
pytanie zadane 10 kwietnia 2021 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 2021 przez Whistleroosh Maniak (56,900 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 2021 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
1 odpowiedź 120 wizyt
pytanie zadane 28 kwietnia 2022 w C i C++ przez polandonion Mądrala (6,970 p.)
0 głosów
2 odpowiedzi 739 wizyt
0 głosów
0 odpowiedzi 67 wizyt
pytanie zadane 21 stycznia w Algorytmy przez Szyszka Gaduła (3,490 p.)

92,452 zapytań

141,262 odpowiedzi

319,077 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...