https://youtu.be/V6axb24D1dw?t=3138
https://szkopul.edu.pl/problemset/problem/SqnOvjVqKup1DdvOx0yBuE_m/site
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;
}