USACO 1.2 Milking Cows

Simple brutal force search with intervals.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
int start, end;
Interval(int start, int end) : start(start), end(end) {}
bool operator < (const Interval& interval) const {
return start < interval.start;
}
};

int main () {
string str;
ifstream fin ("milk2.in");
ofstream fout ("milk2.out");

vector<Interval> intervals;

int farmers;
fin >> farmers;
for (int i = 0; i < farmers; ++i) {
int start, end;
fin >> start >> end;
intervals.emplace_back(Interval(start, end));
}

std::sort(intervals.begin(), intervals.end());

int maxOverlap = 0, maxGap = 0;
Interval it = intervals[0];
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i].start > it.end) {
// none overlap
maxOverlap = std::max(maxOverlap, it.end - it.start);
maxGap = std::max(maxGap, intervals[i].start - it.end);
it = intervals[i];
} else {
it.end = std::max(it.end, intervals[i].end);
}
}

maxOverlap = std::max(maxOverlap, it.end - it.start);

fout << maxOverlap << " " << maxGap << std::endl;

return 0;
}

USACO 1.1 Broken Necklace

Brutal force O(N^2) solution.


#include<iostream>
#include<fstream>
#include<string>

using namespace std;

int main ()
{
string str;
int n, i, l, r, mx = 0;
ifstream fin ("beads.in");
ofstream fout ("beads.out");
fin >> n;
fin >> str;
str += str;
for (i = 0; i < n; i++) {
l = r = 1;
int k = i + 1;
char flag;
while(l < n) {
int j = i;
while(str[j] == 'w')
j++;
flag = str[j];
if (str[k] == flag || str[k] == 'w')
k++, l++;
else break;
}

k = i + n - 2;
while(r < n) {
int j = i;
while(str[j] == 'w')
j--;
if (str[k] == str[i + n - 1] || str[k] == 'w')
k--, r++;
else break;
}

if (l + r > mx) mx = l + r;
}

if (mx > n) mx = n;
fout << mx << endl;
return 0;
}

USACO 1.1 Friday

Straightforward brutal force implementation.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

class Checker {
public:
int day, year, offset;

Checker() : day(1), year(1900), offset(1) {
frequentCounterList = {0, 0, 0 , 0, 0, 0, 0, 0};
month2days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
}

void traverse(int n) {
for (int i = 0; i < n; ++i) {
for (int month = 1; month <= 12; ++month) {
day = offset + 12;
frequentCounterList[day % 7 + 1]++;

if (month == 2) {
if (isLeapYear(year))
offset += 29;
else
offset += 28;
} else
offset += month2days[month];
}
++year;
}
}

vector<int> getFrequency() const {
return frequentCounterList;
}

private:
vector<int> frequentCounterList;
vector<int> month2days;

private:
bool isLeapYear(int year) {
if (year % 100 == 0)
return year % 400 == 0;

return year % 4 == 0;
};
};

int main() {
ofstream fout ("friday.out");
ifstream fin ("friday.in");

string years;
getline(fin, years);
Checker checker;
checker.traverse(stoi(years));

auto list = checker.getFrequency();
fout << list[7] << " " << list[1] << " " <<
list[2] << " " << list[3] << " " << list[4] << " " << list[5] << " " <<
list[6] << endl;

return 0;
}