10093 - An Easy Problem!

Have you heard the fact “The base of every normal number system is 10” ? Of course, I am not talking about number systems like Stern Brockot Number System. This problem has nothing to do with this fact but may have some similarity.  

You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N. The range for N is 2<=N<=62 and the digit symbols for 62 based number is (0..9 and A..Z and a..z). Similarly, the digit symbols for 61 based number system is (0..9 and A..Z and a..y) and so on.  

Input

Each line in the input file will contain an integer (as defined in mathematics) number of any integer base (2..62). You will have to determine what is the smallest possible base of that number for the given conditions. No invalid number will be given as input.

Output

If number with such condition is not possible output the line “such number is impossible!” For each line of input there will be only a single line of output. The output will always be in decimal number system.

Sample Input

3
5
A

Sample Output

4
6
11

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1034

---

這題可能需要知道一個定理會簡單得多，若一個n進位的數可以被n - 1整除，則它每個位數的總和也會被n - 1整除。題目要求找到最小的n，所以我們可以先找到最小的n - 1，這樣就可以找到最小的n。因為n - 1最小要和所有位數裡最大的數相等，所以可以把所有位數裡面最大的數當作找n - 1的起點，接著把61(因為題目說進位最大只到62進位)當作終點，只要一有可以整除所有位數總和的數字出現，它就是最小的n - 1。

c++程式碼:

#include <iostream>
using namespace std;

int main() {
    string input;

    while (cin >> input) {
        int digitSum = 0;
        int ans = -1;
        int maxDigit = -1;

        for (int i=0; i<input.length(); i++){
            int thisDigit;

            if (input[i] >= 'A' && input[i] <= 'Z')
                thisDigit = input[i] - 'A' + 10;
            else if (input[i] >= 'a' && input[i] <= 'z')
                thisDigit = input[i] - 'a' + 36;
            else if (input[i] >= '0' && input[i] <= '9')
                thisDigit = input[i] - '0';
            else
                continue;
            if (thisDigit > maxDigit)
                maxDigit = thisDigit;
            digitSum += thisDigit;
        }
        if (!maxDigit)
            maxDigit = 1;
        for (int i=maxDigit; i<=61; i++) {
            if (!(digitSum % i)) {
                ans = i + 1;
                break;
            }
        }
        if (ans == -1)
            cout << "such number is impossible!\n";
        else
            cout << ans << endl;
    }

    return 0;
}

10082 - WERTYU

A common typing error is to place the hands on the keyboard one row to the right of the correct position. So "Q" is typed as "W" and "J" is typed as "K" and so on. You are to decode a message typed in this manner.
Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input. You are to replace each letter or punction symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input

O S, GOMR YPFSU/

Output for Sample Input

I AM FINE TODAY.

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1023

---

這題就是把每個input的鍵對應到左邊的鍵就對了。

以下是c++程式碼:

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

int main() {
    map<char, char> table;
    string input;

    table['1'] = '`';
    table['2'] = '1';
    table['3'] = '2';
    table['4'] = '3';
    table['5'] = '4';
    table['6'] = '5';
    table['7'] = '6';
    table['8'] = '7';
    table['9'] = '8';
    table['0'] = '9';
    table['-'] = '0';
    table['='] = '-';
    table['W'] = 'Q';
    table['E'] = 'W';
    table['R'] = 'E';
    table['T'] = 'R';
    table['Y'] = 'T';
    table['U'] = 'Y';
    table['I'] = 'U';
    table['O'] = 'I';
    table['P'] = 'O';
    table['['] = 'P';
    table[']'] = '[';
    table['\\'] = ']';
    table['S'] = 'A';
    table['D'] = 'S';
    table['F'] = 'D';
    table['G'] = 'F';
    table['H'] = 'G';
    table['J'] = 'H';
    table['K'] = 'J';
    table['L'] = 'K';
    table[';'] = 'L';
    table['\''] = ';';
    table['X'] = 'Z';
    table['C'] = 'X';
    table['V'] = 'C';
    table['B'] = 'V';
    table['N'] = 'B';
    table['M'] = 'N';
    table[','] = 'M';
    table['.'] = ',';
    table['/'] = '.';
    table[' '] = ' ';
    while (getline(cin, input)) {
        for (int i=0; i<input.length(); i++)
            cout << table[input[i]];
        cout << endl;
    }

    return 0;
}

