USACO 2017 January Contest Bronze Division - Hoof, Paper, Scissors

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simple brute force problem, we try all permutations and find the best score.

Source codes

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

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

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

    int n;
    cin >> n;

    vector<pair<int, int> > vp(n);
    for(int i = 0; i < n; i++)
        cin >> vp[i].first >> vp[i].second;

    int maxscore = 0;
    vector<int> bt = {0, 1, 2};
    vector<int> poz = {0, 1, 2};

    do{
        for(int i = 0; i < 3; i++)
            poz[bt[i]] = i;
        int score = 0;
        for(int i = 0; i < n; i++)
            if((poz[vp[i].first] + 1) % 3 == poz[vp[i].second])
                score++;
        maxscore = max(maxscore, score);
    }while(next_permutation(bt.begin(), bt.end()));

    cout << maxscore;
    return 0;
}

import itertools

with open("hps.in", "r") as fin:
    n = int(fin.readline().strip())
    vp = []
    for _ in range(n):
        a, b = map(int, fin.readline().split())
        vp.append((a-1, b-1))

maxscore = 0
for bt in itertools.permutations([0, 1, 2]):
    poz = [0] * 3
    for i in range(3):
        poz[bt[i]] = i
    score = 0
    for a, b in vp:
        if (poz[a] + 1) % 3 == poz[b]:
            score += 1
    maxscore = max(maxscore, score)

with open("hps.out", "w") as fout:
    fout.write(str(maxscore))