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