Code – 第216页

1061. Dating (20)-PAT甲级真题

Sherlock Holmes received a note with some strange strings: “Let’s date! 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”. It took him only a minute to figure out that those strange strings are actually referring to the coded time “Thursday 14:04” — since the first common capital English letter (case sensitive) shared by the first two strings is the 4th capital letter ‘D’, representing the 4th day in a week; the second common character is the 5th capital letter ‘E’, representing the 14th hour (hence the hours from 0 to 23 in a day are represented by the numbers from 0 to 9 and the capital letters from A to N, respectively); and the English letter shared by the last two strings is ‘s’ at the 4th position, representing the 4th minute. Now given two pairs of strings, you are supposed to help Sherlock decode the dating time.

Input Specification:

Each input file contains one test case. Each case gives 4 non-empty strings of no more than 60 characters without white space in 4 lines.

Output Specification:

For each test case, print the decoded time in one line, in the format “DAY HH:MM”, where “DAY” is a 3-character abbreviation for the days in a week — that is, “MON” for Monday, “TUE” for Tuesday, “WED” for Wednesday, “THU” for Thursday, “FRI” for Friday, “SAT” for Saturday, and “SUN” for Sunday. It is guaranteed that the result is unique for each case.

Sample Input:
3485djDkxh4hhGE
2984akDfkkkkggEdsb
s&hgsfdk
d&Hyscvnm
Sample Output:
THU 14:04

题目大意：福尔摩斯接到一张奇怪的字条：“我们约会吧！3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm”。大侦探很快就明白了，前面两字符串中第1对相同的大写英文字母（大小写有区分）是第4个字母D，代表星期四；第2对相同的字符是E，那是第5个英文字母，代表一天里的第14个钟头（于是一天的0点到23点由数字0到9、以及大写字母A到N表示）；后面两字符串第1对相同的英文字母s出现在第4个位置（从0开始计数）上，代表第4分钟。现给定两对字符串，要求解码得到约会的时间~

分析：按照题目所给的方法找到相等的字符后判断即可，如果输出的时间不足2位数要在前面添0，即用%02d输出～

#include <iostream>
#include <cctype>
using namespace std;
int main() {
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    char t[2];
    int pos, i = 0, j = 0;
    while(i < a.length() && i < b.length()) {
        if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {
            t[0] = a[i];
            break;
        }
        i++;
    }
    i = i + 1;
    while (i < a.length() && i < b.length()) {
        if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {
            t[1] = a[i];
            break;
        }
        i++;
    }
    while (j < c.length() && j < d.length()) {
        if (c[j] == d[j] && isalpha(c[j])) {
            pos = j;
            break;
        }
        j++;
    }
    string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "};
    int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;
    cout << week[t[0]-'A'];
    printf("%02d:%02d", m, pos);
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

string a, b, c, d;

cin >> a >> b >> c >> d;

char t[2];

int pos, i = 0, j = 0;

while(i < a.length() && i < b.length()) {

if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {

t[0] = a[i];

break;

}

i++;

}

i = i + 1;

while (i < a.length() && i < b.length()) {

if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {

t[1] = a[i];

break;

}

i++;

}

while (j < c.length() && j < d.length()) {

if (c[j] == d[j] && isalpha(c[j])) {

pos = j;

break;

}

j++;

}

string week[7] = {"MON ", "TUE ", "WED ", "THU ", "FRI ", "SAT ", "SUN "};

int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;

cout << week[t[0]-'A'];

printf("%02d:%02d", m, pos);

return 0;

}

1070. Mooncake (25)-PAT甲级真题

Mooncake is a Chinese bakery product traditionally eaten during the Mid-Autumn Festival. Many types of fillings and crusts can be found in traditional mooncakes according to the regions culture. Now given the inventory amounts and the prices of all kinds of the mooncakes, together with the maximum total demand of the market, you are supposed to tell the maximum profit that can be made.
Note: partial inventory storage can be taken. The sample shows the following situation: given three kinds of mooncakes with inventory amounts being 180, 150, and 100 thousand tons, and the prices being 7.5, 7.2, and 4.5 billion yuans. If the market demand can be at most 200 thousand tons, the best we can do is to sell 150 thousand tons of the second kind of mooncake, and 50 thousand tons of the third kind. Hence the total profit is 7.2 + 4.5/2 = 9.45 (billion yuans).

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (<=1000), the number of different kinds of mooncakes, and D (<=500 thousand tons), the maximum total demand of the market. Then the second line gives the positive inventory amounts (in thousand tons), and the third line gives the positive prices (in billion yuans) of N kinds of mooncakes. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the maximum profit (in billion yuans) in one line, accurate up to 2 decimal places.

