Omówienie zadania Wieża (Ilocamp)

Szczegółowe omówienie zadania Wieża:

Link do powyższego omówienia zadania Wieża:
https://youtu.be/V6axb24D1dw?t=3138

Zadanie Wieża jest zadaniem na poziomie I etapu OI lub II etapu OIJ.
W omówieniu do rozwiązania zadania Zosia wykorzystała algorytm Binary Search.
Oczywiście są również inne rozwiązania tego zadania.

Zadanie Wieża pochodzi z obozu Ilocamp organizowanego przez ośrodek informatyczny w Białymstoku:
https://youtu.be/V6axb24D1dw?t=3142
Link do wszystkich zadań z tego obozu:
https://szkopul.edu.pl/p/default/problemset/ilocamp/2010

Zadanie omawia Zosia – uczestniczka Olimpijskiego Koła Informatycznego, uczennica VI klasy Szkoły Podstawowej o rozległych zainteresowaniach:
https://youtu.be/V6axb24D1dw?t=3996
Bardzo dziękuję!

——–
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 Wieża, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;
const int MAXI = 5e5 + 7;
int schody[MAXI];
int binarysearchpowyniku(int pocz, int kon, int co){
int sro;
while(pocz < kon){
sro = (pocz + kon + 1) / 2;
if(schody[sro] <= co){
pocz = sro;
}
else{
kon = sro - 1;
}
}
return pocz;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, maxi = 0, osoba, wyn;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> schody[i];
if(schody[i] > maxi){
maxi = schody[i];
}
schody[i] = maxi + 1;
}
for(int i = 1; i <= m; i++){
cin >> osoba;
if(osoba < schody[1]){
cout << 0 << ' ';
continue;
}
if(osoba >= schody[n]){
cout << n << ' ';
continue;
}
wyn = binarysearchpowyniku(1, n, osoba);
cout << wyn << ' ';
}
cout << '\n';
return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Wieża 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz