Szczegółowe omówienie zadania Bankiet:
Link do powyższego omówienia zadania Bankiet:
https://youtu.be/VFJF24BRTyo?t=1365
Omówienie kodu zadania Bankiet:
https://youtu.be/VFJF24BRTyo?t=2605
Link do treści zadania Bankiet oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/NQamRQ2UZEwn6gPqo-l6nat9/site
–
Zadanie Bankiet wymaga jedynie pomysłu.
To fantastyczne zadanie wprowadzające nas w świat rozwiązywania problemów przy pomocy komputera, olimpiady informatycznej, algorytmiki.
Na przykładzie tego zadania Tomek pokazuje jak ważny jest czas wykonywania programu, czyli złożoność naszego rozwiązania:
https://youtu.be/VFJF24BRTyo?t=3809
Omówienie wolniejszego rozwiązania:
https://youtu.be/VFJF24BRTyo?t=3320
Zadanie Bankiet pochodzi z II etapu Olimpiady Informatycznej Gimnazjalistów, poprzednika Olimpiady Informatycznej Juniorów.
By znaleźć się w finale wystarczyło zrobić to zadanie i fragment i fragment innego zadania.
Lista wszystkich zadań OIJ/OIG: https://szkopul.edu.pl/task_archive/oig/
Zadanie omawia oraz zajęcia prowadzi Tomek Kwiatkowski:
https://www.facebook.com/2247317372200511/posts/2958010761131165
–
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++ który rozwiązuje zadanie Bankiet i otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100*1000+10;
// naLewo[i] = kogo chce miec osoba i po lewej stronie
int naLewo[MAXN];
bool sprawdzony[MAXN];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> naLewo[i];
}
int liczbaStolow = 0;
for (int i = 1; i <= n; ++i) {
// jezeli nie sprawdzilismy jeszcze osoby o indeksie i
if (sprawdzony[i] == false) {
int aktIndeks = i;
// chodzimy po sasiadach “naLewo”, dopoki nie zrobimy cyklu
while (sprawdzony[aktIndeks] == false) {
sprawdzony[aktIndeks] = true;
// przechodzimy na indeks sasiada
aktIndeks = naLewo[aktIndeks];
}
// mamy o jeden stol wiecej
++liczbaStolow;
}
}
cout << liczbaStolow << ‘\n’;
return 0;
}