Omówienie zadania “Basen”

Omówienie zadania “Basen”

Szczegółowe omówienie zadania Basen z I etapu tury otwartej XIV Olimpiady Informatycznej Juniorów:
Link do powyższego omówienia zadania Basen:
https://youtu.be/x8-GgzTgCH8
Zadanie Basen wymaga jedynie pomysłu, nie są potrzebne zaawansowane algorytmy
Link do wszystkich zadań z Olimpiady Informatycznej Juniorów:
https://szkopul.edu.pl/task_archive/oig/
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
——-
Kod C++ zadania Basen, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;

int main ( ) {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int liczba_pomiarow;
 bool rosnacy;
 int poprzedni_pomiar, aktualny_pomiar;
 int wynik;
 int i;

 cin >> liczba_pomiarow;

 wynik = 1;
 rosnacy = true;

 cin >> poprzedni_pomiar;
 for (i =2; i<=liczba_pomiarow; ++i) { cin >> aktualny_pomiar;
    if ( (rosnacy == true) && (poprzedni_pomiar>aktualny_pomiar) ) {
       ++wynik;
       rosnacy = false;
    }    
    if ( (rosnacy==false) && (poprzedni_pomiar < aktualny_pomiar) ) {
       ++wynik;
       rosnacy = true;
    }
    poprzedni_pomiar = aktualny_pomiar;
 }

 cout << wynik << "\n" ;
 
 return 0;
}
Kod C++ zadania Basen, który jest omówiony w powyższym filmie i który otrzymuje 100% 

—–
Poniżej powyższy kod wzorcowy wraz z komentarzami

//Na początku dołączamy niezbedne biblioteki C++ 
#include <bits/stdc++.h>
//oraz informujemy C++, że będziemy korzystać ze standardowej przestrzeni nazw.
using namespace std;
//Te 2 linijki umieszczamy zawsze we wszystkich programach Olimpiady Informatycznej

//Funkcja main to ta część naszego kodu C++ która będzie uruchamiona przez system operaycjny jak na przykład Windows czy Linux
int main ( ) {
//Te 3 linijki przyspieszaja wczytywanie i wypisywanie duzej liczby danych w C++
//Pamiętajmy, że musimy wczytac nawet milion pomiarów zegarka Bajtka
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
//Te 3 linjki również umieszczamy zawsze, w każdym zadaniu Olimpiady Infor,atycznej

//Przechodzimy do sekcji w której definiujemy zmienne wykorzystywane przez nasz program
//zmienna liczba_pomiarow przechowuje informacje ile pomiarów zarjestrował zegarek Bajtka
 int liczba_pomiarow;
//zmienna rosnacy mowi nam czy Bajtek plynie aktualnie OD startowego brzegu - wowczas ciag pomiarow jest rosnący i zmienna ma warosc 1
//czy tez Bajtek plynie w stronę startowego brzegu i zmienna rosnacy ma wartosc 0 co oznacza, ze nasz ciag jest aktualnie malejący
 bool rosnacy;
//W trakcie analizy pomiarów zegarka musimy wiedzieć czy ciąg nadal ma ten sam charakter - na przykład czy nadal pozostaje rosnący. 
//Dlatego będziemy pamiętać 2 ostatnie wartości pomiarów smartwatcha w zmiennych poprzedni_pomiar oraz aktualny_pomiar
 int poprzedni_pomiar, aktualny_pomiar;
//Zmienna wynik pamieta ile minimalnie basenow Bajtek musial przepłynac na podstawie dotychczas zaanlizowanych danych 	
 int wynik;
//Wprowadzamy tez zmienną pomocniczą i która pozwoli nam przechodzić w pętli po wszystkich pomiarach Bajtka
 int i;

//Najpierw nasz program wczytuje liczbę wszystkich pomiarów smartwatcha Bajtka
 cin >> liczba_pomiarow;

//Następnie ustawiamy początkowe wartości zmiennych
//Kiedy Bajtek wszedł do wody to na pewno przepłynie przynajmniej jedna dlugosc basenu
 wynik = 1;
//oraz zacznie płynąć OD startowego brzegu - zatem nasz ciąg będzie najpierw rosnacy
 rosnacy = true;

//wczytujemy pierwsza wartosc z zegarka Bartka - inicjujemy zmienna poprzednia_wartosc
 cin >> poprzedni_pomiar;
//W petli znalizujemy wszystkie pomiary zegarka poczawszy od drugiego (pierwszy pomiar juz wczytalismy)
//Zliczymy MINIMALNA liczbe długosci basenow Bajtka, jako liczbę koniecznych nawrotow czyli zmian ciagu z rosnacego na malejacy
 for (i =2; i<=liczba_pomiarow; ++i) { //Podczas każdego przebiegu pętli najpierw wczytujemy aktualny pomiar zegarka Bajtka cin >> aktualny_pomiar;
//Jezeli do tej pory oddalalismy sie od startowego brzegu (ciąg był rosnący), a aktualny pomiar jest mniejszy od poprzedniego 
//to znaczy ze mamy zmiane ciagu z rosnacego na malejacy:
    if ( (rosnacy == true) && (poprzedni_pomiar>aktualny_pomiar) ) {
//czyli musielismy zawrócic, zatem dodajemy nowa dlugosc basenu do wyniku.
       ++wynik;
//i zmieniamy kierunek plyniecia z rosnącego na malejacy.
       rosnacy = false;
    }    
//analogicznie jezeli do tej pory zblizalismy sie do startowego brzegu (ciag byl maalejacy), a nowy pomiar jest wiekszy od poprzedniego
//to znaczy ze mamy zmiane ciagu z malejacego na rosnacy
    if ( (rosnacy==false) && (poprzedni_pomiar<aktualny_pomiar) ) {
//czyli musielismy zawrócic, zatem dodajemy nowa dlugosc basenu do wyniku.
       ++wynik;
// i zmieniamy kierunek plyniecia z malejacego na rosnacy.
       rosnacy = true;
    }
//Na koncu aktualny pomiar staje sie poprzednim dla kolejnego przebiegu petli
    poprzedni_pomiar = aktualny_pomiar;
 }

//Po zakonczeniu petli - analizy wszystkich pomiarow zegarka
//wypisujemy liczbe MINIMALNIE przepłynietych basenow przez Batjka, czyli liczbe koniecznych nawrotow plus 1.
 cout << wynik << "\n" ;
 
 return 0;
}

 

Liczba komentarzy: 2

Dodaj komentarz