USACO 2019 February Contest Bronze Division - Measuring Traffic

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

In short, you need to be careful about avoiding any case where the interval makes no sense, you would be left with something less than 0 or anything similar.

Source codes

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

#include <iostream>
#include <fstream>

using namespace std;

int n, tp[3][1002];

int minIn = 10000000, maxIn;
int minOut = 10000000, maxOut;

pair<int, int> valid(int x)
{
    pair<int, int> ans = {x, x};
    for(int i = 0; i < n; i++)
    {
        if(tp[0][i] == 0)
        {
            ans.first += tp[1][i];
            ans.second += tp[2][i];
        }
        if(tp[0][i] == 2)
        {
            ans.first -= tp[2][i];
            ans.second -= tp[1][i];
            if(ans.second < 0)
                return {-1, -1};
            ans.first = max(ans.first, 0);
        }
        if(tp[0][i] == 1)
        {
            ans.first = max(ans.first, tp[1][i]);
            ans.second = min(ans.second, tp[2][i]);
            if(ans.first > ans.second)
                return {-1, -1};
        }
    }
    return ans;
}
int main()
{
    ifstream cin("traffic.in");
    ofstream cout("traffic.out");

    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;

        if(s.size() == 3)
            tp[0][i] = 2;
        if(s.size() == 4)
            tp[0][i] = 1;

        cin >> tp[1][i];
        cin >> tp[2][i];
    }

    for(int i = 0; i <= 1000000; i++)
    {
        pair<int, int> cnt = valid(i);
        if(cnt.first >= 0)
        {
            minIn = min(minIn, i);
            maxIn = i;
            minOut = min(minOut, cnt.first);
            maxOut = max(maxOut, cnt.second);
        }
    }

    cout << minIn << " " << maxIn << '\n';
    cout << minOut << " " << maxOut << '\n';
    return 0;
}

with open("traffic.in", "r") as fin:
    n = int(fin.readline().strip())
    tp = [[0] * n for _ in range(3)]
    for i in range(n):
        parts = fin.readline().split()
        s = parts[0]
        tp[1][i] = int(parts[1])
        tp[2][i] = int(parts[2])
        if len(s) == 3:
            tp[0][i] = 2
        if len(s) == 4:
            tp[0][i] = 1

def valid(x):
    ans_first = x
    ans_second = x
    for i in range(n):
        if tp[0][i] == 0:
            ans_first += tp[1][i]
            ans_second += tp[2][i]
        if tp[0][i] == 2:
            ans_first -= tp[2][i]
            ans_second -= tp[1][i]
            if ans_second < 0:
                return (-1, -1)
            ans_first = max(ans_first, 0)
        if tp[0][i] == 1:
            ans_first = max(ans_first, tp[1][i])
            ans_second = min(ans_second, tp[2][i])
            if ans_first > ans_second:
                return (-1, -1)
    return (ans_first, ans_second)

minIn = 10000000
maxIn = 0
minOut = 10000000
maxOut = 0

for i in range(1000001):
    cnt = valid(i)
    if cnt[0] >= 0:
        minIn = min(minIn, i)
        maxIn = i
        minOut = min(minOut, cnt[0])
        maxOut = max(maxOut, cnt[1])

with open("traffic.out", "w") as fout:
    fout.write(f"{minIn} {maxIn}\n")
    fout.write(f"{minOut} {maxOut}\n")