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?