Omówienie zadania Berry Picking (USACO Silver)

Omówienie zadania Berry Picking (USACO Silver)

Szczegółowe omówienie zadania Berry Picking – Amerykańska Olimpiada Informatyczna USACO:

Link do powyższego omówienia zadania Berry Picking :
https://youtu.be/a7E8i-dXyCM


Link do treści zadania Berry Picking :
http://usaco.org/index.php?page=viewproblem2&cpid=990


Zadanie Berry Picking pochodzi z Amerykańskiej Olimpiady Informatycznej USACO – poziom silver
Jest to typowe zadanie na pomysł – na poziomie II etapu / finału Olimpiady Informatycznej Juniorów.

Jak się uczyć na podstawie takiego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019

——-
Kod C++ programu Berry Picking, który jest omówiony w powyższym filmie i który otrzymuje 100%


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

void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

constexpr int M=1e3+7;

int t[M];

int border;
bool cmp(int a, int b){
	return a%border > b%border;
}

int main(){
	setIO("berries");
	
	int n,k,mx=0,res=0,res2,bigger;
	
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>t[i];
		mx=max(mx,t[i]);
	}

	for(int i=1; i<=mx; i++){
		bigger=res2=0;
		for(int j=1; j<=n; j++) bigger+=t[j]/i;
		
		if(bigger<(k>>1)) break;
		else if(bigger>=k) res2=i*(k>>1);
		else{
			res2=i*(bigger-(k>>1));
			
			border=i;
			sort(t+1,t+n+1,cmp);
			
			for(int j=1; j<=k-bigger; j++) res2+=t[j]%i;
		}
		
		res=max(res,res2);
	}
	
	cout<<res;
	
	return 0;
}
Link do pliku ze wzorcowym kodem C++ zadania Berry Picking 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz