【UVa】12325 - Zombie's Treasure Chest

Problem here

Problem

Some brave warriors come to a lost village. They are very lucky and find a lot of treasures and a big
treasure chest, but with angry zombies.
The warriors are so brave that they decide to defeat the zombies and then bring all the treasures
back. A brutal long-drawn-out battle lasts from morning to night and the warriors find the zombies
are undead and invincible.
Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the
treasures by the treasure chest due to the limitation of the capacity of the chest. Indeed, there are only
two types of treasures: emerald and sapphire. All of the emeralds are equal in size and value, and with
infinite quantities. So are sapphires.
Being the priest of the warriors with the magic artifact: computer, and given the size of the chest,
the value and size of each types of gem, you should compute the maximum value of treasures our
warriors could bring back.

INPUT

There are multiple test cases. The number of test cases T (T ≤ 200) is given in the first line of the
input file. For each test case, there is only one line containing five integers N, S1, V1, S2, V2, denoting
the size of the treasure chest is N and the size and value of an emerald is S1 and V1, size and value of
a sapphire is S2, V2. All integers are positive and fit in 32-bit signed integers.

OUTPUT

For each test case, output a single line containing the case number and the maximum total value of all
items that the warriors can carry with the chest.

Sample

input

2
100 1 1 2 2
100 34 34 5 3

output

Case #1: 100
Case #2: 86

Solution

整個可裝物品數 ＝ i + (N-i*S1)/S2 //設有i個寶物1 ，有 (N-i*S1)/S2個寶物2

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

int main(){
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        int N, s1, s2, v1, v2;
        cin >> N >> s1 >> v1 >> s2 >> v2;
        long var = 0;

        for(long i = 0; i <= 99999; i++){
            if(s1*i <= N)
                var = max(var , (v1*i + (N-i*s1)/s2*v2 ) );
            if(s2*i <= N)
                var = max(var , (v2*i + (N-i*s2)/s1*v1 ) );
        }

        cout << "Case #" << t << ": ";
        cout << var << endl;
    }
    return 0;
}

【UVa】524 - Prime Ring Problem

Problem here

Problem

A ring is composed of n (even number) circles as shown in diagram.
Put natural numbers 1, 2, . . . , n into each circle separately, and the
sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.

INPUT

n (0 < n ≤ 16

OUTPUT

The output format is shown as sample below. Each row represents a series of circle numbers in the
ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above
requirements.
You are to write a program that completes above process

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

Solution

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

int A[20];
bool vis[20];
int n;
int testcase = 1;

bool is_prime(int n){
    for(int i = 2; i <= sqrt(n); i++)
        if(n % i == 0)
            return false;
        return true;

}

void slove(int cur){
    if(cur == n && is_prime(A[n-1] + A[n])){
        for(int i = 0; i < n; i++){
            if(i == 0)  
                cout << A[i];
            else
                cout << " " << A[i];
        }
        cout << endl;
    }else{
        for(int i = 2; i <= n; i++){
            if(!vis[i] && is_prime(i+A[cur-1])){
                A[cur] = i;
                vis[i] = true;
                slove(cur+1);
                vis[i] = false;
            }
        }
    }
}

int main(){
    while(cin >> n){
        if(testcase > 1)
            cout << endl;
        A[0] = A[n] = 1;
        cout << "Case " << testcase++ << ":" << endl;
        slove(1);
    }

    return 0;
}