10071 - Back to High School Physics

A particle has initial velocity and constant acceleration. If its velocity after certain time is v then what will its displacement be in twice of that time?

Input

The input will contain two integers in each line. Each line makes one set of input. These two integers denote the value of v (-100 <= v <= 100) and t(0<=t<= 200) ( t means at the time the particle gains that velocity) 

Output

For each line of input print a single integer in one line denoting the displacement in double of that time.

Sample Input

0 0
5 12

Sample Output

0
120

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1012

---

這題是個物理題(話說我高中時候物理超級爛，但是竟然還記得一點點力學的公式XD，若推導有不對還請多多指教)。首先題目會告訴你在某個時間點(t)下的速度(v)，要你算出兩倍的時間(2 * t)的位移是多少。

要算出位移，需要套用到以下公式:

x是位移, v0是初速, t是時間, a是加速度

x = v0 * t + (1 / 2) * a * t ^ 2

現在我們將題目要的結果v和2 * t(因為要2倍時間)帶到公式裡並且算出位移x，則:

x = v0 * (2 * t) + (1 / 2) * a * (2 * t) ^ 2

整理一下

x = 2 * v0 * t + (1 / 2) * a * 4 * t ^ 2

我們需要加速度a，所以用以下公式算出a:

v = v0 + a * t

a = (v - v0) / t

將a代回我們的位移公式:

x = 2 * v0 * t + (1 / 2) * ((v - v0) / t) * 4 * t ^ 2

最後可以把此算式整理成以下算式:

x = 2 * v * t

這就是神奇的最終公式啦~所以只要把所有的input代這個公式就可以求解嚕。

以下是c++程式碼:

#include <iostream>
using namespace std;

int main() {
    int v, t;

    while (cin >> v >> t)
        cout << 2 * v * t << endl;

    return 0;
}

10062 - Tell me the frequencies!

Given a line of text you will have to find out the frequencies of the ASCII characters present in it. The given lines will contain none of the first 32 or last 128 ASCII characters. Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration.

Input

Several lines of text are given as input. Each line of text is considered as a single input. Maximum length of each line is 1000.

Output

Print the ASCII value of the ASCII characters which are present and their frequency according to the given format below. A blank line should separate each set of output. Print the ASCII characters in the ascending order of their frequencies. If two characters are present the same time print the information of the ASCII character with higher ASCII value first. Input is terminated by end of file.

Sample Input:

AAABBC
122333

Sample Output:

67 1
66 2
65 3

49 1
50 2
51 3

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1003

---

這題我不是採用暴力法(雖然程式碼比較簡潔)，我是採用排序的方式，作法和 http://samchien.blogspot.tw/2013/04/10008-whats-cryptanalysis.html 十分類似，所以以下就不贅述。

比較需要注意的地方是input資料的ascii code範圍會包含空白，所以會需要用到能讀取一整行input的方式。

以下是c++程式碼:

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

class Freq {
    public:
        int ascii, times;
};

bool freqCmp(const Freq* theFreq, const Freq* otherFreq) {
    if (theFreq->times < otherFreq->times)
        return true;
    else if (theFreq->times == otherFreq->times)
        return theFreq->ascii > otherFreq->ascii;
    else
        return false;
}

int main() {
    string input;
    bool firstTime = true;

    while (getline(cin, input)) {
        map<int, int> table;
        vector<int> keyList;
        vector<Freq*> freqList;

        for (int i=0; i<input.length(); i++) {
            if (!table[input[i]])
                keyList.push_back(input[i]);
            table[input[i]]++;
        }
        for (int i=0; i<keyList.size(); i++) {
            Freq* f = new Freq();

            f->ascii = keyList[i];
            f->times = table[keyList[i]];
            freqList.push_back(f);
        }
        sort(freqList.begin(), freqList.end(), freqCmp);
        if (firstTime)
            firstTime = false;
        else
            cout << endl;
        for (int i=0; i<freqList.size(); i++)
            cout << freqList[i]->ascii << " " << freqList[i]->times << endl;
        for (int i=0; i<freqList.size(); i++)
            delete freqList[i];
    }

    return 0;
}

