Szczegółowe omówienie zadania Lampy:
Link do powyższego omówienia zadania Lampy:
https://youtu.be/0ri7j0X_Oqo?t=1649
Link do treści zadania Lampy oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/ZpgyJvo98HkU-D9X3lcuI7hN/site
–
Zadanie Lampy jest prostym zadaniem wymagającym
1. Obserwacji i narysowania:
https://youtu.be/0ri7j0X_Oqo?t=2159
2. Zastanowienia się gdzie dołożyć kolejną dodatkową lampę
https://youtu.be/0ri7j0X_Oqo?t=3387
3. Wymyślenia rozwiązania brutalnego
https://youtu.be/0ri7j0X_Oqo?t=4135
4. Ulepszenia bruta szybkim wyborem poprawy
https://youtu.be/0ri7j0X_Oqo?t=4528
5. Złożoność optymalnego rozwiązania:
https://youtu.be/0ri7j0X_Oqo?t=7063
6. Kod zadania Lampy:
https://youtu.be/0ri7j0X_Oqo?t=5412
–
Zadanie Lampy pochodzi z finału Olimpiady Informatycznej Gimnazjalistów – poprzednika Olimpiady Informatycznej Juniorów.
Pięknie pokazuje. które pokazuje, że każdy może być w finale Olimpiady Informatycznej!
https://youtu.be/0ri7j0X_Oqo?t=171
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
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
–
Kod C++ programu Lampy, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include<iostream>
#include<queue>
#include<iomanip>
const int MAX_LICZBA_LAMP=1e5+7;
int DlugosciPrzerw[MAX_LICZBA_LAMP];
int IleLampWPrzerwie[MAX_LICZBA_LAMP];
std::priority_queue < std::pair<double, int> > kolejka_najwiekszych_popraw;
double CiemnaPrzestrzenPrzerwy (int dlugosc_przerwy, int ile_lampy_w_przerwie) {
int liczba_trojkatow;
double przeciwprostokatna;
double pole_trojkata;
double pole_wszystkich_trojkotow;
liczba_trojkatow = ile_lampy_w_przerwie+1;
przeciwprostokatna = (double)dlugosc_przerwy / (double)liczba_trojkatow;
pole_trojkata = przeciwprostokatna * przeciwprostokatna / (double)4;
pole_wszystkich_trojkotow = (double)liczba_trojkatow * pole_trojkata;
return pole_wszystkich_trojkotow;
}
int main (){
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int ile_oryginalnych_lamp, ile_dodatkowych_lamp, ile_przerw, dlugosc_kotarza;
long long pozycja_poprzedniej_lampy, pozycja_akt_lampy;
int numer_przerwy, i;
double suma_ciemnej_przestrzeni, kolejna_poprawa;
std::pair <double, int> najwieksza_poprawa;
std::cin >> ile_oryginalnych_lamp >> ile_dodatkowych_lamp >> dlugosc_kotarza;
ile_przerw = ile_oryginalnych_lamp-1;
std::cin >> pozycja_poprzedniej_lampy;
for(i=0; i<ile_przerw; ++i){
std::cin >> pozycja_akt_lampy;
DlugosciPrzerw[i] = pozycja_akt_lampy - pozycja_poprzedniej_lampy;
pozycja_poprzedniej_lampy = pozycja_akt_lampy;
}
for(i=0; i<ile_przerw; ++i){
kolejna_poprawa = CiemnaPrzestrzenPrzerwy(DlugosciPrzerw[i], 0) - CiemnaPrzestrzenPrzerwy(DlugosciPrzerw[i], 1);
kolejka_najwiekszych_popraw.push( std::make_pair(kolejna_poprawa, i) );
}
for(i=0; i<ile_dodatkowych_lamp; ++i){
najwieksza_poprawa = kolejka_najwiekszych_popraw.top();
kolejka_najwiekszych_popraw.pop();
numer_przerwy = najwieksza_poprawa.second;
++IleLampWPrzerwie[numer_przerwy];
kolejna_poprawa = CiemnaPrzestrzenPrzerwy (DlugosciPrzerw[numer_przerwy], IleLampWPrzerwie[numer_przerwy]) -
CiemnaPrzestrzenPrzerwy (DlugosciPrzerw[numer_przerwy], IleLampWPrzerwie[numer_przerwy]+1);
kolejka_najwiekszych_popraw.push( std::make_pair(kolejna_poprawa, numer_przerwy) );
}
suma_ciemnej_przestrzeni = 0;
for(i=0; i<ile_przerw; i++){
suma_ciemnej_przestrzeni += CiemnaPrzestrzenPrzerwy(DlugosciPrzerw[i], IleLampWPrzerwie[i]);
}
std::cout << std::fixed << std::setprecision(9) << suma_ciemnej_przestrzeni << "\n";
return 0;
}
Kod C++ programu Lampy, który jest omówiony w powyższym filmie i który otrzymuje 100%