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