【USACO】Barn Repair

Problem here

Solution

dp~~~

/*
ID: LeongHouHeng
PROG: barn1
LANG: C++
 */

 #include <iostream>
 #include <memory.h>
 #include <string.h>
 #include <fstream>
 #include <algorithm>
 using namespace std;

 ifstream fin("barn1.in");
 ofstream fout("barn1.out");

 int cows[201];
 int dp[250][60];
 int MIN_NUM = 2e9;
 int main(){
     int M, S, C;
     fin >> M >> S >> C;

     for(int i = 0; i < C; i++){
         fin >> cows[i];
     }
     sort(cows, cows+C);
     memset(dp, 0x1f, sizeof(dp));
     dp[0][0] = 1;
     for(int i = 1; i < C; i++){
         for(int j = 0; j <= i && j < M; j++){
            dp[i][j] = dp[i-1][j] + (cows[i] - cows[i-1]);
            if(j > 0)
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + 1);
            if(C-1 == i)
                MIN_NUM = min(MIN_NUM, dp[i][j]);
         }
     }

     fout << MIN_NUM << endl;
 }

【USACO】Transformations

Problem

A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

#1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.

#2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.

#3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.

#4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).

#5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).

#6: No Change: The original pattern was not changed.

#7: Invalid Transformation: The new pattern was not obtained by any of the above methods.

In the case that more than one transform could have been used, choose the one with the minimum number above.

PROGRAM NAME: transform

INPUT FORMAT

Line 1:A single integer, N

Line 2..N+1:N lines of N characters (each either @' or-'); this is the square before transformation

Line N+2..2*N+1:N lines of N characters (each either @' or-'); this is the square after transformation

SAMPLE INPUT (file transform.in)

3 @-@

--- @@- @-@ @-- --@

OUTPUT FORMAT

A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the before' representation to theafter' representation.

SAMPLE OUTPUT (file transform.out)

1

Solution

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

    ifstream fin("transform.in");
    ofstream fout("transform.out");

    int main(){
        int n;
        fin >> n;
        int arr[n+1][n+1];
        int tar[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                char input;
                fin >> input;
                if(input == '@') arr[i][j] = 1;
                else    arr[i][j] = 0;
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                char input;
                fin >> input;
                if(input == '@') tar[i][j] = 1;
                else    tar[i][j] = 0;
            }
        }

        int count = 0;
        int ans = 99;
        //
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 1)    ans = 1;
        count = 0;
        //
        int arr180[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                arr180[j][n-i+1] = arr[i][j];
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr180[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 2)    ans = 2;
        count = 0;
        //
        int arr270[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                arr270[j][n-i+1] = arr180[i][j];
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr270[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 3)    ans = 3;
        count = 0;
        //
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][j] == tar[i][n-j+1]){
                    count++;
                }
            }
        }
        if(count == n*n && ans > 4)    ans = 4;
        count = 0;
        //
        int rarr[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                rarr[i][n-j+1] = arr[i][j];
            }
        }

        /**/
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(rarr[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 5)    ans = 5;
        count = 0;
        // /
        int rarr180[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                rarr180[j][n-i+1] = rarr[i][j];
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(rarr180[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 5)    ans = 5;
        count = 0;
        // /
        int rarr270[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                rarr270[j][n-i+1] = rarr180[i][j];
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(rarr270[i][j] == tar[j][n-i+1])
                    count++;
            }
        }
        if(count == n*n && ans > 5)    ans = 5;
        count = 0;
        //
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][j] == tar[i][j]){
                    count++;
                }
            }
        }
        if(count == n*n && ans > 6)     ans = 6;
        count = 0;
        //
        if(ans == 99){
            fout << 7 << endl;
        }else{
            fout << ans << endl;
        }

        return 0;
    }

【USACO】Milking Cows

Problem

Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):
The longest time interval at least one cow was milked.
The longest time interval (after milking starts) during which no cows were being milked.

PROGRAM NAME: milk2

INPUT FORMAT

Line 1:
The single integer, N

Lines 2..N+1:
Two non-negative integers less than 1,000,000, respectively the starting and ending time in seconds after 0500

SAMPLE INPUT (file milk2.in)

3
300 1000
700 1200
1500 2100

OUTPUT FORMAT

A single line with two integers that represent the longest continuous time of milking and the longest idle time.SAMPLE ##OUTPUT (file milk2.out)
900 300