10057 - A mid-summer night's dream.

This is year 2200AD. Science has progressed a lot in two hundred years. Two hundred years is mentioned here because this problem is being sent back to 2000AD with the help of time machine. Now it is possible to establish direct connection between man and computer CPU. People can watch other people’s dream on 3D displayer (That is the monitor today) as if they were watching a movie. One problem in this century is that people have become so dependent on computers that their analytical ability is approaching zero. Computers can now read problems and solve them automatically. But they can solve only difficult problems. There are no easy problems now. Our chief scientist is in great trouble as he has forgotten the number of his combination lock. For security reasons computers today cannot solve combination lock related problems. In a mid-summer night the scientist has a dream where he sees a lot of unsigned integer numbers flying around. He records them with the help of his computer, Then he has a clue that if the numbers are (X1, X2,   …  , Xn) he will have to find an integer number A (This A is the combination lock code) such that

             

             (|X1-A| + |X2-A| + … … + |Xn-A|) is minimum.

Input

Input will contain several blocks. Each block will start with a number n (0<n<=1000000) indicating how many numbers he saw in the dream. Next there will be n numbers. All the numbers will be less than 65536. The input will be terminated by end of file.

Output

For each set of input there will be one line of output. That line will contain the minimum possible value for A. Next it will contain how many numbers are there in the input that satisfy the property of A (The summation of absolute deviation from A is minimum). And finally you have to print how many possible different integer values are there for A (these values need not be present in the input). These numbers will be separated by single space.

Sample Input:

2
10
10
4
1
2
2
4

Sample Output:

10 2 1
2 2 1

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=998

---

這一題也是和中位數有相關的題目。題目是說有一堆數字X1 X2 ... Xn，可以找到數字A使得(|X1-A| + |X2-A| + … … + |Xn-A|)的值是最小的，A這個數字其實就是中位數。

至於題目的output是要你輸出三個結果，第一個是最小值的A，第二個是在全部的數字中幾個數字符合A的性質，第三個是要你算出有幾個不同符合A性質的數字，這些數字包含沒有出現在這堆數字裡面的。

首先，先將題目給的所有數字做排序，若全部數字的數量是奇數，則第一個答案就是中位數，若全部數字的數量是偶數，則第一個答案就是中間兩個數中的第一個數字(因為第一個答案要求的是最小值的A)。接下來要求出第二個答案，若全部數字的數量是奇數，則第二個答案就是所有和中位數相等的數字，若全部數字的數量是偶數，則第二個答案就是所有和中間兩個數相等的數字。最後是第三個答案，若全部數字的數量是奇數，則第三個答案就是1(因為只會有那一個，沒有其他不一樣數字的可能)，若全部數字的數量是偶數，則第三個答案就是中間兩數相減加1，因為除了中間兩個數以外，兩數中間每個不同的值都包含在內。

以下是c++程式碼:

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

int main() {
    int n;

    while (cin >> n) {
        vector<int> nums;
        int mid;
        int countMid = 0;
        int diffValNum;

        while (n--) {
            int theNum;

            cin >> theNum;
            nums.push_back(theNum);
        }
        sort(nums.begin(), nums.end());
        mid = (nums.size() - 1) / 2;
        if (nums.size() % 2) {
            for (int i=mid; i>=0 && nums[i]==nums[mid]; i--)
                countMid++;
            for (int i=mid+1; i<nums.size() && nums[i]==nums[mid]; i++)
                countMid++;
            diffValNum = 1;
        }
        else {
            for (int i=mid; i>=0 && nums[i]==nums[mid]; i--)
                countMid++;
            for (int i=mid+1; i<nums.size() && nums[i]==nums[mid+1]; i++)
                countMid++;
            diffValNum = nums[mid+1] - nums[mid] + 1;
        }
        cout << nums[mid] << " " << countMid << " " << diffValNum << endl;
    }

    return 0;
}

10056 - What is the Probability ?

Probability has always been an integrated part of computer algorithms. Where the deterministic algorithms have failed to solve a problem in short time, probabilistic algorithms have come to the rescue. In this problem we are not dealing with any probabilistic algorithm. We will just try to determine the winning probability of a certain player.

