【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;
    }

【CodeForces】C. Drazil and Factorial

Problem here

Problem

Drazil is playing a math game with Varda.

Let’s define  for positive integer x as a product of factorials of its digits. For example, 

First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:

1. x doesn’t contain neither digit 0 nor digit 1.
2. = 

Help friends find such number.

INPUT

The first line contains an integer n (1 ≤ n ≤ 15) — the number of digits in a.

The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.

OUTPUT

Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

Sample

input

4 
1234

output

33222

input

3 
555

output

555

Solution

答案參考這裡

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string arr[] = {"0", "0", "2", "3", "322", "5", "53", "7", "7222", "7332"};

bool cmp(char &a, char &b){
    return a > b;
}

int main(){
    int n;
    cin >> n;

    string input;
    cin >> input;
    string result = "";
    for(int i = 0; i < input.length(); i++){
        if(input[i] != '0' && input[i] != '1'){
            result += arr[input[i]-'0'];
        }
    }
    sort(result.begin(), result.end(), cmp);
    cout << result << endl;

    return 0;
}  

【CodeForces】A. Pouring Rain

Problem here

Problem

A lot of people in Berland hates rain, but you do not. Rain pacifies, puts your thoughts in order. By these years you have developed a good tradition — when it rains, you go on the street and stay silent for a moment, contemplate all around you, enjoy freshness, think about big deeds you have to do.

Today everything had changed quietly. You went on the street with a cup contained water, your favorite drink. In a moment when you were drinking a water you noticed that the process became quite long: the cup still contained water because of rain. You decided to make a formal model of what was happening and to find if it was possible to drink all water in that situation.

Thus, your cup is a cylinder with diameter equals d centimeters. Initial level of water in cup equals h centimeters from the bottom.

You drink a water with a speed equals v milliliters per second. But rain goes with such speed that if you do not drink a water from the cup, the level of water increases on e centimeters per second. The process of drinking water from the cup and the addition of rain to the cup goes evenly and continuously.

Find the time needed to make the cup empty or find that it will never happen. It is guaranteed that if it is possible to drink all water, it will happen not later than after 104 seconds.

Note one milliliter equals to one cubic centimeter.

Input

The only line of the input contains four integer numbers d, h, v, e (1 ≤ d, h, v, e ≤ 104), where:

• d — the diameter of your cylindrical cup
• h — the initial level of water in the cup
• v — the speed of drinking process from the cup in 
  milliliters per second 
  e — the growth of water because of rain if 
  you do not drink from the cup.

Output

If it is impossible to make the cup empty, print “NO” (without quotes).

Otherwise print “YES” (without quotes) in the first line. In the second line print a real number — time in seconds needed the cup will be empty. The answer will be considered correct if its relative or absolute error doesn’t exceed 10 - 4. It is guaranteed that if the answer exists, it doesn’t exceed 104.

Sample

input

1 2 3 100

output

NO

input

1 1 1 1

output

YES
3.659792366325

Solution

#include <iostream>
#include <iomanip>
using namespace std;
double pi = 3.1415926;
int main(){

    double d, h, v, e;
    while(cin >> d >> h >> v >> e){
        if(4*v > pi*d*d*e){
            cout << "YES" << endl;
            cout << fixed << setprecision(5) << (pi*d*d*h) / (4*v-pi*d*d*e) << endl; 
        }else{
            cout << "NO" << endl;
        }
    }

    return 0;
}