Solution

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <fstream>
    #include <memory.h>
    #include <utility>
    using namespace std;

    ifstream fin("milk2.in");
    ofstream fout("milk2.out");

    int main(){
        int n;
        fin >> n;
        int min_s = 999999, max_e = 0;
        pair<int, int> time;
        vector<pair<int, int> > times;
        for(int i = 0; i < n; i++){
            int s, e;
            fin >> s >> e;
            time = make_pair(s, e);
            times.push_back(time);
            if(s < min_s)   min_s = s;
            if(e > max_e)   max_e = e;
        }
        int work = 0, max_work = 0, free = 0, max_free = 0;
        vector<pair<int, int> >::iterator it;
        for(int i = min_s; i <= max_e; i++){
            for(it = times.begin(); it != times.end(); it++){
                if(it->first <= i && it->second > i){
                    work++;
                    if(max_free < free){
                        max_free = free;
                    }
                    free = 0;
                    break;
                }
            }
            if(it ==  times.end()){
                free++;
                if(work > max_work){
                    max_work = work;
                }
                work = 0;
            }
        }

        fout << max_work << " " << max_free << endl;

        return 0;
    }

【USACO】Greedy Gift Givers

題目內容

A group of NP (2 ≤ NP ≤ 10) uniquely named friends has decided to exchange gifts of money. Each of these friends might or might not give some money to any or all of the other friends. Likewise, each friend might or might not receive money from any or all of the other friends. Your goal in this problem is to deduce how much more money each person gives than they receive.

The rules for gift-giving are potentially different than you might expect. Each person sets aside a certain amount of money to give and divides this money evenly among all those to whom he or she is giving a gift. No fractional money is available, so dividing 3 among 2 friends would be 1 each for the friends with 1 left over -- that 1 left over stays in the giver's "account".

In any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.

Given a group of friends, no one of whom has a name longer than 14 characters, the money each person in the group spends on gifts, and a (sub)list of friends to whom each person gives gifts, determine how much more (or less) each person in the group gives than they receive.

IMPORTANT NOTE

The grader machine is a Linux machine that uses standard Unix conventions: end of line is a single character often known as '\n'. This differs from Windows, which ends lines with two charcters, '\n' and '\r'. Do not let your program get trapped by this!

PROGRAM NAME: gift1

INPUT FORMAT

Line 1:	The single integer, NP
Lines 2..NP+1:	Each line contains the name of a group member
Lines NP+2..end:	NP groups of lines organized like this: The first line in the group tells the person's name who will be giving gifts. The second line in the group contains two numbers: The initial amount of money (in the range 0..2000) to be divided up into gifts by the giver and then the number of people to whom the giver will give gifts, NGi (0 ≤ NGi ≤ NP-1). If NGi is nonzero, each of the next NGi lines lists the the name of a recipient of a gift.

SAMPLE INPUT (file gift1.in)

5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0

OUTPUT FORMAT

The output is NP lines, each with the name of a person followed by a single blank followed by the net gain or loss (final_money_value - initial_money_value) for that person. The names should be printed in the same order they appear on line 2 of the input.

All gifts are integers. Each person gives the same integer amount of money to each friend to whom any money is given, and gives as much as possible that meets this constraint. Any money not given is kept by the giver.

SAMPLE OUTPUT (file gift1.out)

dave 302
laura 66
owen -359
vick 141
amr -150

Solution

總之就是
收到的錢 – 送出的錢

需要注意的是送出的錢除以送出的人後要取整數

e.g.   dave

dave 首先送了200元給laura、owen和vick
所以是200 / 3 = 66.6666667 取整數(不是四捨五入!)後 =66

因為送了給3人所以

66*3 = 198

後來owen送給dave 500 元

所以是

500 – 198 = 〖302〗<—-輸出的答案

代碼

/* ID: 你的USACO ID PROG: gift1 LANG: C++  */ #include <iostream> #include <fstream> #include <string> #include <vector>   using namespace std;   struct gift{     string name;     int gets_money;     int give_money;       };   int main(){     ifstream fin("gift1.in");     ofstream fout("gift1.out");           gift g;     vector<gift> gifts;           int np;     string tmp_name;     fin >> np;           for(int i = 0; i < np; i++){ fin >> tmp_name;         g.name = tmp_name;         g.gets_money = 0;         g.give_money = 0;         gifts.push_back(g);     }           int tmp_giveTotal = 0, tmp_give = 0;     int tmp_giveMoney = 0;     string tmp_gifname;         for(int i = 0; i < np; i++){ fin >> tmp_name;               for(int j = 0; j < gifts.size(); j++){ if(tmp_name == gifts[j].name){ fin >> tmp_give >> tmp_giveTotal;                                   if(tmp_giveTotal > 0){                                       tmp_giveMoney = tmp_give / tmp_giveTotal;                     gifts[j].give_money += (tmp_giveMoney*tmp_giveTotal);                                          for(int k = 0; k < tmp_giveTotal; k++){ fin >> tmp_gifname;                                              for(int l = 0; l < gifts.size(); l++){                             if(tmp_gifname == gifts[l].name){                                 gifts[l].gets_money += tmp_giveMoney;                                                               }                         }                     }                                   }             }         }     }           int result = 0;     for(int i = 0; i < np; i++){         result = gifts[i].gets_money - gifts[i].give_money;         fout << gifts[i].name << " " << result << endl;     }                 return 0; }