Sample Input:
3 200
180 150 100
7.5 7.2 4.5
Sample Output:
9.45

题目大意：N表示月饼种类，D表示月饼的市场最大需求量，给出每种月饼的数量和总价，问根据市场最大需求量，这些月饼的最大销售利润为多少～

分析：首先根据月饼的总价和数量计算出每一种月饼的单价，然后将月饼数组按照单价从大到小排序，根据需求量need的大小，从单价最大的月饼开始售卖，将销售掉这种月饼的价格累加到result中，最后输出result即可～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct mooncake{
    float num, price, unit;
};
int cmp(mooncake a, mooncake b) {
    return a.unit > b.unit;
}
int main() {
    int n, need;
    cin >> n >> need;
    vector<mooncake> a(n);
    for (int i = 0; i < n; i++) scanf("%f", &a[i].num);
    for (int i = 0; i < n; i++) scanf("%f", &a[i].price);
    for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].num;
    sort(a.begin(), a.end(), cmp);
    float result = 0.0;
    for (int i = 0; i < n; i++) {
        if (a[i].num <= need) {
            result = result + a[i].price;
        } else {
            result = result + a[i].unit * need;
            break;
        }
        need = need - a[i].num;
    }
    printf("%.2f",result);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

struct mooncake{

float num, price, unit;

};

int cmp(mooncake a, mooncake b) {

return a.unit > b.unit;

}

int main() {

int n, need;

cin >> n >> need;

vector<mooncake> a(n);

for (int i = 0; i < n; i++) scanf("%f", &a[i].num);

for (int i = 0; i < n; i++) scanf("%f", &a[i].price);

for (int i = 0; i < n; i++) a[i].unit = a[i].price / a[i].num;

sort(a.begin(), a.end(), cmp);

float result = 0.0;

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

if (a[i].num <= need) {

result = result + a[i].price;

} else {

result = result + a[i].unit * need;

break;

}

need = need - a[i].num;

}

printf("%.2f",result);

return 0;

}

1074. Reversing Linked List (25)-PAT甲级真题

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

分析：把地址为temp的数的数值存入data[temp]中，把temp的下一个结点的地址存入next[temp]中。
注意：不一定所有的输入的结点都是有用的，加个计数器sum

#include <iostream>
using namespace std;
int main() {
    int first, k, n, sum = 0;
    cin >> first >> n >> k;
    int temp, data[100005], next[100005], list[100005], result[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < sum; i++) result[i] = list[i];
    for (int i = 0; i < (sum - sum % k); i++)
        result[i] = list[i / k * k + k - 1 - i % k];
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int first, k, n, sum = 0;

cin >> first >> n >> k;

int temp, data[100005], next[100005], list[100005], result[100005];

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

cin >> temp;

cin >> data[temp] >> next[temp];

}

while (first != -1) {

list[sum++] = first;

first = next[first];

}

for (int i = 0; i < sum; i++) result[i] = list[i];

for (int i = 0; i < (sum - sum % k); i++)

result[i] = list[i / k * k + k - 1 - i % k];

for (int i = 0; i < sum - 1; i++)

printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);

printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);

return 0;

}

1085. Perfect Sequence (25)-PAT甲级真题

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output:
8

题目大意：给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。输入第一行给出两个正整数N（输入正数的个数）和p（给定的参数），第二行给出N个正整数。在一行中输出最多可以选择多少个数可以用它们组成一个完美数列

分析：简单题。首先将数列从小到大排序，设当前结果为result = 0，当前最长长度为temp = 0；从i = 0～n，j从i + result到n，【因为是为了找最大的result，所以下一次j只要从i的result个后面开始找就行了】每次计算temp若大于result则更新result，最后输出result的值～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    long long p;
    scanf("%d%lld", &n, &p);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    int result = 0, temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + result; j < n; j++) {
            if (v[j] <= v[i] * p) {
                temp = j - i + 1;
                if (temp > result)
                    result = temp;
            } else {
                break;
            }
        }
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

int n;

long long p;

scanf("%d%lld", &n, &p);

vector<int> v(n);

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

cin >> v[i];

sort(v.begin(), v.end());

int result = 0, temp = 0;

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

for (int j = i + result; j < n; j++) {

if (v[j] <= v[i] * p) {

temp = j - i + 1;

if (temp > result)

result = temp;

} else {

break;

}

cout << result;

return 0;

}

【solution 2】如果熟练使用upper_bound()，可以使用以下解法解决问题（代码由Github用户littlesevenmo提供，在此表达感谢）：

