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
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/
https://szkopul.edu.pl/task_archive/oig/
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
https://youtu.be/QgLyXYmFQeU?t=2019
——-
Kod C++ zadania Basen, który jest omówiony w powyższym filmie i który otrzymuje 100%
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; }
To niezłe akademy
A da się to zadanie zrobić szybciej?