Tävlingsprogrammering/Uppgifter/Tunnelbaneplatser

Från Wikibooks
Hoppa till navigering Hoppa till sök

Se problemet

4- och 3-grupper behöver egna sätesgrupper, men i varje 3-grupp kan även en 1-grupp sitta, så vi subtraherar min(3grupper,1grupper) från antal 1-grupper. Nu har vi endast 2- och 1-grupper kvar, och då går det alltid att fylla ut så att endast en sätesgrupp inte blir tom. Därför adderar vi bara (antal personer kvar)/4 avrundat uppåt till svaret. Notera att om man gör heltalsdivision i C++ så avrundas svaret i vanliga fall nedåt, så vi måste addera 1 så länge det inte är delbart med 4.

Lösningsförslag i C++:

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

int main(){
    cin.sync_with_stdio(false);
    vi v(5);
    rep(i,1,5)
        cin>>v[i];
    ll ans = v[4]+v[3];
    v[1] -= min(v[3],v[1]);
    ll left = (v[2]*2+v[1])
    ans += left/4 + (left%4!=0);

    cout<<ans<<endl;
}