Szczegółowe omówienie zadania Swapity Swapity Swap:
Link do powyższego omówienie zadania Swapity Swapity Swap:
https://youtu.be/nvA92I5nU0c?t=1480
Omówienie kodu zadania Swapity Swapity Swap: https://youtu.be/nvA92I5nU0c?t=4400
Link do treści zadania: http://www.usaco.org/index.php?page=viewproblem2&cpid=1014
Zadanie wymaga jedynie pomysłu – rozpatrzenia cykli.
Zadanie Swapity Swapity Swap pochodzi z dywizji Silver Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów: https://youtu.be/KI7un-HU_Hk?t=49
Daje piękny wpis do CV:
https://youtu.be/P2sLFZBjOmM?t=7223
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO?
https://youtu.be/K7fZfJ8nN6A?t=6848
Co to jest USACO? https://youtu.be/nvA92I5nU0c?t=1414
–
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/
Bezpłatne zajęcia OKI: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php
Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109
–
Kod C++ programu Swapity Swapity Swap, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100*1000+10;
int krowy[MAXN];
bool sprawdzone[MAXN];
int wynik[MAXN];
int n, m, k;
void obroc(int l, int r)
{
int dlugosc = (r - l + 1);
for (int i = 0; i < dlugosc / 2; ++i) {
swap(krowy[l + i], krowy[r - i]);
}
}
int main()
{
ifstream in("swap.in");
ofstream out("swap.out");
in >> n >> m >> k;
for (int i = 1; i <= n; ++i)
krowy[i] = i;
for (int i = 0; i < m; ++i) {
int l, r;
in >> l >> r;
obroc(l, r);
}
vector<int> cykl;
for (int i = 1; i <= n; ++i) {
if (sprawdzone[i] == false) {
int aktIndeks = i;
while (sprawdzone[aktIndeks] == false) {
cykl.push_back(aktIndeks);
sprawdzone[aktIndeks] = true;
aktIndeks = krowy[aktIndeks];
}
int dlugoscCyklu = cykl.size();
for (int j = 0; j < dlugoscCyklu; ++j) {
int miejsceKrowy = cykl[j];
int przesuniecie = k % dlugoscCyklu;
int krowa = cykl[(j + przesuniecie) % dlugoscCyklu];
wynik[miejsceKrowy] = krowa;
}
cykl.clear();
}
}
for (int i = 1; i <= n; ++i) {
out << wynik[i] << '\n';
}
return 0;
}
Kod C++ programu Swapity Swapity Swap, który jest omówiony w powyższym filmie i który otrzymuje 100%