【POJ】Balance

Problem here

Description

Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance. 
It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights. 
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.

Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device. 
It is guaranteed that will exist at least one solution for each test case at the evaluation.

Input

The input has the following structure: 
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20); 
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: ‘-’ for the left arm and ‘+’ for the right arm); 
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights’ values.

Output

The output contains the number M representing the number of possibilities to poise the balance. 
Sample Input

2 4 
-2 3 
3 4 5 8 
Sample Output

2

Solution

力矩：力和力臂的乘积。

科科 

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

int cost[30], weight[30];
int dp[25][15001];
int n, m;

int main(){
    while(~scanf("%d %d", &n, &m)){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &cost[i]);
        for(int i = 1; i <= m; i++)
            scanf("%d", &weight[i]);

        dp[0][7500] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 0; j <= 15000; j++)
                if(dp[i-1][j])
                    for(int k = 1; k <= n; k++)
                        dp[i][j+weight[i] * cost[k]] += dp[i-1][j];

        printf("%d", dp[m][7500]);
    }
    return 0;
}

【POJ】Painter

Problem here

Description

The local toy store sells small fingerpainting kits with between three and twelve 50ml bottles of paint, each a different color. The paints are bright and fun to work with, and have the useful property that if you mix X ml each of any three different colors, you get X ml of gray. (The paints are thick and “airy”, almost like cake frosting, and when you mix them together the volume doesn’t increase, the paint just gets more dense.) None of the individual colors are gray; the only way to get gray is by mixing exactly three distinct colors, but it doesn’t matter which three. Your friend Emily is an elementary school teacher and every Friday she does a fingerpainting project with her class. Given the number of different colors needed, the amount of each color, and the amount of gray, your job is to calculate the number of kits needed for her class.

Input

The input consists of one or more test cases, followed by a line containing only zero that signals the end of the input. Each test case consists of a single line of five or more integers, which are separated by a space. The first integer N is the number of different colors (3 <= N <= 12). Following that are N different nonnegative integers, each at most 1,000, that specify the amount of each color needed. Last is a nonnegative integer G <= 1,000 that specifies the amount of gray needed. All quantities are in ml.

Output

For each test case, output the smallest number of fingerpainting kits sufficient to provide the required amounts of all the colors and gray. Note that all grays are considered equal, so in order to find the minimum number of kits for a test case you may need to make grays using different combinations of three distinct colors.

Sample Input

3 40 95 21 0 
7 25 60 400 250 0 60 0 500 
4 90 95 75 95 10 
4 90 95 75 95 11 
5 0 0 0 0 0 333 
0

Sample Output

2 
8 
2 
3 
4

SOLUTION

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

int color[13];

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

int main(){

    int n;
    while(cin >> n){
        if(n == 0)
            break;
        int count = 0;
        for(int i = 0; i < n; i++)
            cin >> color[i];

        int gray;
        cin >> gray;

        sort(color, color+n, cmp);
        if(color[0] % 50)
            count = color[0]/50+1;
        else
            count = color[0]/50;

        for(int i = 0; i < n; i++)
            color[i] = count * 50 - color[i];

            while(gray!=0){
                sort(color, color+n, cmp);

                if(color[2] <= 0){
                    count++;
                    for(int i = 0; i < n; i++)
                        color[i] += 50;
                }
                color[0] --;
                color[1] --;
                color[2] --;
                gray--;
            }
            cout << count << endl;
    }

    return 0;
}

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

【POJ】Power of Cryptography

Description

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest.
This problem involves the efficient computation of integer roots of numbers.
Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find).

Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 such that kn = p.
Output

For each integer pair n and p the value k should be printed, i.e., the number k such that k n =p.

Sample Input

2 16
3 27
7 4357186184021382204544

Sample Output

4
3
1234

Solution

kn=p
p=k1n

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

int main(){
    double n, p;
    while(cin >> n >> p){
        double k = pow(p, 1/n);
        cout << k << endl;
    }
    return 0;
}

【POJ】Y2K Accounting Bug

Problem here

Description

Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. 
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.

Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.

Input

Input is a sequence of lines, each containing two positive integers s and d.

Output

For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.

Sample Input

59 237 
375 743 
200000 849694 
2500000 8000000 
Sample Output

116 
28 
300612 
Deficit

Solution

