Bankiet – Omówienie zadania, II etap Olimpiady Informatycznej Juniorów

Bankiet – Omówienie zadania, II etap Olimpiady Informatycznej Juniorów

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;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz