USACO 2022 December Contest Bronze Division - Feeding the Cows

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The problem can be solved greedily, through picking feeding slots along the grid. However, we need to be careful about the placement of the last cow in order to avoid any further complications.

You can check out my code for more details.

Source codes

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
    {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        char ans[n];
        for(int i = 0; i < n; i++)
            ans[i] = '.';
        int cnt = 0;        
        int lstG = -1, lstH = -1;
        for(int i = 0; i < n; i++)
        {
            if(s[i] == 'G' && lstG < i)
            {
                cnt++;
                if(i + k >= n-1)
                {
                    int poz = n-1;
                    while(ans[poz] != '.')
                        poz--;
                    ans[poz] = 'G', lstG = poz + k;
                }
                else
                    ans[i + k] = 'G', lstG = i + k + k;
            }
            if(s[i] == 'H' && lstH < i)
            {
                cnt++;
                if(i + k >= n-1)
                {
                    int poz = n-1;
                    while(ans[poz] != '.')
                        poz--;
                    ans[poz] = 'H', lstH = poz + k;
                }
                else
                    ans[i + k] = 'H', lstH = i + k + k;
            }
        }

        cout << cnt << '\n';
        for(int i = 0; i < n; i++)
            cout << ans[i];
        cout << '\n';
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    s = input().strip()
    ans = ['.'] * n
    cnt = 0
    lstG = -1
    lstH = -1
    for i in range(n):
        if s[i] == 'G' and lstG < i:
            cnt += 1
            if i + k >= n - 1:
                poz = n - 1
                while ans[poz] != '.':
                    poz -= 1
                ans[poz] = 'G'
                lstG = poz + k
            else:
                ans[i + k] = 'G'
                lstG = i + k + k
        if s[i] == 'H' and lstH < i:
            cnt += 1
            if i + k >= n - 1:
                poz = n - 1
                while ans[poz] != '.':
                    poz -= 1
                ans[poz] = 'H'
                lstH = poz + k
            else:
                ans[i + k] = 'H'
                lstH = i + k + k
    print(cnt)
    print(''.join(ans))