The Meeting Place Cannot Be Changed – Codeforces – Omówienie zadania – Binary Search po wyniku

Szczegółowe omówienie zadania The Meeting Place Cannot Be Changed:

Link do powyższego omówienia zadania The Meeting Place Cannot Be Changed: https://youtu.be/x9mQ4zs410g?t=1468
Omówienie kodu zadania The Meeting Place Cannot Be Changed: https://youtu.be/x9mQ4zs410g?t=5210

Link do treści zadania The Meeting Place Cannot Be Changed: https://codeforces.com/problemset/problem/780/B

Zadanie The Meeting Place Cannot Be Changed wymaga zastosowania techniki Binary Search po wyniku (wyszukiwanie połówkowe): https://youtu.be/x9mQ4zs410g?t=2435
Złożoność Binary search po wyniku: https://youtu.be/x9mQ4zs410g?t=4820
Kod algorytmu Binary Search po wyniku: https://youtu.be/x9mQ4zs410g?t=5391

Zadanie z Codeforces! https://youtu.be/gTEmPXiN53U?t=13
Pozwala stworzyć fantastyczne CV! https://youtu.be/gTEmPXiN53U?t=5557


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

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/
Zajęcia: : https://oki.org.pl/harmonogram-zajec/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu The Meeting Place Cannot Be Changed, który jest omówiony w powyższym filmie i który otrzymuje 100%


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 60*1000 + 7;
const double EPS = 1e-7; // 10^(-7)
// poczatkowa pozycja i-tej osoby
int pozycja[MAXN];
// maksymalna predkosc i-tej osoby
int predkosc[MAXN];
int liczba_osob;
bool mogaSieSpotkac(double czas)
{
// poczatkowe miejsce spotkania
double L = 0;
double R = 1e9;
// przejdz po kolei po osobach i zaktualizuj miejsce spotkania
for (int i = 1; i <= liczba_osob; ++i) {
// droga, jaka i-ta osoba może przebyć w jedna strone
double droga = (double)predkosc[i] * czas;
// gdzie najdalej na lewo/prawo moze dotrzec i-ta osoba
double lewo = (double)pozycja[i] - droga;
double prawo = (double)pozycja[i] + droga;
L = max(lewo, L);
R = min(prawo, R);
// jezeli miejsce spotkania nie istnieje, zwroc false
if (L > R)
return false;
}
// rozpatrzylismy wszystkie osoby, mamy miejsce spotkania
return true;
}
double BS(double lewo, double prawo)
{
while (prawo - lewo > EPS) {
double srodek = (lewo + prawo) / 2;
if (mogaSieSpotkac(srodek))
prawo = srodek; // nie ma sensu patrzec na czasy wieksze
else
lewo = srodek; // nie ma sensu patrzec na czasy mniejsze
}
return lewo;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> liczba_osob;
for (int i = 1; i <= liczba_osob; ++i)
cin >> pozycja[i];
for (int i = 1; i <= liczba_osob; ++i)
cin >> predkosc[i];
cout << fixed << setprecision(7);
cout << BS(0, 1e9) << '\n'; // [0, 10^9]
return 0;
}
Kod C++ programu The Meeting Place Cannot Be Changed, który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu The Meeting Place Cannot Be Changed, który otrzymuje 100%:

EPS = 1e-7
def mogaSieSpotkac(czas):
# poczatkowe miejsce spotkania
L = 0
R = 1e9
# przejdz po kolei po osobach i zaktualizuj miejsce spotkania
for poz, v in zip(pozycja, predkosc):
# droga, jaka i-ta osoba może przebyć w jedna strone
droga = v * czas
# gdzie najdalej na lewo/prawo moze dotrzec i-ta osoba
lewo = poz - droga
prawo = poz + droga
L = max(lewo, L)
R = min(prawo, R)
# jezeli miejsce spotkania nie istnieje, zwroc false
if (L > R):
return False
# rozpatrzylismy wszystkie osoby, mamy miejsce spotkania
return True
def BS(lewo, prawo):
while (prawo - lewo > EPS):
srodek = (lewo + prawo) / 2
if (mogaSieSpotkac(srodek)):
prawo = srodek # nie ma sensu patrzec na czasy wieksze
else:
lewo = srodek # nie ma sensu patrzec na czasy mniejsze
return lewo
liczba_osob = int(input())
# poczatkowa pozycja i-tej osoby
pozycja = list(map(int, input().split()))
# maksymalna predkosc i-tej osoby
predkosc = list(map(int, input().split()))
print(BS(0, 1e9))

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz