【國際象棋】國象－－開局(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;
}

【TopCoder】 SRM 144 div 2 200

Problem

Problem Statement

Computers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date. Your task in this problem is to write a method whatTime, which takes an int, seconds, representing the number of seconds since midnight on some day, and returns a string formatted as “< H >:< M >:< S >”. Here, < H > represents the number of complete hours since midnight, < M > represents the number of complete minutes since the last complete hour ended, and < S > represents the number of seconds since the last complete minute ended. Each of < H >, < M >, and < S > should be an integer, with no extra leading 0’s. Thus, if seconds is 0, you should return “0:0:0”, while if seconds is 3661, you should return “1:1:1”. 
Definition

Class:

Time

Method:

whatTime

Parameters:

int

Returns:

string

Method signature:

string whatTime(int seconds) 
(be sure your method is public)

Limits

Time limit (s):

2.000

Memory limit (MB):

64

Constraints

seconds will be between 0 and 24*60*60 - 1 = 86399, inclusive.

Examples

0)

0 
Returns: “0:0:0”

1)

3661 
Returns: “1:1:1”

2)

5436 
Returns: “1:30:36”

3)

86399 
Returns: “23:59:59”

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Solution

Get 155.57/200 points

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

class Time{
    public:
        string whatTime(int seconds);

};

string Time::whatTime(int seconds){
    int h = seconds / 60 / 60;
    int m = seconds / 60 - h*60;
    int s = seconds - h*60*60 - m*60;
    stringstream ss;
    string str, str2, str3;
    ss << h;
    ss >> str;
    ss.clear();
    ss << m;
    ss >> str2;
    ss.clear();
    ss << s;
    ss >> str3;
    return str + ":" + str2 + ":" + str3;
}

【UVa】495 - Fibonacci Freeze

Problem here

Problem

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …) are defined by the recurrence:

eqnarray20

Write a program to calculate the Fibonacci Numbers.

INPUT&OUTPUT

The input to your program would be a sequence of numbers smaller or equal than 5000, each on a separate line, specifying which Fibonacci number to calculate.

Your program should output the Fibonacci number for each input value, one per line.

Sample

input

5 
7 
11

output

The Fibonacci number for 5 is 5 
The Fibonacci number for 7 is 13 
The Fibonacci number for 11 is 89

Solution

這題要用大數加法才不會WA

#include <iostream>
using namespace std;
int f[5001][5001] = {0};

int main(){
    f[1][0] = 1;
    for(int i = 2; i <= 5000; i++){
        for(int j = 0; j < 5001; j++){
            f[i][j] += f[i-1][j] + f[i-2][j];
            f[i][j+1] += f[i][j]/10;
            f[i][j] %= 10;
        }
    }
    int n;
    while(cin >> n){
        cout << "The Fibonacci number for " << n << " is "; 
        int i;
        for( i = 5000 ; i >= 0 ; i-- )
            if( f[n][i] )
             break;
        if( i == -1 )
          cout << 0;
        else
          for( ; i >= 0 ; i-- )
            cout << f[n][i];
        cout << endl;
    }
    return 0;
}

【LeetCode】70. Climbing Stairs

Problem here

Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

這題之前做過 
就是超級樓梯那條

class Solution {
public:
    int climbStairs(int n) {
        vector<int> f;
        f.push_back(1);
        f.push_back(1);
        for(int i = 2; i <= n; i++){
            f.push_back(f[i-1] + f[i-2]);
        }
        return f[n];

    }
};

【NEFU】17-数字三角形

Problem here

Problem

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 
给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。 
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

INPUT

输入数据有多组，每组输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

OUTPUT

输出最大的和。

Sample

input

5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 
3 
1 
2 3 
1 1 1

output

30 
5

Solution

7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5 
以這個為例 
設x,y為位置 
則f(x,y)為到了(x,y)時的路徑長度 
所以可以得知 
f(1,1) = 7 <—第一個數嘛 
f(1+1, 1)=f(1,1)+f(1+1,1)=10 
f(1+1,1+1)=f(1,1)+f(1+1,1+1)=15 
f(3,1)= f(2,1)+f(3,1)=18 
f(3,2)=max(10,15)+1=16 
由此可知 
f(x,y)=max(f(x-1,y), f(x-1,y-1))+f(x,y)

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

int main(){
    int n;
    while(cin >> n){
        int tg[101][101];
        memset(tg, 0, sizeof(tg));
        cin >> tg[1][1];
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                cin >> tg[i][j];
                tg[i][j] = max(tg[i-1][j], tg[i-1][j-1]) + tg[i][j];
            }
        }
        int max = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(max < tg[i][j]){
                    max = tg[i][j];
                }
            }
        }
        cout << max << endl;
    }
    return 0;
}

【HDU】2041-超级楼梯

Problem here

Problem

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

INPUT

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

OUTPUT

对于每个测试实例，请输出不同走法的数量

Sample

input

2 
2 
3

output

1 
2

Solution

設x為樓梯數 
f(x)為上樓梯的方法 
因為已知 
f(1)=1 <—因為一開始就站在第一級，所以不用再走上一級 
f(2)=1<—只有兩級樓梯，所以只能向上走一級 
f(3)=2<—每次只能走一或兩級，所以只有兩種方法 
f(4)=f(3)+f(2)=3<—當只走上一級時，就會變成f(3)的情況；當只走上兩級時，就會變成f(2)的情況 
. 
. 
. 
etc. 
由此得知 
f(x) = f(x-1)+f(x-2)

#include <iostream>
using namespace std;