A game is played by throwing a dice like thing (it should not be assumed that it has six sides like an ordinary dice). If a certain event occurs when a player throws the dice (such as getting a 3, getting green side on top or whatever) he is declared the winner. There can be N such player. So the first player will throw the dice, then the second and at last the N th player and again the first player and so on. When a player gets the desired event he or she is declared winner and playing stops. You will have to determine the winning probability of one (The I th) of these players.

Input

Input will contain an integer S (S<=1000) at first, which indicates how many sets of inputs are there. The next S lines will contain S sets of inputs. Each line contain an integer N (N<=1000) which denotes the number players, a floating point number p which indicates the probability of the happening of a successful event in a single throw (If success means getting 3 then p is the probability of getting 3 in a single throw. For a normal dice the probability of getting 3 is 1/6), and I (I<=N) the serial of the player whose winning probability is to be determined (Serial no varies from 1 to N). You can assume that no invalid probability (p) value will be given as input.

Output

For each set of input, output in a single line the probability of the I th player to win. The output floating point number will always have four digits after the decimal point as shown in the sample output.

Sample Input:

2
2 0.166666 1
2 0.166666 2

Sample Output:

0.5455
0.4545

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=997

---

這題需要用到一點數學。首先，我們先來了解一下題目的意思，這就是一個有關機率的遊戲，題目會告訴你有幾個玩家，勝率多少，然後要你求出第x個玩家獲勝的機率。那玩家play的順序是從第一個到最後一個，若沒有人獲勝，就到第二輪，若第二輪還沒有人獲勝，就到第三輪，直到有人獲勝為止。

算法大致上就是先求出第一輪x玩家獲勝的機率，再加上第二輪x玩家獲勝的機率...一直加到無窮大。我們先把算式列出來:

設p = 獲勝的機率, q = 沒有獲勝的機率 = 1 - p, n = 總共的玩家數, x = 第幾個玩家要贏

算式就是這樣:

p * q ^ (x - 1) + p * q ^ (n + x - 1) + p * q ^ (2 * n + x - 1)...

接下來我們可以把 p * q ^ (x - 1)提出來:

( p * q ^ (x - 1) ) * ( 1 + q ^ n + q ^ (2 * n)... )

1 + q ^ n + q ^ (2 * n)...很明顯是個無窮等比級數，所以利用無窮等比級數公式代掉後，會變成以下式子:

( p * q ^ (x - 1) ) * ( 1 / (1 - q ^ n) )

整理一下:

( p * q ^ (x - 1) ) / (1 - q ^ n)

這就是最後的公式，只要把input代進去就可以求出解了。

以下是c++程式碼:

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

int main() {
    int caseNum;

    cin >> caseNum;
    while (caseNum--) {
        int n, x;
        double p, q, ans;

        cin >> n >> p >> x;
        q = 1 - p;
        if (q == 1)
            cout << "0.0000" << endl;
        else {
            ans = pow(q, x - 1) * p / (1 - pow(q, n));
            cout << fixed << setprecision(4) << ans << endl;
        }
    }
    return 0;
}

10055 - Hashmat the Brave Warrior

Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.

Input

The input contains two integer numbers in every line. These two numbers in each line denotes the number of soldiers in Hashmat's army and his opponent's army or vice versa. The input numbers are not greater than 2^32. Input is terminated by End of File.

Output

 For each line of input, print the difference of number of soldiers between Hashmat's army and his opponent's army. Each output should be in seperate line.

Sample Input:

10 12
10 14
100 200

Sample Output:

2
4
100

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=996

---

這一題十分的簡單，就是把兩個數相減取絕對值就對了。唯一有可能出錯的地方就在於資料型態的使用吧，因為題目說輸入的數字不會大於2^32，但是並不代表不會等於XD，所以解題的時候需要用大一點的資料型態。

c++程式碼:

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

int main() {
    long long a, b;

    while (cin >> a >> b)
        cout << abs(a - b) << endl;
    return 0;
}

10041 - Vito's Family

Background 

The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.

Problem 

Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

Input 

The input consists of several test cases. The first line contains the number of test cases.For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < s_i < 30000 ). Note that several relatives could live in the same street number.

Output 

For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers s_i and s_j is d_ij= |s_i-s_j|.

