USACO 2016 February Contest Silver Division - Milk Pails

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The constraints for this problem are quite small and given that the operations consist in changing the contents in both pails, it motivates us to try some sort of a flood fill algorithm, where we can have as a state a pair \((i, j)\), which represents that one of the pails has \(i\) units and the other one has \(j\) units.

After making this observation, all we have to do is to incorporate the operations described in the statement by using this floodfill model. You can check out the code below for more details.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <queue>
using namespace std;

int dist[102][102];
bool visited[102][102];

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

    int x, y, k, m;
    cin >> x >> y >> k >> m;

    queue<pair<int, int> > q;
    q.push({0, 0});
    visited[0][0] = 1;

    int ans = 1000000;

    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        ans = min(ans, abs(m - p.first - p.second));

        if (dist[p.first][p.second] == k)
            continue;

        if (!visited[x][p.second]) {
            visited[x][p.second] = 1;
            dist[x][p.second] = dist[p.first][p.second] + 1;
            q.push({x, p.second});
        }
        if (!visited[p.first][y]) {
            visited[p.first][y] = 1;
            dist[p.first][y] = dist[p.first][p.second] + 1;
            q.push({p.first, y});
        }

        if (!visited[0][p.second]) {
            visited[0][p.second] = 1;
            dist[0][p.second] = dist[p.first][p.second] + 1;
            q.push({0, p.second});
        }
        if (!visited[p.first][0]) {
            visited[p.first][0] = 1;
            dist[p.first][0] = dist[p.first][p.second] + 1;
            q.push({p.first, 0});
        }

        int nw_x = p.first;
        int nw_y = p.second;
        if (p.second + p.first <= x) {
            nw_x = p.first + p.second, nw_y = 0;
        }
        else {
            nw_y -= (x - nw_x), nw_x = x;
        }

        if (!visited[nw_x][nw_y]) {
            visited[nw_x][nw_y] = 1;
            dist[nw_x][nw_y] = dist[p.first][p.second] + 1;
            q.push({nw_x, nw_y});
        }

        nw_x = p.first;
        nw_y = p.second;
        if (p.second + p.first <= y) {
            nw_y = p.first + p.second, nw_x = 0;
        }
        else {
            nw_x -= (y - nw_y), nw_y = y;
        }

        if (!visited[nw_x][nw_y]) {
            visited[nw_x][nw_y] = 1;
            dist[nw_x][nw_y] = dist[p.first][p.second] + 1;
            q.push({nw_x, nw_y});
        }
    }

    cout << ans;
    return 0;
}