int main(){

    int n;
    while(cin >> n){
        int s[50];
        s[1] = 1;
        s[2] = 1;
        for(int i = 3; i <= 40; i++){
            s[i] = s[i-1] + s[i-2];
        }
        while(n--){
            int m;
            cin >> m;
            cout << s[m] << endl;
        }
    }

    return 0;
}

【GoogleCodeJam Qualification Round 2016】Problem A. Counting Sheep

Problem here

Problem

Bleatrix Trotter the sheep has devised a strategy that helps her fall asleep faster. First, she picks a number N. Then she starts naming N, 2 × N, 3 × N, and so on. Whenever she names a number, she thinks about all of the digits in that number. She keeps track of which digits (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) she has seen at least once so far as part of any number she has named. Once she has seen each of the ten digits at least once, she will fall asleep.

Bleatrix must start with N and must always name (i + 1) × N directly after i × N. For example, suppose that Bleatrix picks N = 1692. She would count as follows:

N = 1692. Now she has seen the digits 1, 2, 6, and 9. 
2N = 3384. Now she has seen the digits 1, 2, 3, 4, 6, 8, and 9. 
3N = 5076. Now she has seen all ten digits, and falls asleep. 
What is the last number that she will name before falling asleep? If she will count forever, print INSOMNIA instead.

INPUT

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a single integer N, the number Bleatrix has chosen.

OUTPUT

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the last number that Bleatrix will name before falling asleep, according to the rules described in the statement.

Limits

1 ≤ T ≤ 100.

Small dataset

0 ≤ N ≤ 200.

Large dataset

0 ≤ N ≤ 106.

Sample

input

5 
0 
1 
2 
11 
1692

output

Case #1: INSOMNIA 
Case #2: 10 
Case #3: 90 
Case #4: 110 
Case #5: 5076

Solution

很紅很暴力 
注：1844674407370955161是long long 的最大值 
正解在這裡

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include "memory.h"
using namespace std;

ifstream fin("A-large.in"); //ifstream fin("A-small-attempt0.in");
ofstream fout("A-large.out");//ofstream fout("A-small-attempt0.out");

bool check[10];

int slove(int input){
    for(unsigned long long i = 1; i <= 1844674407370955161; i++){
        stringstream ss;
        unsigned long long n;
        n = input * i;
        string str;
        ss << n;
        ss >> str;
        for(int j = 0; j < str.length(); j++){
            switch(str[j]){
                case '0':
                    check[0] = true;
                    break;
                case '1':
                    check[1] = true;
                    break;
                case '2':
                    check[2] = true;
                    break;
                case '3':
                    check[3] = true;
                    break;
                case '4':
                    check[4] = true;
                    break;
                case '5':
                    check[5] = true;
                    break;
                case '6':
                    check[6] = true;
                    break;
                case '7':
                    check[7] = true;
                    break;
                case '8':
                    check[8] = true;
                    break;
                case '9':
                    check[9] = true;
                    break;

            }
        }
        bool pass = true;
        for(int j = 0; j < sizeof(check); j++){
            if(check[j] == false){
                pass = false;
            }
        }
        if(pass){
            return n;
        }else{
            continue;
        }
    }
    return -1;
}

int main(){

    int t;
    while(fin >> t){
        for(int i = 1; i <= t; i++){
            int input;
            fin >> input;
            memset(check, false, sizeof(check));
            fout << "Case #" << i << ": ";
            if(input <= 0){
                fout << "INSOMNIA" << endl;
            }else{
                fout << slove(input) << endl;
            }
        }
    }

    return 0;
}

【UVa】11389 - The Bus Driver Problem

Problem here

Problem

In a city there are n bus drivers. Also there are n morning bus routes and n afternoon bus routes with 
various lengths. Each driver is assigned one morning route and one evening route. For any driver, if 
his total route length for a day exceeds d, he has to be paid overtime for every hour after the first d 
hours at a flat r taka / hour. Your task is to assign one morning route and one evening route to each 
bus driver so that the total overtime amount that the authority has to pay is minimized.

INPUT

The first line of each test case has three integers n, d and r, as described above. In the second line, 
there are n space separated integers which are the lengths of the morning routes given in meters. 
Similarly the third line has n space separated integers denoting the evening route lengths. The lengths 
are positive integers less than or equal to 10000. The end of input is denoted by a case with three 0’s.

OUTPUT

For each test case, print the minimum possible overtime amount that the authority must pay. 
Constraints 
• 1 ≤ n ≤ 100 
• 1 ≤ d ≤ 10000 
• 1 ≤ r ≤ 5

Sample

input

2 20 5 
10 15 
10 15 
2 20 5 
10 10 
10 10 
0 0 0

output

50 
0

Solution

Sorting

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

bool cmp1(int &a, int &b){
    return a < b;
}
bool cmp2(int &a, int &b){
    return a > b;
}

int main(){

    int n, d, r;
    while(cin >> n >> d >> r){
        if(n == 0 && d == 0 && r== 0)
            break;

        vector<int> m, e;
        for(int i = 0; i < n; i++){
            int tm;
            cin >> tm ;
            m.push_back(tm);
        }
        for(int i = 0; i < n; i++){
            int te;
            cin >> te;
            e.push_back(te);
        }
        sort(m.begin(), m.end(), cmp1);
        sort(e.begin(), e.end(), cmp2);
        int ot = 0;
        for(int i = 0 ;i < n; ++i){
            int men = m[i] + e[i];
            if(men > d){
                ot += (men-d) * r;
            }
        }
        cout << ot << endl;
    }

    return 0;
}