Sample Input 

2
2 2 4 
3 2 4 6

Sample Output 

2
4

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=982

---

題目是說Vito威脅你幫他寫一個程式(programmer好可憐，沒賺到錢還有被威脅QQ)，讓他可以算出他到所有親戚家的最短距離總和。要找出最短的距離總和，必須要先幫Vito找到一個住的地方讓他可以到親戚家的距離總和最短，這個地方其實就是所有街編號的中位數，所以我們只要找到所有街編號的中位數，就可以算出最短距離總和。所以首先第一步，就是要將所有街的編號做排序，再找中位數。若街的數量是奇數，中位數當然就是中間的數字;若街的數量是偶數，則中位數就是中間兩個數相加除以2。但是在這題，偶數的情況可以取中間兩個數前面那個數或後面那個數都可以，並不會影響答案。最後再將所有的街編號和中位數相減取絕對值加總就可以得到答案。

以下是c++程式碼:

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

int main() {
    int n;

    cin >> n;
    while (n--) {
        int r;
        vector<int> streets;
        int mid;
        int sum = 0;

        cin >> r;
        while (r--) {
            int s;

            cin >> s;
            streets.push_back(s);
        }
        sort(streets.begin(), streets.end());
        mid = streets.size() / 2;
        for (int i=0; i<streets.size(); i++)
            sum += abs(streets[mid] - streets[i]);
        cout << sum << endl;
    }
    return 0;
}

10038 - Jolly Jumpers

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the difference between successive elements take on all the values 1 through n-1. For instance,

1 4 2 3

is a jolly jumper, because the absolutes differences are 3, 2, and 1 respectively. The definition implies that any sequence of a single integer is a jolly jumper. You are to write a program to determine whether or not each of a number of sequences is a jolly jumper.

Input

Each line of input contains an integer n <= 3000 followed by n integers representing the sequence.

Output

For each line of input, generate a line of output saying "Jolly" or "Not jolly".

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=979

---

這題的題意是說若有一n項的數列，相鄰兩個數的差的絕對值，包含了所有1~n-1的數字就是jolly，反之就是not jolly。我的作法是將相鄰兩數相減取絕對值後記在table裡，看有哪些數字有出現過，最後在從1跑到n-1檢查table看是不是每個數字都出現了，只要有任何一個數字沒有出現，這就不是jolly，若都出現了，就是jolly。

c++程式碼:

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

int main() {
    int n;

    while (cin >> n) {
        map<int, bool> rem;
        vector<int> seq;
        bool isJolly = true;

        for (int i=0; i<n; i++) {
            int num;

            cin >> num;
            seq.push_back(num);
        }
        for (int i=1; i<seq.size(); i++)
            rem[abs(seq[i]-seq[i-1])] = true;
        for (int i=1; i<n; i++) {
            if (!rem[i]) {
                isJolly = false;
                break;
            }
        }
        if (isJolly)
            cout << "Jolly\n";
        else
            cout << "Not jolly\n";
    }
    return 0;
}

10035 - Primary Arithmetic

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation - in which a 1 is carried from one digit position to be added to the next - to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.

Input

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.

Output

For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

Sample Input

123 456
555 555
123 594
0 0

Sample Output

No carry operation.
3 carry operations.
1 carry operation.

出處: UVa Online Judge - Primary Arithmetic

---

問題敘述

此題會給您很多成對的整數，要求您計算出將兩個整數相加所需要的進位次數。

解題思路

此題可以用取餘數和除法的方式解析出每個位數，並且作加法計算進位次數，除此之外還有要注意的是如果沒有進位或只有一個進位的話輸出operation，其他的輸出operations。

c++ 程式碼

#include <iostream>
using namespace std;

int main() {
    int numA, numB;

    while (true) {
        int carryNum = 0;
        bool isCarry = false;

        cin >> numA >> numB;
        if (!(numA || numB))
            break;
        while (numA || numB) {
            int digitA = numA % 10;
            int digitB = numB % 10;

            if (isCarry) {
                isCarry = false;
                digitA++;
            }
            if (digitA + digitB >= 10) {
                isCarry = true;
                carryNum++;
            }
            numA /= 10;
            numB /= 10;
        }
        if (!carryNum)
            cout << "No carry operation." << endl;
        else if (carryNum == 1)
            cout << "1 carry operation." << endl;
        else
            cout << carryNum << " carry operations." << endl;
    }

    return 0;
}

