【UVa】11636 - Hello World!

Problem here

Solution

water water water water ~~~

#include <iostream>
using namespace std;

int main(){

    int n;
    int kase = 1;
    while(cin >> n){
        if(n < 0)
            break;

        int ans = 1;
        int cnt = 0;
        while(ans < n){
            ans = ans * 2;
            cnt++;
        }
        cout << "Case " << kase++ << ": " << cnt << endl;
    }
    return 0;
}

【UVa】10684 - The jackpot

Problem here

Problem

As Manuel wants to get rich fast and without too much work, he decided to make a career in gambling.
Initially, he plans to study the gains and losses of players, so that, he can identify patterns of consecutive
wins and elaborate a win-win strategy. But Manuel, as smart as he thinks he is, does not know how to
program computers. So he hired you to write programs that will assist him in elaborating his strategy.
Your first task is to write a program that identifies the maximum possible gain out of a sequence of
bets. A bet is an amount of money and is either winning (and this is recorded as a positive value), or
losing (and this is recorded as a negative value).

Input

The input set consists of a positive number N ≤ 10000 , that gives the length of the sequence, followed
by N integers. Each bet is an integer greater than 0 and less than 1000.
The input is terminated with N = 0.

Output

For each given input set, the output will echo a line with the corresponding solution. If the sequence
shows no possibility to win money, then the output is the message ‘Losing streak.’

Sample Input

6
-99 10 -9 10 -5 4
3
-999 100 -9
5
12 -4
-10 4
9
3
-2 -1 -2
0

Sample Output

The maximum winning streak is 11.
The maximum winning streak is 100.
The maximum winning streak is 13.
Losing streak.

Solution

設dp[i] 是以i為結尾的最大收入
取「dp[i-1]加上第i次賭錢的結果」與「只計第i次賭錢的結果」較大的一個
所以有dp[i] = max(dp[i-1] + data[i], data[i]);
前題是要先設dp[0] = data[0](沒有dp[0-1] ，且以第一個數作為結尾的答案只有一個嘛\\就是第一個數嘛orz)

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

int main(){
    int n;
    while(cin >> n){
        if(n == 0)
            break;

        int dp[100001];
        vector<int> data;
        for(int i = 0; i < n; i++){
            int input;
            cin >> input;
            data.push_back(input);
        }
        dp[0] = data[0];

        for(int i = 1; i < n; i++){
            dp[i] = max(dp[i-1] + data[i], data[i]);
        }

        int ans = -100000;
        for(int i = 0; i < n; i++){
            if(ans < dp[i])
                ans = dp[i];
        }
        if(ans <= 0)
            cout << "Losing streak." << endl;
        else
            cout << "The maximum winning streak is " << ans << "." << endl;
    }

    return 0;
}

【POJ】Sumsets

Problem here

Description

Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:

1) 1+1+1+1+1+1+1 
2) 1+1+1+1+1+2 
3) 1+1+1+2+2 
4) 1+1+1+4 
5) 1+2+2+2 
6) 1+2+4

Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).

Input

A single line with a single integer, N.

Output

The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).

Sample Input

7

Sample Output

6

Source

USACO 2005 January Silver

Solution

當n為奇數時，dp[n] = dp[n-1] 
當n為偶數且含有1時，dp[n] = dp[n-1] 
當n為偶數且不含有1時，dp[n]=dp[n/2] 
所以當n為偶數時，dp[i] = (dp[i-1] + dp[i/2])%1000000000

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

int dp[1000001];

int main(){
    dp[0] = 0;
    dp[1] = 1;
    int n;
    while(cin >> n){
        for(int i = 2; i <= n; i++){
            if(i % 2 == 0)
                dp[i] = (dp[i-1] + dp[i/2])%1000000000;
            else
                dp[i] = dp[i-1];
        }
        cout << dp[n] << endl;
    }

    return 0;
}

【POJ】Cow Bowling

Problem here

Description

The cows don’t use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this:

      7



    3   8



  8   1   0



2   7   4   4

4 5 2 6 5 
Then the other cows traverse the triangle starting from its tip and moving “down” to one of the two diagonally adjacent cows until the “bottom” row is reached. The cow’s score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame.

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

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

Sample Output

30

Hint

