【CodeForces】〖 Educational Codeforces Round 16〗A. King Moves

Problem here

Problem

The only king stands on the standard chess board. You are given his position in format “cd”, where c is the column from ‘a’ to ‘h’ and d is the row from ‘1’ to ‘8’. Find the number of moves permitted for the king.

Check the king’s moves here https://en.wikipedia.org/wiki/King_(chess).

King moves from the position e4

Input

The only line contains the king’s position in the format “cd”, where ‘c’ is the column from ‘a’ to ‘h’ and ‘d’ is the row from ‘1’ to ‘8’.

Output

Print the only integer x — the number of moves permitted for the king.

Example

input
e4
output
8

Solution

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


int main(){
    char cc;
    int c, d, ans = 0;
    cin >> cc >> d;
    cc -= 48;
    c = cc - '0';
    if(c + 1 <= 8 && c + 1 > 0){
        ans++;
        if(d+1 > 0 && d+1 <= 8)
            ans++;
        if(d-1 > 0 && d-1 <= 8)
            ans++;
    }
    if(c - 1 <= 8 && c - 1 > 0){
        ans++;
        if(d+1 > 0 && d+1 <= 8)
            ans++;
        if(d-1 > 0 && d-1 <= 8)
            ans++;
    }
    if(d + 1 > 0 && d + 1 <= 8)
        ans++;
    if(d - 1 > 0 && d - 1 <= 8)
        ans++;

    cout << ans << 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;
}

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

【CodeForces】A. Dragons

Problem here

Problem

Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he’s got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel’s outcome is determined by their strength. Initially, Kirito’s strength equals s.

If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito’s strength is not greater than the dragon’s strength xi, then Kirito loses the duel and dies. But if Kirito’s strength is greater than the dragon’s strength, then he defeats the dragon and gets a bonus strength increase by yi.

Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.

Input

The first line contains two space-separated integers s and n (1 ≤ s ≤ 104, 1 ≤ n ≤ 103). Then n lines follow: the i-th line contains space-separated integers xi and yi (1 ≤ xi ≤ 104, 0 ≤ yi ≤ 104) — the i-th dragon’s strength and the bonus for defeating it.

Output

On a single line print “YES” (without the quotes), if Kirito can move on to the next level and print “NO” (without the quotes), if he can’t.

Examples

input

2 2 
1 99 
100 0

output

YES

input

10 1 
100 100

output

NO

Note

In the first sample Kirito’s strength initially equals 2. As the first dragon’s strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.

In the second sample Kirito’s strength is too small to defeat the only dragon and win.

Solution

桐人23333先排序再做比較

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

struct dragon{
    int level;
    int bonus;
};
bool cmp(dragon &a, dragon &b){
    return a.level < b.level;
}

int main(){
    int s, n;
    while(cin >> s >> n){
        int bs = s;
        bool next = true;
        vector<dragon> vd;
        dragon d;
        while(n--){
            int l, b;
            cin >> l >> b;
            d.level = l;
            d.bonus = b;
            vd.push_back(d);
        }
        sort(vd.begin(), vd.end(), cmp);
        for(int i = 0; i < vd.size(); i++){
            if(bs > vd[i].level){
                bs += vd[i].bonus;
            }else{
                next = false;
            }
        }
        if(next){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

【CodeForces】A. Football

Problem here

Problem

Petya loves football very much. One day, as he was watching a football match, he was writing the players’ current positions on a piece of paper. To simplify the situation he depicted it as a string consisting of zeroes and ones. A zero corresponds to players of one team; a one corresponds to players of another team. If there are at least 7 players of some team standing one after another, then the situation is considered dangerous. For example, the situation 00100110111111101 is dangerous and 11110111011101 is not. You are given the current situation. Determine whether it is dangerous or not.

Input

The first input line contains a non-empty string consisting of characters “0” and “1”, which represents players. The length of the string does not exceed 100 characters. There’s at least one player from each team present on the field.

Output

Print “YES” if the situation is dangerous. Otherwise, print “NO”.

Examples

input

001001

output

NO

input

1000000001

output

YES

Solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    string input;
    while(cin >> input){
        int count = 0;
        char last = '/';
        for(int i = 0; i < input.length(); i++){
            if(last == '/'){
                last = input[i];
                count++;
                continue;
            } 
            if(input[i] == last){
                count++;
                if(count >= 7){
                    cout << "YES" << endl;
                    break;
                }
            }else if(input[i] != last){
                count = 0;
                last = input[i];
                count++;
            }
        }
        if(count < 7){
            cout << "NO" << endl;
        }
    }
    return 0;
}

【CodeForces】A. I Wanna Be the Guy

Problem here

Problem

There is a game called “I Wanna Be the Guy”, consisting of n levels. Little X and his friend Little Y are addicted to the game. Each of them wants to pass the whole game. 
Little X can pass only p levels of the game. And Little Y can pass only q levels of the game. You are given the indices of levels Little X can pass and the indices of levels Little Y can pass. Will Little X and Little Y pass the whole game, if they cooperate each other?

Input

The first line contains a single integer n (1 ≤  n ≤ 100).

The next line contains an integer p (0 ≤ p ≤ n) at first, then follows p distinct integers a1, a2, …, ap (1 ≤ ai ≤ n). These integers denote the indices of levels Little X can pass. The next line contains the levels Little Y can pass in the same format. It’s assumed that levels are numbered from 1 to n.

Output

If they can pass all the levels, print “I become the guy.”. If it’s impossible, print “Oh, my keyboard!” (without the quotes).

Example

input

4 
3 1 2 3 
2 2 4

output

I become the guy.

input

4 
3 1 2 3 
2 2 3

output

Oh, my keyboard!

Note

In the first sample, Little X can pass levels [1 2 3], and Little Y can pass level [2 4], so they can pass all the levels both.

In the second sample, no one can pass level 4.

Solution

開一個布爾數組
每次讀入都將狀態改成true

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

int main(){
    int n;
    cin >> n;
    vector<bool> level;
    for(int i = 0; i < n; i++){
        level.push_back(false);
    }
    int x;
    cin >> x;
    while(x--){
        int tmp;
        cin >> tmp;
        level[tmp-1] = true;
    }
    int y;
    cin >> y;
    while(y--){
        int tmp;
        cin >> tmp;
        level[tmp-1] = true;
    }
    bool succ = true;
    for(int i = 0; i < level.size(); i++){
        if(level[i] == false){
            succ = false;
        }
    }

    if(succ){
        cout << "I become the guy." << endl;
    }else{
        cout << "Oh, my keyboard!" << endl;
    }
    return 0;
}

【CodeForces】A. Lucky Division

Problem here

Problem

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5,17, 467 are not.

Petya calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number n is almost lucky.

Input

The single line contains an integer n (1 ≤ n ≤ 1000) — the number that needs to be checked.

Output

In the only line print “YES" (without the quotes), if number n is almost lucky. Otherwise, print “NO" (without the quotes).

Sample test(s)

input

47

output

YES

input

16

output

YES

input

78

output

NO

Note

Note that all lucky numbers are almost lucky as any number is evenly divisible by itself.

In the first sample 47 is a lucky number. In the second sample 16 is divisible by 4.

Solution

brute force

#include <iostream> using namespace std;   int nums[] = {4, 7, 44, 47, 74, 77, 444, 447, 477, 474, 747, 777, 744};   int main(){     int input;     cin >> input;     bool flat = false;     for(int i = 0; i < 13; i++){         if(input % nums[i] == 0){             flat = true;         }     }           if(flat){         cout << "YES" << endl;     }else{         cout << "NO" << endl;     }           return 0; }