#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int main() {
    int n;
    long long p;
    cin >> n >> p;
    if (n == 0) {
        cout << n;
        return 0;
    }
    long long int *a = new long long int[n];
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    int result = 1;
    for (int i = 0; i < n; i++) {
        result = max((int)(upper_bound(a, a+n, a[i] * p) - (a+i)), result);
    }
    cout << result;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <stdlib.h>

using namespace std;

int main() {

int n;

long long p;

cin >> n >> p;

if (n == 0) {

cout << n;

return 0;

}

long long int *a = new long long int[n];

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

cin >> a[i];

sort(a, a + n);

int result = 1;

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

result = max((int)(upper_bound(a, a+n, a[i] * p) - (a+i)), result);

}

cout << result;

return 0;

}

1088. Rational Arithmetic (20)-PAT甲级真题

For two rational numbers, your task is to implement the basic arithmetics, that is, to calculate their sum, difference, product and quotient.

Input Specification:

Each input file contains one test case, which gives in one line the two rational numbers in the format “a1/b1 a2/b2”. The numerators and the denominators are all in the range of long int. If there is a negative sign, it must appear only in front of the numerator. The denominators are guaranteed to be non-zero numbers.

Output Specification:

For each test case, print in 4 lines the sum, difference, product and quotient of the two rational numbers, respectively. The format of each line is “number1 operator number2 = result”. Notice that all the rational numbers must be in their simplest form “k a/b”, where k is the integer part, and a/b is the simplest fraction part. If the number is negative, it must be included in a pair of parentheses. If the denominator in the division is zero, output “Inf” as the result. It is guaranteed that all the output integers are in the range of long int.

Sample Input 1:
2/3 -4/2
Sample Output 1:
2/3 + (-2) = (-1 1/3)
2/3 – (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)
Sample Input 2:
5/3 0/6
Sample Output 2:
1 2/3 + 0 = 1 2/3
1 2/3 – 0 = 1 2/3
1 2/3 * 0 = 0
1 2/3 / 0 = Inf

题目大意：输入在一行中按照“a1/b1 a2/b2”的格式给出两个分数形式的有理数，其中分子和分母全是整型范围内的整数，负号只可能出现在分子前，分母不为0，分别在4行中按照“有理数1 运算符有理数2 = 结果”的格式顺序输出2个有理数的和、差、积、商。注意输出的每个有理数必须是该有理数的最简形式“k a/b”，其中k是整数部分，a/b是最简分数部分；若为负数，则须加括号；若除法分母为0，则输出“Inf”～题目保证正确的输出中没有超过整型范围的整数～

分析：func(m, n)的作用是对m/n的分数进行化简，gcd(t1, t2)的作用是计算t1和t2的最大公约数～在func函数中，先看m和n里面是否有0（即m*n是否等于0），如果分母n=0，输出Inf，如果分子m=0，输出”0″～flag表示m和n是否异号，flag=true表示后面要添加负号”(-“和括号”)”，再将m和n都转为abs(m)和abs(n)，即取他们的正数部分方便计算～x = m/n为m和n的可提取的整数部分，先根据flag的结果判断是否要在前面追加”(-“，然后根据x是否等于0判断要不要输出这个整数位，接着根据m%n是否等于0的结果判断后面还有没有小分数，如果m能被n整除，表示没有后面的小分数，那么就根据flag的结果判断要不要加”)”，然后直接return～如果有整数位，且后面有小分数，则要先输出一个空格，接着处理剩下的小分数，先把m分子减去已经提取出的整数部分，然后求m和n的最大公约数t，让m和n都除以t进行化简～最后输出“m/n”，如果flag==true还要在末尾输出”)”

注意：判断m和n是否异号千万不要写成判断m*n是否小于0，因为m*n的结果可能超过了long long int的长度，导致溢出大于0，如果这样写的话会有一个测试点无法通过～（(⊙o⊙)嗯为了这一个测试点找bug找到凌晨两三点的就是我…我好菜啊.jpg）

