Social Distancing – Omówienie zadania – Binary Search po wyniku – Amerykańska Olimpiada Informatyczna USACO

Szczegółowe omówienie zadania Social Distancing:

Link do powyższego omówienia zadania Social Distancing: https://youtu.be/YexKHKMxIiw?t=1650
Omówienie kodu zadania Social Distancing: https://youtu.be/YexKHKMxIiw?t=3297

Link do treści zadania Social Distancing: http://www.usaco.org/index.php?page=viewproblem2&cpid=1038

Zadanie Social Distancing to szkoleniowe zadanie pokazujące algorytm Binary Search po wyniku (wyszukiwanie połówkowe): https://youtu.be/YexKHKMxIiw?t=2048
Złożoność Binary search po wyniku: https://youtu.be/YexKHKMxIiw?t=2937
Kod algorytmu Binary Search po wyniku: https://youtu.be/YexKHKMxIiw?t=3410

Co robi uczestnik Olimpiady? Dokąd prowadzi nasza droga? https://youtu.be/YexKHKMxIiw?t=1410

Zadanie Social Distancing pochodzi z dywizji Silver Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów: https://youtu.be/KI7un-HU_Hk?t=49
Daje piękny wpis do CV: https://youtu.be/P2sLFZBjOmM?t=7223
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO? https://youtu.be/K7fZfJ8nN6A?t=6848
Co to jest USACO? https://youtu.be/nvA92I5nU0c?t=1414

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 "Social Distancing", który jest omówiony w powyższym filmie i który otrzymuje 100%


#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+50;
pair<ll, ll> Przedzialy[N];

int CzyMoznaRozmiescic(int n, int m, ll d){
	ll ostatni = -2*d;
	ll wynik = 0;
	for(int i=1; i<=m; i++){
		while( max(ostatni+d, Przedzialy[i].first) <= Przedzialy[i].second ){
			wynik++;
			ostatni = max(ostatni+d, Przedzialy[i].first);
			if ( wynik >= (ll)n ) return 1;
		}
	}
	return 0;
}

ll LiczWynik(int n, int m){ 
	ll p, k, s;
	p = 0;
	k = (ll)1e18;
	while(p<k){
		s=(p+k+1)/2;
		if( CzyMoznaRozmiescic(n, m, s) ) p=s;
		else k=s-1;
	}
	return p;
}

int main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 freopen("socdist.in", "r", stdin);
 freopen("socdist.out", "w", stdout);
	int n, m;
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		cin>>Przedzialy[i].first>>Przedzialy[i].second;
	}
	sort(Przedzialy+1, Przedzialy+1+m);
	cout << LiczWynik(n, m) << "\n";
	return 0;
}
Kod C++ programu "Social Distancing", który jest omówiony w powyższym filmie i który otrzymuje 100%

 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz