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