USACO 2018 December Contest Bronze Division - Back and Forth

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We only have to deal with 5 days, so we can run a complete search algorithm to check all ways to distribute the milk in buckets.

Source codes

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

#include <bits/stdc++.h>
using namespace std;
ifstream f("backforth.in");
ofstream g("backforth.out");
int v[12], v2[12];
map<int, int>sol;
void bkt(int d, int v[], int v2[], int xa, int xb)
{
    if(d == 5)
    {
        sol[xa]++;
        return;
    }
    if(d % 2 == 1)
    {
        for(int i = 1; i <= 10; ++i)
        {
            int v3[12], v4[12];
            for(int j = 1; j <= 10; ++j)
                v4[j] = v2[j];
            v4[11] = v[i];
            for(int j = 1; j < i; ++j)
                v3[j] = v[j];
            for(int j = i+1; j <= 10; ++j)
                v3[j-1] = v[j];
            bkt(d + 1, v3, v4, xa - v[i], xb + v[i]);
        }
    }
    else
    {
        for(int i = 1; i <= 11; ++i)
        {
            int v3[12], v4[12];
            for(int j = 1; j <= 9; ++j)
                v3[j] = v[j];
            v3[10] = v2[i];
            for(int j = 1; j < i; ++j)
                v4[j] = v2[j];
            for(int j = i+1; j <= 11; ++j)
                v4[j-1] = v2[j];
            bkt(d + 1, v3, v4, xa + v2[i], xb + v2[i]);
        }
    }
}
int main()
{
    for(int i = 1; i <= 10; ++i)
        f >> v[i];
    for(int i = 1; i <= 10; ++i)
        f >> v2[i];
    bkt(1, v, v2, 1000, 1000);
    g << sol.size() << '\n';
    return 0;
}

def bkt(d, v, v2, xa, xb):
    global sol
    if d == 5:
        sol.add(xa)
        return
    if d % 2 == 1:
        for i in range(1, len(v)):
            new_v2 = [None] + v2[1:] + [v[i]]
            new_v3 = [None] + v[1:i] + v[i+1:]
            bkt(d + 1, new_v3, new_v2, xa - v[i], xb + v[i])
    else:
        for i in range(1, len(v2)):
            new_v3 = [None] + v[1:10] + [v2[i]]
            new_v4 = [None] + v2[1:i] + v2[i+1:]
            bkt(d + 1, new_v3, new_v4, xa + v2[i], xb + v2[i])

with open("backforth.in", "r") as fin:
    tokens = fin.read().split()
initial_v = [None] + [int(x) for x in tokens[:10]]
initial_v2 = [None] + [int(x) for x in tokens[10:20]]

sol = set()
bkt(1, initial_v, initial_v2, 1000, 1000)

with open("backforth.out", "w") as fout:
    fout.write(str(len(sol)) + "\n")