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;
}