10019 - Funny Encryption Method

The Problem

History : 
A student from ITESM Campus Monterrey plays with a new encryption method for numbers. These method consist of the following steps:Steps :  Example
1) Read the number N to encrypt M = 265
2) Interpret N as a decimal number X1= 265 (decimal)
3) Convert the decimal interpretation of N to its binary representation X1= 100001001 (binary)
4) Let b1 be equal to the number of 1’s in this binary representation B1= 3
5) Interpret N as a Hexadecimal number X2 = 265 (hexadecimal)
6) Convert the hexadecimal interpretation of N to its binary representation X2 = 1001100101
7) Let b2 be equal to the number of 1’s in the last binary representation B2 = 5
8) The encryption is the result of  M xor (b1*b2) M xor (3*5) = 262
This student failed Computational Organization, that’s why this student asked the judges of ITESM Campus Monterrey internal ACM programming Contest to ask for the numbers of 1’s bits of this two representations so that he can continue playing.
Task :
You have to write a program that read a Number and give as output the number b1 and b2

The Input

The first line will contain a number N which is the number of cases that you have to process. Each of the following N Lines ( 0<N<=1000) will contain the number M (0<M<=9999, in decimal representation)  which is the number the student wants to encrypt.

The Output

You will have to output N lines, each containing the number b1 and b2 in that order, separated by one space  corresponding to that lines number to crypt

Sample Input

3
265
111
1234

Sample Output

3 5 
6 3 
5 5

出處: UVa Online Judge - Funny Encryption Method

---

問題敘述

此題 input 的第一行會表示下面要輸入幾個整數，接著要將輸入的每個整數做兩件事情。第一: 先將它解讀成十進位並且轉換成二進位，輸出二進位中 1 的數量。第二: 將它解讀成十六進位並且轉換成二進位，輸出二進位中 1 的數量。輸出的兩個數字必須要用空白隔開。

解題思路

這題和 948 - Fibonaccimal Base (Chinese version) 一樣也是個進位轉換的題目，先將輸入的數字轉換成二進位，並且輸出二進位中 1 的數量。再將輸入的數字視為十六進位後先將它轉換成十進位再轉換成二進位，且輸出空白以及二進位中 1 的數量。

c++ 程式碼

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

int decToBin(int num, vector<int>& binTable) {
    int count = 0;

    for (int i=16; num; i--) {
        if (num >= binTable[i]) {
            num -= binTable[i];
            count++;
        }
    }
    return count;
}

int main() {
    int n;
    vector<int> binTable;
    vector<int> hexTable;
    int product = 1;

    for (int i=0; i<=16; i++) {
        binTable.push_back(product);
        product *= 2;
    }
    product = 1;
    for (int i=0; i<=3; i++) {
        hexTable.push_back(product);
        product *= 16;
    }
    cin >> n;
    for (int i=0; i<n; i++) {
        int num;
        int dec = 0;

        cin >> num;
        cout << decToBin(num, binTable);
        for (int j=0; num; j++) {
            dec += (num % 10) * hexTable[j];
            num /= 10;
        }
        cout << " " << decToBin(dec, binTable) << endl;
    }

    return 0;
}

10008 - What's Cryptanalysis?

Cryptanalysis is the process of breaking someone else's cryptographic writing. This sometimes involves some kind of statistical analysis of a passage of (encrypted) text. Your task is to write a program which performs a simple analysis of a given text.

Input 

The first line of input contains a single positive decimal integer n. This is the number of lines which follow in the input. The next n lines will contain zero or more characters (possibly including whitespace). This is the text which must be analyzed.

Output 

Each line of output contains a single uppercase letter, followed by a single space, then followed by a positive decimal integer. The integer indicates how many times the corresponding letter appears in the input text. Upper and lower case letters in the input are to be considered the same. No other characters must be counted. The output must be sorted in descending count order; that is, the most frequent letter is on the first output line, and the last line of output indicates the least frequent letter. If two letters have the same frequency, then the letter which comes first in the alphabet must appear first in the output. If a letter does not appear in the text, then that letter must not appear in the output.

