Porządek – Omówienie zadania z finału II etapu Olimpiady Informatycznej Gimnazjalistów

Porządek – Omówienie zadania z finału II etapu Olimpiady Informatycznej Gimnazjalistów

Szczegółowe omówienie zadania Porządek:

Link do powyższego omówienia zadania Porządek:
https://youtu.be/3E_EBxTygpo?t=2348
Początek omówienia rozwiązania optymalnego:
https://youtu.be/3E_EBxTygpo?t=3469

——-
Link do treści zadania Porządek:
—–
Zadanie Porządek to najtrudniejsze zadanie z II etapu VII Olimpiady Informatycznej Gimnazjalistów – poprzednika Olimpiady Informatycznej Juniorów.
Link do wszystkich zadań z Olimpiady Informatycznej Juniorów:
——
Zadanie Porządek wymaga wykorzystania sum prefiksowych.
Szczegółowe wytłumaczenie czym są sumy prefiksowe poprzez quiz:
https://youtu.be/3E_EBxTygpo?t=305
https://youtu.be/3E_EBxTygpo?t=664
https://youtu.be/3E_EBxTygpo?t=945
Wytłumaczenie programistyczne czym są sumy prefiksowe:
https://youtu.be/3E_EBxTygpo?t=1083
———-
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
——-

#include <bits/stdc++.h>
using namespace std;

const int MAX_DLUGOSC_OGRODU = 1e6+7;
long long int ile_par_do_tego_miejsca [MAX_DLUGOSC_OGRODU];
long long int ile_nasturcji_od_1 [MAX_DLUGOSC_OGRODU];
long long int ile_rudbekii_od_1 [MAX_DLUGOSC_OGRODU];

int main() {
 string kwiaty;
 int ile_kwiatow, ile_pytan;
 int odkad, dokad;
 int ile_rudbekii;
 int i;
 long long int odpowiedz, ile_par_pomiedzy;

 cin >> ile_kwiatow;
 cin >> kwiaty;
 
 kwiaty = " " + kwiaty;

 for (i=1; i<=ile_kwiatow; ++i) {
    ile_nasturcji_od_1[i] = ile_nasturcji_od_1[i-1];
    if ( kwiaty[i] == 'N' )
       ++ile_nasturcji_od_1[i];
 }

 for (i=1; i<=ile_kwiatow; ++i) {
    ile_rudbekii_od_1[i] = ile_rudbekii_od_1[i-1];
    if ( kwiaty[i] == 'R' )
       ++ile_rudbekii_od_1[i];
 }
 
 for (i=1; i<=ile_kwiatow; ++i) {
    ile_par_do_tego_miejsca[i] = ile_par_do_tego_miejsca[i-1];
    if ( kwiaty[i] == 'N' )
       ile_par_do_tego_miejsca[i] = ile_par_do_tego_miejsca[i] + ile_rudbekii_od_1[i];;
 }

 cin >> ile_pytan;
 for (i=1; i<=ile_pytan; ++i) {
 	cin >> odkad;
 	cin >> dokad;
 	
 	ile_par_pomiedzy = ile_rudbekii_od_1[odkad-1] * 
	                   (ile_nasturcji_od_1[dokad] - ile_nasturcji_od_1[odkad-1]);
 	odpowiedz = ile_par_do_tego_miejsca[dokad] - ile_par_do_tego_miejsca[odkad-1]
 	            - ile_par_pomiedzy;
 	cout << odpowiedz << "\n";
 }
 return 0;
}
Kod C++ programu Porządek, który jest omówiony w powyższym filmie i który otrzymuje 100% 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz