USACO 2018 February Contest Bronze Division - Taming

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simulate the process backwards and then count the remaining number of \(-1\).

Source codes

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

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

int main()
{
    ifstream cin("taming.in");
    ofstream cout("taming.out");

    int n;
    cin >> n;

    vector<int> v(n+1);
    for(int i = 1; i <= n; i++)
        cin >> v[i];

    if(v[1] != 0 && v[1] != -1)
    {
        cout << -1;
        return 0;
    }
    v[1] = 0;
    for(int i = n; i >= 1; i--)
    {
        if(v[i] > 0)
        {
            if(v[i-1] == v[i] - 1 || v[i-1] == -1)
                v[i-1] = v[i] - 1;
            else
            {
                cout << -1;
                return 0;
            }
        }
    }
    int cnt = 0, cntneg = 0;
    for(int i = 1; i <= n; i++)
        if(v[i] == 0)
            cnt++;
        else
            if(v[i] == -1)
                cntneg++;
    cout << cnt << " " << cnt+cntneg << '\n';

    return 0;
}

with open("taming.in", "r") as fin:
    tokens = fin.read().split()

n = int(tokens[0])
v = [0] * (n + 1)
for i in range(1, n + 1):
    v[i] = int(tokens[i])

if v[1] != 0 and v[1] != -1:
    with open("taming.out", "w") as fout:
        fout.write("-1")
    exit(0)

v[1] = 0
for i in range(n, 0, -1):
    if v[i] > 0:
        if v[i - 1] == v[i] - 1 or v[i - 1] == -1:
            v[i - 1] = v[i] - 1
        else:
            with open("taming.out", "w") as fout:
                fout.write("-1")
            exit(0)

cnt = 0
cntneg = 0
for i in range(1, n + 1):
    if v[i] == 0:
        cnt += 1
    elif v[i] == -1:
        cntneg += 1

with open("taming.out", "w") as fout:
    fout.write(f"{cnt} {cnt + cntneg}\n")