USACO 2018 December Contest Bronze Division - The Bucket List

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can sort the cows by the starting position and run a brute force algorithm to distribute the cows.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;
ifstream f("blist.in");
ofstream g("blist.out");
int n, pus, tk[2002];
struct cows
{
    int st, sf, cate;
};
cows v[102];
bool cmp(cows a, cows b)
{
    return a.st < b.st;
}
int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> v[i].st >> v[i].sf >> v[i].cate;
    sort(v+1, v+n+1, cmp);
    for(int i = 1; i <= n; ++i)
    {
        int still = v[i].cate;
        for(int j = 1; j <= pus; ++j)
        {
            if(tk[j] <= v[i].st)
                tk[j] = 0;
            if(tk[j] == 0)
            {
                tk[j] = v[i].sf;
                --still;
                if(still == 0)
                    break;
            }
        }
        while(still)
        {
            ++pus, tk[pus] = v[i].sf;
            --still;
        }
    }
    g << pus;
    return 0;
}

with open("blist.in") as fin:
    tokens = fin.read().split()

n = int(tokens[0])
cows = []
idx = 1
for i in range(n):
    st = int(tokens[idx]); sf = int(tokens[idx+1]); cate = int(tokens[idx+2])
    idx += 3
    cows.append((st, sf, cate))

cows.sort(key=lambda x: x[0])

pus = 0
tk = []  

for st, sf, cate in cows:
    still = cate
    for j in range(pus):
        if tk[j] <= st:
            tk[j] = 0
        if tk[j] == 0:
            tk[j] = sf
            still -= 1
            if still == 0:
                break
    while still > 0:
        tk.append(sf)
        pus += 1
        still -= 1

with open("blist.out", "w") as fout:
    fout.write(str(pus) + "\n")