#include <iostream>
using namespace std;
/*
ssssd-> ssssd ssssd ss
sssdd-> sssdd sssdd ss
ssddd-> ssddd ssddd ss
sdddd-> sdddd sdddd sd
ddddd-> ddddd ddddd dd
*/
int main(){
    int s, d;
    while(cin >> s >> d){
        int ans = 0;
        if(4*s < d)
            ans = 10*s - 2*d;
        else if(3*s < 2*d)
            ans = 8*s - 4*d;
        else if(2*s < 3*d)
            ans = 6*s - 6*d;
        else if(s < 4*d)
            ans = 3*s - 9*d;
        else
            ans = -12*d;

        if(ans > 0)
            cout << ans << endl;
        else
            cout << "Deficit" << endl;
    }

    return 0;
}

【POJ】Heavy Transportation

Problem here

Description

Background

Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight. 
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.

Problem

You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions.

Input

The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.

Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.

Sample Input

1 
3 3 
1 2 3 
1 3 4 
2 3 5 
Sample Output

Scenario #1: 
4

Solution

#include <iostream>
#include <queue>
#include <memory.h>
#include <vector>
#include <utility>
#include <stdio.h>
#include <algorithm>
using namespace std;
int s, n, m;
bool visit[1001];
int dis[1001];
int map[1001][1001];
int dijkstra(){
    for(int i = 1; i <= n; i++){
        dis[i] = map[1][i];
    }
    memset(visit, false, sizeof(visit));
    visit[1] = true;
    for(int i = 1; i <= n-1; i++){
        int maxnum = 0;
        int u;
        for(int j = 1; j <= n; j++)
            if(visit[j] == false && dis[j] > maxnum){
                maxnum = dis[j];
                u = j;
            }

        visit[u] = true;

        for(int k = 1; k <= n; k++)
            if(visit[k] == false){
                int ans = min(maxnum, map[u][k]);
                if(ans > dis[k])
                    dis[k] = ans;
            }

    }
    return dis[n];
}

int main(){
    scanf("%d", &s);
    for(int i = 1; i <= s; i++){
        memset(map, 0, sizeof(map));
        scanf("%d %d", &n, &m);
        for(int j = 1; j <= m; j++){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            map[a][b] = map[b][a] = c;
        }
        printf("Scenario #%d", i);
        cout << ":" << endl;
        cout << dijkstra() << endl << endl;

    }
    return 0;
}

【POJ】Frogger

Problem here

Description

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. 
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps. 
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence. 
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.

Input

The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.

Output

For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.

Sample Input

2 
0 0 
3 4

3 
17 4 
19 4 
18 5

0

Sample Output

Scenario #1 
Frog Distance = 5.000

Scenario #2 
Frog Distance = 1.414

Solution

#include <iostream>
#include <memory.h>
#include <math.h>
#include <vector>
#include <utility>
#include <cmath>
#include <iomanip>
#define INF 999999
using namespace std;

float map[201][201];
bool visit[201];
int n;
vector<pair<int, int> > coor;

float alg(pair<int, int> p1, pair<int, int> p2){
    float a = p1.first - p2.first;
    float b = p1.second - p2.second;
    float u = sqrt(pow(a, 2) + pow(b, 2));
    //cout << "\\\\" << u << endl;
    float ans = abs(u);
    return ans;
}

int main(){
    int cnt = 0;
    while(cin >> n){
        memset(map, INF, sizeof(map));
        memset(visit, false, sizeof(visit));
        if(n == 0)
            break;
        cnt++;
        for(int i = 1; i <= n; i++){
            int x, y;
            cin >> x >> y;
            coor.push_back(make_pair(x, y));
        }
        for(int i = 0; i < coor.size(); i++){
            for(int j = 0; j < coor.size(); j++){
                map[i+1][j+1] = map[j+1][i+1] = alg(coor[i], coor[j]);
            }
        }

        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    map[j][k] = min(map[j][k], max(map[j][i], map[i][k]));

        float min = INF;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(map[i][j] < min && map[i][j] != 0)
                    min = map[i][j];

        cout << "Scenario #" << cnt << endl;
        cout << fixed << setprecision(3) << "Frog Distance = " << map[1][2] << endl;

        /////////////////////////
        coor.clear();
        cout << endl;
    }
    return 0;
}