Sample Input 

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!!  Is this question easy?

Sample Output 

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

出處: UVa Online Judge - What's Cryptanalysis?

---

問題敘述

此問題會先輸入一個整數 n，表示後面要輸入的文字行數。接著會輸入 n 行文字，您的任務是要在這些文字中統計出所有英文字母出現的次數 (忽略大小寫)，並且依據出現次數由多到少依序輸出，若有出現次數一樣的字母，則將字母順序比較前面的先輸出，例如: "A 2" 和 "H 2"，就要先輸出 "A 2" 然後再輸出 "H 2"。

解題思路

我的想法是先統計出每個字母出現的次數，這用 c++ STL 的 map 可以很容易做到。再把每對字母和次數綁成一個物件並且依據字母順序排好，最後利用穩定排序來依據次數大小做排序。穩定排序可以用重新定義 c++ STL algorithm 裡的 sort 的比較函數來做到，詳細請看程式碼。

c++ 程式碼

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

class EngTimesPair {
    public:
        char eng;
        int times;
};

bool pairCmp(const EngTimesPair* thisPair, const EngTimesPair* otherPair) {
    if (thisPair->times > otherPair->times)
        return true;
    else if (thisPair->times == otherPair->times && thisPair->eng < otherPair->eng)
        return true;
    else
        return false;
}

int main() {
    int n;
    map<char, int> countTable;
    vector<EngTimesPair*> pairList;
    string inputLine;

    (cin >> n).get();
    for (int i=1; i<=n; i++) {
        getline(cin, inputLine);
        for (int j=0; j<inputLine.length(); j++) {
            if ((inputLine[j] >= 'A' && inputLine[j] <= 'Z') ||
                (inputLine[j] >= 'a' && inputLine[j] <= 'z')) {
                if (inputLine[j] >= 'a' && inputLine[j] <= 'z')
                    inputLine[j] -= 'a' - 'A';
                countTable[inputLine[j]]++;
            }
        }
    }
    for (int i='A'; i<'Z'; i++) {
        if (countTable[(char)i]) {
            EngTimesPair* pairs = new EngTimesPair();

            pairs->eng = (char)i;
            pairs->times = countTable[(char)i];
            pairList.push_back(pairs);
        }
    }
    sort(pairList.begin(), pairList.end(), pairCmp);
    for (int i=0; i<pairList.size(); i++)
        cout << pairList[i]->eng << " " << pairList[i]->times << endl;
    for (int i=0; i<pairList.size(); i++)
        delete pairList[i];

    return 0;
}

948 - Fibonaccimal Base

The well known Fibonacci sequence is obtained by starting with 0 and 1 and then adding the two last numbers to get the next one. For example the third number in the sequence is 1 (1=1+0), the forth is 2 (2=1+1), the fifth is 3 (3=2+1) and so on.

i	0	1	2	3	4	5	6	7	8	9
Fib(i)	0	1	1	2	3	5	8	13	21	34

Figure 1 - The first numbers in the Fibonacci sequence

The sequence appears on many things in our life, in nature, and has a great significance. Among other things, do you know that all positive integer numbers can be represented as a sum of numbers in the Fibonacci sequence? More than that, all positive integers can be represented as a sum of a set of Fibonacci numbers, that is, numbers from the sequence, without repetition. For example: 13 can be the sum of the sets {13}, {5,8} or{2,3,8} and 17 is represented by {1,3,13} or {1,3,5,8}. Since all numbers have this property (do you want to try to prove this for yourself?) this set could be a nice way to use as a "base" to represent the number. But, as we have seen, some numbers have more than one set whose sum is the number. How can we solve that? Simple! If we add the constraint that the sets cannot have two consecutive Fibonacci numbers, than we have a unique representation for each number! This restriction is because the sum of any two consecutive Fibonacci numbers is just the following Fibonacci number.

Now that we know all this we can prepare a nice way to represent any positive integer. We will use a binary sequence (just zeros and ones) to do that. For example, 17 = 1 + 3 + 13 (remember that no two consecutive Fibonacci numbers can be used). Let's write a zero for each Fibonacci number that is not used and one for each one that is used, starting at the right. Then, 17 = 100101. See figure 2 for a detailed explanation. In this representation we should not have zeros at the left, this is, we should only write starting with the first one. In order for you to understand better, note that in this scheme, not using two consecutive Fibonacci numbers means that the binary sequence will not have two consecutive ones. When we use this representation for a number we say that we are using the Fibonaccimal base, and we write it like 17 = 100101 (fib).

