Szczegółowe omówienie zadania Monety:
Link do powyższego omówienia zadania Monety: https://youtu.be/dpedTv7MvAI?t=1765
Link do treści zadania Monety: https://szkopul.edu.pl/problemset/problem/xss1BbTCqSIb-udUi6NnHb4P/site
Zadanie Monety wykorzystuje sumy prefiksowe: https://youtu.be/7Ap0B_C4T24?t=3553
Gdzie wykorzystuje się sumy prefiksowe? https://youtu.be/jsaVtx5WQv0?t=245
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
Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia Olimpiada Informatyczna POZIOM II: https://oki.org.pl/olimpiada-informatyczna-poziom-ii/
Wszystkie zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php
–
Kod C++ programu "Monety", który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;
int arr[MAXN];
map<long long, int> prev_sums;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
char c;
cin >> c;
if (c == 'O')
arr[i] = 1;
else
arr[i] = -k;
}
prev_sums[0] = 0;
int ans = 0;
long long curr_sum = 0;
for (int i = 1; i <= n; ++i) {
curr_sum += arr[i];
if (prev_sums.find(curr_sum) != prev_sums.end()) {
int prev_ind = prev_sums[curr_sum];
ans = max(ans, i-prev_ind);
} else {
prev_sums[curr_sum] = i;
}
}
cout << ans << '\n';
return 0;
}
Kod C++ programu "Monety", który jest omówiony w powyższym filmie i który otrzymuje 100%