Explanation of the sample:

      7

     *

    3   8

   *

  8   1   0

   *

2   7   4   4

   *

4 5 2 6 5 
The highest score is achievable by traversing the cows as shown above.

Solution

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

int dp[355][355], cost[355][355];

int main(){

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin >> cost[i][j];
        }
    }
    dp[0][0] = cost[0][0];
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j - 1 < 0)
                dp[i][j] = dp[i-1][j] + cost[i][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + cost[i][j];
        }
    }
    int answer = 0;
    for(int i = 0; i < n; i++){
        if(answer < dp[n-1][i])
            answer = dp[n-1][i];
    }
    cout << answer << endl;
    return 0;
}

【UVa】10298 - Power Strings

Problem here

---

Given two strings a and b we define a ∗ b to be their concatenation. For 
example, if a = ‘abc’ and b = ‘def’ then a ∗ b = ‘abcdef’. If we think of 
concatenation as multiplication, exponentiation by a non-negative integer 
is defined in the normal way: a 
0 = ‘’ (the empty string) and a 
(n+1) = 
a ∗ (a 
n).

Input

Each test case is a line of input representing s, a string of printable characters. 
The length of s will be at least 1 and will not exceed 1 million 
characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a 
n for some string 
a.

Sample Input

abcd 
aaaa 
ababab 
.

Sample Output

1 
4 
3

Solution

#include <iostream>
#include <string>
//#include <fstream>
#define MAX_NUM 9999999
using namespace std;

//ifstream fin("10298.in");
//ofstream fout("10298.out");

int next_pos[1000001];

void getNext(string str){
    next_pos[0] = -1;
    int j = 0, k = -1;
    while(j < str.size()){
        if(k == -1 || str[j] == str[k]){
            next_pos[++j] = ++k;
        }
        else{
            k = next_pos[k];
        }
    }
}

int main(){
    string input;
    while(cin >> input){
        if(input == ".")
            break;

        getNext(input);
        int length = input.size();
        if(length % (length- next_pos[length]) == 0 && next_pos[length] != 0)
            cout << length / (length - next_pos[length]) << endl;
        else
            cout << 1 << endl;
    }

    return 0;
}

【UVa】455 - Periodic Strings

Problem here 
A character string is said to have period k if it can be formed by concatenating one or more repetitions 
of another string of length k. For example, the string ”abcabcabcabc” has period 3, since it is formed 
by 4 repetitions of the string ”abc”. It also has periods 6 (two repetitions of ”abcabc”) and 12 (one 
repetition of ”abcabcabcabc”). 
Write a program to read a character string and determine its smallest period.

Input

The first line oif the input file will contain a single integer N indicating how many test case that your 
program will test followed by a blank line. Each test case will contain a single character string of up 
to 80 non-blank characters. Two consecutive input will separated by a blank line.

Output

An integer denoting the smallest period of the input string for each input. Two consecutive output are 
separated by a blank line.

Sample Input

1 
HoHoHo

Sample Output

2

Solution

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

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

    while(kase--){
        string line;
        getline(cin, line);
        bool pass = false;
        string input;
        cin >> input;
        for(int i = 1; i <= input.size()-1; i++){
            if(input.size() % i == 0){
                int j;
                for(j = i; j < input.size(); j++){
                    if(input[j] != input[j%i])
                        break;
                }
                if(j == input.size()){
                    cout << i << endl;
                    pass = true;
                    break;
                }
            }
        }
        if(!pass)
            cout << input.size() << endl;
        if(kase)
            cout << endl;
    }
    return 0;
}

【TopCoder】ZigZag - 2003 TCCC Semifinals 3

Problem Statement

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. 
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. 
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Solution

class ZigZag{
    public:
        int longestZigZag(vector<int> numbers){
            vector<int> dp(numbers.size(), 1);
            vector<int> mark(numbers.size(), 0);
            for(int i = 1; i < numbers.size(); i++){
                for(int j = 0; j < i; j++){
                    int tmp = numbers[i] - numbers[j];
                    if(tmp > 0 && mark[j] <= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = 1;
                    }else if(tmp < 0 && mark[j] >= 0 && dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        mark[i] = -1;
                    }
                }
            }
            sort(dp.begin(), dp.end());

            return dp[numbers.size()-1];
        }
};

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