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

【國際象棋】國象－－開局(I)[白方]

有時候身為黑方時，用作為白方時的套路，卻不能達到白方時的效果，這是為什麼呢？

而要怎樣做才能走出對自己更有利的局面呢？

一般對白方來說，e4是最常見的第一步

而這時候黑方會怎樣應對呢？

對稱防禦：1. e4 e5 2.Kf3

黑方這樣做確實可以阻止白方的前進，然而白方的kf3馬上就可以吃死對方了，這時候黑方可以走Kc6來防止白方的進攻，但這樣做真的做成更有利的局面嗎？

不對稱防禦：1. e4 c5

與對稱法相反的動作，做出了使局勢平衡的效果


斯堪的納維亞防禦：1.e4 d5

用同樣的走法來應對白方，而白方是否吃掉黑棋會對之後的棋局做成影響

法式防禦: 1. e4 e6

Caro-Kann防禦: 1.e4 c6

 Pirc防禦: 1.e4 d6 2.d4 Nf6 3.Nc3 g6

——-所有圖片裁自http://zh.lichess.org/editor

【國際象棋】－－Start

診le段時間好好甘研究下棋譜～

圖片來自Lev Alburt 的 Chess Openings for White, Explained

這算是國際象棋的基礎吧

記錄方法：

國王－－K

皇后－－Q

車／城堡－－R

馬／騎士－－N

主教－－B

默認不寫就是 卒

格式：

Nc3 //馬移動到e5

a3 //卒移動到a3

axb5 //a4的卒吃掉b5的棋子

Bb5xc6 或 Bxc6 //c5的主教吃掉c6的棋子

當有兩只棋子可以走到同一格時，就要寫出該棋的起始格

e.g. Rad3 //a3的車移動到d3

【CodeForces】Registration system

problem here

Problem

A new e-mail service “Berlandesk” is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that’s why they ask you to help. You’re suggested to implement the prototype of site registration system. The system should work on the following principle.

Each time a new user wants to register, he sends to the system a request with his name. If such a name does not exist in the system database, it is inserted into the database, and the user gets the response OK, confirming the successful registration. If the name already exists in the system database, the system makes up a new user name, sends it to the user as a prompt and also inserts the prompt into the database. The new name is formed by the following rule. Numbers, starting with 1, are appended one after another to name (name1, name2, …), among these numbers the least i is found so that namei does not yet exist in the database.

INPUT

The first line contains number n (1 ≤ n ≤ 105). The following n lines contain the requests to the system. Each request is a non-empty line, and consists of not more than 32 characters, which are all lowercase Latin letters.

OUTPUT

Print n lines, which are system responses to the requests: OK in case of successful registration, or a prompt with a new name, if the requested name is already taken.

Sample

input

4 
abacaba 
acaba 
abacaba 
acab

output

OK 
OK 
abacaba1 
OK

input

6 
first 
first 
second 
second 
third 
third

output

OK 
first1 
OK 
second1 
OK 
third1

Solution

hash table

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        unordered_map<string, int> um;
        while(n--){
            string input;
            cin >> input;
            unordered_map<string, int>::const_iterator it = um.find(input);
            if(it == um.end()){
                um.insert(pair<string, int>(input, 1));
                cout << "OK" << endl;
            }else{
               stringstream ss;
               int num = it->second;
               ss << num;
               string str;
               ss >> str;
               string key = it->first;
               string data = key + str;
               um.erase(it->first);
               um.insert(pair<string, int>(key, ++num));
               cout << data << endl;
            }
        }
    }

    return 0;
}