#include <iostream>
#include <cmath>
using namespace std;
long long a, b, c, d;
long long gcd(long long t1, long long t2) {
    return t2 == 0 ? t1 : gcd(t2, t1 % t2);
}
void func(long long m, long long n) {
    if (m * n == 0) {
        printf("%s", n == 0 ? "Inf" : "0");
        return ;
    }
    bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));
    m = abs(m); n = abs(n);
    long long x = m / n;
    printf("%s", flag ? "(-" : "");
    if (x != 0) printf("%lld", x);
    if (m % n == 0) {
        if(flag) printf(")");
        return ;
    }
    if (x != 0) printf(" ");
    m = m - x * n;
    long long t = gcd(m, n);
    m = m / t; n = n / t;
    printf("%lld/%lld%s", m, n, flag ? ")" : "");
}
int main() {
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
    func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");
    func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");
    func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");
    func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

long long a, b, c, d;

long long gcd(long long t1, long long t2) {

return t2 == 0 ? t1 : gcd(t2, t1 % t2);

}

void func(long long m, long long n) {

if (m * n == 0) {

printf("%s", n == 0 ? "Inf" : "0");

return ;

}

bool flag = ((m < 0 && n > 0) || (m > 0 && n < 0));

m = abs(m); n = abs(n);

long long x = m / n;

printf("%s", flag ? "(-" : "");

if (x != 0) printf("%lld", x);

if (m % n == 0) {

if(flag) printf(")");

return ;

}

if (x != 0) printf(" ");

m = m - x * n;

long long t = gcd(m, n);

m = m / t; n = n / t;

printf("%lld/%lld%s", m, n, flag ? ")" : "");

}

int main() {

scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);

func(a, b); printf(" + "); func(c, d); printf(" = "); func(a * d + b * c, b * d); printf("\n");

func(a, b); printf(" - "); func(c, d); printf(" = "); func(a * d - b * c, b * d); printf("\n");

func(a, b); printf(" * "); func(c, d); printf(" = "); func(a * c, b * d); printf("\n");

func(a, b); printf(" / "); func(c, d); printf(" = "); func(a * d, b * c);

return 0;

}

1089. Insert or Merge (25)-PAT甲级真题

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.
Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

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

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

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

Sample Output 2:

Merge Sort
1 2 3 8 4 5 7 9 0 6

题目大意：现给定原始序列和由某排序算法产生的中间序列，请你判断该算法是插入算法还是归并算法。首先在第1行中输出“Insertion Sort”表示插入排序、或“Merge Sort”表示归并排序；然后在第2行中输出用该排序算法再迭代一轮的结果序列

分析：先将i指向中间序列中满足从左到右是从小到大顺序的最后一个下标，再将j指向从i+1开始，第一个不满足a[j] == b[j]的下标，如果j顺利到达了下标n，说明是插入排序，再下一次的序列是sort(a, a+i+2);否则说明是归并排序。归并排序就别考虑中间序列了，直接对原来的序列进行模拟归并时候的归并过程，i从0到n/k，每次一段段得sort(a + i * k, a + (i + 1) * k);最后别忘记还有最后剩余部分的sort(a + n / k * k, a + n);这样是一次归并的过程。直到有一次发现a的顺序和b的顺序相同，则再归并一次，然后退出循环～

注意：一开始第三个测试点一直不过，天真的我以为可以模拟一遍归并的过程然后在过程中判断下一步是什么。。然而真正的归并算法它是一个递归过程。。也就是先排左边一半，把左边的完全排列成正确的顺序之后，再排右边一半的。。而不是左右两边一起排列的。。后来改了自己的归并部分判断的代码就过了。。。｡◕‿◕｡

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, a[100], b[100], i, j;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);
    for (j = i + 1; a[j] == b[j] && j < n; j++);
    if (j == n) {
        cout << "Insertion Sort" << endl;
        sort(a, a + i + 2);
    } else {
        cout << "Merge Sort" << endl;
        int k = 1, flag = 1;
        while(flag) {
            flag = 0;
            for (i = 0; i < n; i++) {
                if (a[i] != b[i])
                    flag = 1;
            }
            k = k * 2;
            for (i = 0; i < n / k; i++)
                sort(a + i * k, a + (i + 1) * k);
            sort(a + n / k * k, a + n);
        }
    }
    for (j = 0; j < n; j++) {
        if (j != 0) printf(" ");
        printf("%d", a[j]);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, a[100], b[100], i, j;

cin >> n;

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

cin >> a[i];

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

cin >> b[i];

for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++);

for (j = i + 1; a[j] == b[j] && j < n; j++);

if (j == n) {

cout << "Insertion Sort" << endl;

sort(a, a + i + 2);

} else {

cout << "Merge Sort" << endl;

int k = 1, flag = 1;

while(flag) {

flag = 0;

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

if (a[i] != b[i])

flag = 1;

}

k = k * 2;

for (i = 0; i < n / k; i++)

sort(a + i * k, a + (i + 1) * k);

sort(a + n / k * k, a + n);

}

for (j = 0; j < n; j++) {

if (j != 0) printf(" ");

printf("%d", a[j]);

}

return 0;

}