17 =	1	0	0	1	0	1
13+3+1 =	13	8	5	3	2	1

Figure 2 - Explaining the representation of 17 in Fibonaccimal base

The Problem

Given a set of numbers in decimal base, your task is to write them in the Fibonaccimal base.

Input

The first line of input contains a single number N, representing the quantity of numbers that follow ( 1 ≤ N ≤ 500).

Than follow exactly N lines, each one containing a single positive integer smaller than 100 000 000. These numbers can come in any order.

Output

You should output a single line for each of the N integers in the input, with the format "DEC_BASE = FIB_BASE (fib)". DEC_BASE is the original number in decimal base and FIB_BASE is its representation in Fibonaccimal base. See the sample output for an example.

Example Input

10
1
2
3
4
5
6
7
8
9
10

Example Output

1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)

出處: UVa Online Judge - Fibonaccimal Base

---

問題敘述

這題要求您把十進位數字轉換成費氏數列進位，費氏數列進位的定義請詳見題目描述。

解題思路

因為是將十進位數字轉換成費氏數列進位，費式數字會很常被使用到，所以我會先建立一個費氏數列的表。不過這個表要多大呢? 因為題目說最大的十進位數字是100000000，所以這個表建立到第39項就夠了。接著你可以利用這個表把十進位轉換成費氏數列進位，由大到小去跑這個表，如果有小於或等於這個十進位數字的費氏數字出現，就扣掉它並且印出1，若沒有則印出0，重複動作一直跑到費氏數列第二項為止。

c++程式碼

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

int main() {
    int n;
    vector<int> fibTable;

    fibTable.push_back(0);
    fibTable.push_back(1);
    for (int i=2; i<=39; i++)
        fibTable.push_back(fibTable[i - 1] + fibTable[i - 2]);
    cin >> n;
    for (int i=0; i<n; i++) {
        int num;
        bool start = false;

        cin >> num;
        cout << num << " = ";
        for (int j=39; j>=2; j--) {
            if (num >= fibTable[j]) {
                num -= fibTable[j];
                cout << 1;
                start = true;
            }
            else if (start)
                cout << 0;
        }
        cout << " (fib)" << endl;
    }

    return 0;
}

100 - The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 
  1.    input n

  2.    print n



  3.    if n = 1 then STOP



  4.       if n is odd then   



  5.       else   



  6.    GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

出處: UVa Online Judge - The 3n + 1 problem

---

問題敘述

此問題會輸入好幾組資料，每組資料有2個數字，您要從這對數字的範圍中取出每個數字當數列的起點，並且找出最長的數列長度。數列的規則如下: 假設某一項的內容為n，且n為奇數，則下一項的內容為3 * n + 1，若n為偶數，則下一項的內容為n / 2，一直到n為1數列就結束。輸出時必須照原本輸入的數字印出(順序不能對調)，且還要印出最長的數列長度。

解題思路

沒有什麼特別的思路，就單純照著題目的說明做，比較需要注意的是輸入的範圍可能大的數字會在前面，小的數字在後面，輸出時必須按照輸入的順序輸出，不然會wrong answer。

c++程式碼

#include <iostream>
using namespace std;

int findLength(int num) {
    if (num == 1)
        return 1;
    else {
        if (num % 2)
            return 1 + findLength(3 * num + 1);
        else
            return 1 + findLength(num / 2);
    }
}

int main() {
    int startRange, endRange;

    while (cin >> startRange >> endRange) {
        bool isSwap = false;
        int maxLength = 0;

        if (startRange > endRange) {
            swap(startRange, endRange);
            isSwap = true;
        }
        for (int i=startRange; i<=endRange; i++) {
            int length = findLength(i);

            if (length > maxLength)
                maxLength = length;
        }
        if (isSwap)
            swap(startRange, endRange);
        cout << startRange << " " << endRange << " " << maxLength << endl;
    }

    return 0;
}