Omówienie zadania Naklejki – Finał OIG

Omówienie zadania Naklejki – Finał OIG

Szczegółowe omówienie zadania Naklejki:

Link do powyższego omówienia zadania Naklejki:
https://youtu.be/OC_xrHSMYlA?t=6468

——
Zadanie Naklejki wymaga pomysłu – nie potrzeba żadnej zaawansowanej algorytmiki.
Realizuje strategię na później – najpierw zaznaczamy co mamy zrobić dla każdej ze 100 000 operacji – a następnie przechodząc raz po zadanym napisie wykonujemy od razu wszystkie operacje.

Zadanie Naklejki pochodzi z finału Olimpiady Informatycznej Gimnazjalistów, poprzednika Olimpiady Informatycznej Juniorów.

——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019

Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625

——-
Kod C++ programu Naklejki, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 +10;
int numer_operacji[MAXN];
int przesuniecie[MAXN];
string slowo;

int main() {
 int liczba_naklejek, liczba_zamian;
 int poczatek, koniec;
 int delta, ktora_operacja;
 int i;

 cin >> liczba_naklejek >> liczba_zamian;
 cin >> slowo;

 for (i=1; i<=liczba_zamian; ++i) {
    cin >> poczatek >> koniec;
    --poczatek;
    --koniec;
    numer_operacji[koniec] = i;
    przesuniecie[koniec] = koniec - poczatek;
 }

 delta = 0;
 ktora_operacja = 0;
 for (i=0; i<liczba_naklejek; ++i) {
    if (ktora_operacja < numer_operacji[i]) {
       delta = przesuniecie[i];
       ktora_operacja = numer_operacji[i];
    }
	slowo[i] = slowo[i-delta];
 }

 cout << slowo;

 return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Naklejki 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz