Lab0_Welcome

Problem A: Rubik’s Cube

Description

On the original classic Rubik’s Cube, each of the six faces was covered by nine stickers. Each face has its own color, which is determined by the central sticker, since that the positions of all six central stickers will never be changed.

Now, given a face of Rubik’s Cube, try to find out the color of it.

Input

The first line of input is the number of test cases $T$ ($1\leq T \leq 100$)

For each test case, there are three lines, each line will only contain three upper case English letters, separated by a single blank, which shows the color of stickers.

Output

For each test case, print only one upper case English letter to show the color of the face.

Sample Input

1	2
2	A B C
3	D E F
4	A B C
5
6	Z Z Z
7	Z Z Z
8	Z Z Z

Sample Output

1	E
2	Z

Code

1	public class Main {
2	public static void main(String[] args) {
3	java.util.Scanner input = new java.util.Scanner(System.in);
4
5	int n = input.nextInt();
6
7	for(int num = 0; num < n; num++) {
8	int t = 4;
9	while(t-->0) {input.next();}
10	System.out.println(input.next());
11	t = 4;
12	while(t-->0) {input.next();}
13	}
14	input.close();
15	}
16	}
17	/**************************************************************
18	Problem: 1198
19	User:
20	Language: Java
21	Result: Accepted
22	Time:176 ms
23	Memory:17752 kb
24	****************************************************************/

Problem B: Sudoku

Description

For a classic Sudoku, your aim is to fill a 99 grid with digits so that each column, each row, and each of the nine 33 sub grids that compose the grid contain all of the digits from 1 to 9. To make it easier, we guarantee that:
If you choose the order wisely, you can always find such a special blank that its row (column, or 33 sub grid) has already been filled with 8 numbers, so that you can determine its value quite easily. (*Hint may help you understand the definition of special blanks).
However, if you cannot find such special blank till you complete the Sudoku, just point out that the test data is incorrect.

Input

There is a Sudoku presented by ‘1~9’ and ‘ x ’. ‘x’ shows the blank you need to fill.(More details can be found at Sample input.) (Number of ‘x’s is greater than 1.)

Output

If you can always find ‘special blank’ till you complete the sudoku, print your solution of Sudoku as the given format. Otherwise print ‘The test data is incorrect!’(without quotes), instead.

Sample Input

1	6 1 8 \| 5 3 7 \| 4 9 2 \|
2	5 9 4 \| 1 8 2 \| 6 3 7 \|
3	2 3 7 \| 4 6 9 \| 8 5 1 \|
4
5	3 7 2 \| 6 5 1 \| 9 x 8 \|
6	9 4 5 \| 3 x 8 \| 1 x 6 \|
7	1 8 6 \| 2 9 4 \| 5 7 3 \|
8
9	7 6 3 \| 8 4 5 \| 2 1 9 \|
10	8 5 1 \| 9 2 3 \| 7 6 4 \|
11	4 2 9 \| 7 1 6 \| 3 8 5 \|

Sample Output

1	6 1 8 \| 5 3 7 \| 4 9 2 \|
2	5 9 4 \| 1 8 2 \| 6 3 7 \|
3	2 3 7 \| 4 6 9 \| 8 5 1 \|
4
5	3 7 2 \| 6 5 1 \| 9 4 8 \|
6	9 4 5 \| 3 7 8 \| 1 2 6 \|
7	1 8 6 \| 2 9 4 \| 5 7 3 \|
8
9	7 6 3 \| 8 4 5 \| 2 1 9 \|
10	8 5 1 \| 9 2 3 \| 7 6 4 \|
11	4 2 9 \| 7 1 6 \| 3 8 5 \|

HINT

‘Special blank’ means that its row has been filled with 8 numbers, or its column has been filled with 8 numbers, or its 3*3 sub grid has been filled with 8 numbers.

For the sample input, you can choose the order (5,5)，(4,8)，(5,8) to fill the blank. Initially, (5,5) and (4,8) are the ‘special blanks’, since that (5,5)’s 3*3 sub grid and (4,8)’s row have already been filled with eight numbers. When (5,5) is filled, (5,8) becomes a new ‘special blank’. After filling (4,8) and (5,8), the sudoku is completed.

6 1 8 | 5 3 7 | 4 9 2 |
5 9 4 | 1 X X | 6 3 7 |
2 3 7 | 4 6 9 | 8 5 1 |

3 7 2 | 6 5 1 | 9 4 8 |
9 4 5 | 3 X X | 1 2 6 |
1 8 6 | 2 9 4 | 5 7 3 |

7 6 3 | 8 4 5 | 2 1 9 |
8 5 1 | 9 2 3 | 7 6 4 |
4 2 9 | 7 1 6 | 3 8 X |

For this test case, the most lower-right x is the first ‘special blank’ that we seek. However, after filling that, you can not find any other ‘special blank’, so just print ‘The test data is incorrect!’

Code

public class Main {
    private static int[][] sudoku = new int[9][9];
    private static java.util.Stack<Integer[]> coordinates = new java.util.Stack<>();
    private static int[][] coo;
 
    public static void main(String[] args) {
        java.util.Scanner input = new java.util.Scanner(System.in);
        for(int i=0; i<sudoku.length; i++) {
            for(int j=0; j<sudoku[i].length; j++) {
                String s = input.next();
                if(s.equals("|")) {s = input.next();}
                if(s.equals("x")) {
                    Integer[] coordinate = {i, j, position(i, j)};
                    coordinates.push(coordinate);
                    continue;
                }
                sudoku[i][j] = Integer.parseInt(s);
            }
        }
        input.close();
 
        exchange();
        int n = coo.length;
 
        do {
            boolean[][] ways = Judge();
            for(int i=0; i<coo.length; i++) {
                if(ways[i][0] && ways[i][1] && ways[i][2]) {
                    Integer[] t = {coo[i][0], coo[i][1], coo[i][2]};
                    coordinates.push(t);
                }
                else {
                    if(!ways[i][0]) way0(coo[i]);
                    else if(!ways[i][1]) way1(coo[i]);
                    else if(!ways[i][2]) way2(coo[i]);
                }
            }
            exchange();
            if(n==coo.length) {
                System.out.println("The test data is incorrect!");
                return;
            }
            else {
                n = coo.length;
            }
        } while(coo.length != 0);
 
        printSudoku();
    }
 
    private static int position(int x, int y) {
        int a = 0;
        switch(x/3) {
            case 2: a += 3;
            case 1: a += 3;
            case 0:
        }
        return a + y/3;
    }
 
    private static void exchange() {
        coo = new int[coordinates.size()][3];
        for(int i=coo.length-1; i>=0; i--) {
            Integer[] temp = coordinates.pop();
            coo[i][0] = temp[0];
            coo[i][1] = temp[1];
            coo[i][2] = temp[2];
        }
    }
 
    private static boolean[][] Judge() {
        boolean[][] ways = new boolean[coo.length][3];
        for(int i=0; i<coo.length; i++) {
            for (int j = i + 1; j < coo.length; j++) {
                if (coo[i][0] == coo[j][0]) {
                    ways[i][0] = true;
                    ways[j][0] = true;
                }
                if (coo[i][1] == coo[j][1]) {
                    ways[i][1] = true;
                    ways[j][1] = true;
                }
                if (coo[i][2] == coo[j][2]) {
                    ways[i][2] = true;
                    ways[j][2] = true;
                }
            }
        }
        return ways;
    }
 
    private static void way0(int[] coo) {
        int sum = 0;
        for(int i=0; i<sudoku.length; i++) {
            sum += sudoku[coo[0]][i];
        }
        sudoku[coo[0]][coo[1]] = 45 - sum;
    }
 
    private static void way1(int[] coo) {
        int sum = 0;
        for(int i=0; i<sudoku.length; i++) {
            sum += sudoku[i][coo[1]];
        }
        sudoku[coo[0]][coo[1]] = 45 - sum;
    }
 
    private static void way2(int[] coo) {
        int[] startPoint = new int[2];
        switch(coo[2]) {
            case 2: startPoint[1] += 3;
            case 1: startPoint[1] += 3;
            case 0: break;
            case 5: startPoint[1] += 3;
            case 4: startPoint[1] += 3;
            case 3: {
                startPoint[0] = 3;
                break;
            }
            case 8: startPoint[1] += 3;
            case 7: startPoint[1] += 3;
            case 6: startPoint[0] = 6;
        }
        int sum = 0;
        for(int i=startPoint[0]; i<startPoint[0]+3; i++) {
            for(int j=startPoint[1]; j<startPoint[1]+3; j++) {
                sum += sudoku[i][j];
            }
        }
        sudoku[coo[0]][coo[1]] = 45 - sum;
    }
 
    private static void printSudoku() {
        for(int i=0; i<sudoku.length; i++) {
            for(int j=0; j<sudoku[i].length; j++) {
                System.out.print(sudoku[i][j]+" ");
                if(j%3 == 2) {
                    System.out.print('|');
                    if(j==sudoku[i].length-1) System.out.println();
                    else System.out.print(' ');
                }
            }
            if(i%3 == 2) System.out.println();
        }
    }
}
 
/**************************************************************
    Problem: 1202
    User: 
    Language: Java
    Result: Accepted
    Time:188 ms
    Memory:18444 kb
****************************************************************/

Problem C: Majsoul

Description

Mahjong, one of the most famous games in China, has aroused lanran’s interest. However, it is a little bit complex for a new bee and he needs your help: To sort 13 Mahjong tiles in order, so that he can make decision much easier. Here is the rule of sorting Mahjong tiles:

1.Mahjong tiles can be roughly divided into four types, ‘ 萬’ , ‘ 筒’, ’ 条’, ‘ 字’. For the first three types, each type has 9 different numbers(‘1’ to ‘9’), usually noted by ‘1萬’, ‘2萬’,’1条’,’2条’. If you still get puzzled, just imagine that we express the cards in ‘UNO’ by a number and a Chinese character rather than a colour. For the last type, there are only 7 kinds of tiles, ‘ 東’, ‘ 南’, ‘ 西’, ‘北’, ’白’, ’發’,’中’.

2.‘ 萬 ’ noted by ‘Wx’( x is an integer between ‘1’ to ‘9’), for example (W1,W2,…). Similarly, ‘ 筒 ’ by ‘Tx’, ‘ 条 ’ by ‘Yx’. We name those 7 tiles of the last type by ‘E’,’S’,’W’,’N’,’B’,’F’,’Z’ correspondingly.

3.Here is the priority of Mahjong tiles:
Wx>Tx>Yx>E>S>W>N>B>F>Z
For the same type:
W1>W2>W3>W4>W5>W6>W7>W8>W9

Notice that: For each kind of tile, there are totally four duplicate ones.

Input

The first line of input is the number of test cases $T$($1\leq T\leq 200$)
For each test case, there are 13 strings in one line, showing the Mahjong tiles you have.

Output

For each test case, output the ordered Mahjong tiles in one line.

Sample Input

1	2
2	W1 S S N E N E N W E W W S
3	T1 T2 T3 T5 T8 T9 T6 T4 T7 T9 T9 T1 T1

Sample Output

1	W1 E E E S S S W W W N N N
2	T1 T1 T1 T2 T3 T4 T5 T6 T7 T8 T9 T9 T9

Code

#include <iostream>
#include <algorithm>
#include <string.h>
 
using namespace std;
 
 
enum Majhong { Z, F, B, N, W, S, E, Yx, Tx, Wx, Nil };
 
 
Majhong determine(string mah) {
    if (mah.size() == 1) {
        if (mah.compare("Z") == 0) return Z;
        if (mah.compare("F") == 0) return F;
        if (mah.compare("B") == 0) return B;
        if (mah.compare("N") == 0) return N;
        if (mah.compare("W") == 0) return W;
        if (mah.compare("S") == 0) return S;
        if (mah.compare("E") == 0) return E;
    }
    else {
        if (mah[0] == 'Y') return Yx;
        if (mah[0] == 'T') return Tx;
        if (mah[0] == 'W') return Wx;
    }
    return Nil;
}
 
 
bool compare(string a, string b) {
    if (a.size() > b.size()) return true;
    else if (a.size() > b.size()) return false;
    else {
        Majhong aM;
        aM = determine(a);
        Majhong bM;
        bM = determine(b);
        if (aM > bM) return true;
        else if (aM < bM) return false;
        else if (aM == bM && a.size() == 1) return true;
        else {
            if (a[1] <= b[1]) return true;
            else if (a[1] > b[1]) return false;
        }
    }
    return false;
}
 
 
int main() {
    int times;
    cin >> times;
 
    while (times-- > 0) {
        string mahjong[13];
        for (int i = 0; i < 13; i++) {
            cin >> mahjong[i];
        }
        sort(mahjong, mahjong + 13, compare);
 
        for (int i = 0; i < 13; i++) {
            cout << mahjong[i];
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1247
    User: 
    Language: C++
    Result: Accepted
    Time:8 ms
    Memory:1720 kb
****************************************************************/

Problem D: Magical Number

Description

We want to find those Magical Numbers which are symmetry, that is, no matter whether you count it from left to right or right to left, its value will not be changed. For example, 1, 121, 12321, are Magic Numbers, but 123, 321, are not. To be more precise, suppose that we present a number by array a of size n (index starts with 1). It is a Magical Number if and only if $a[i]=a[n-i+1]$ for any$i$, $1\leq i\leq n$. Notice that Magical Number are non-negative integers.

You are asked to count how many Magical Numers are smaller or equal than an integer N.

Input

The first line of input is the number of test cases $T$ ($1\leq T\leq 20$)
For each test case, there is only one integer $N$($0\leq N\leq 1011$)

Notice that: the maximum value of a signed 32-bit integer is 2147483647
‘long long’ in C++, ‘long’ in Java is recommended.

Output

One line for each test case, print the result you get.

Sample Input

1	2
2	1
3	11

Sample Output

1	2
2	11

HINT

Try to construct all the required Magical Numbers rather than check it from 1 to N.

Code

#include <iostream>
#include <math.h>
 
 
using namespace std;
 
 
 
long long len(long long num) {
    long long n = 0;
    while (num != 0) {
        num /= 10;
        n++;
    }
    return n;
}
 
 
long long zonetotal(long long len) {
    if (len == 0) return 0;
    if (len == 1) return 10;
    return 9 * (long long)pow(10, (len - 1) / 2);
}
 
 
long long func(long long len) {
    if (len == 0) return 0;
    if (len == 1) return 10;
    return func(len - 1) + zonetotal(len);
}
 
 
long long piecenumber(long long* piece, long long startp, long long endp) {
    if (startp == 0) {
        if (endp == startp) return piece[startp] - 1;
        else return (piece[startp] - 1) * pow(10, (endp - startp)) + piecenumber(piece, startp + 1, endp);
    }
    if (endp == startp) return piece[startp];
    return piece[startp] * pow(10, (endp - startp)) + piecenumber(piece, startp + 1, endp);
}
 
 
bool isplus(long long* left, long long* right, long long half) {
    for (long long i = half - 1; i >= 0; i--) {
        int a = left[i];
        int b = right[i];
        if (left[i] == right[i]) continue;
        if (left[i] < right[i]) return true;
        return false;
    }
    return true;
}
 
 
long long zonepart(long long num) {
    long long length = len(num);
    if (length == 1) return num + 1;
    long long half = (length + 1) / 2;
    long long left[23] = { 0 };
    long long right[23] = { 0 };
    for (long long i = 0; i < half; i++) {
        right[i] = num % 10;
        num /= 10;
    }
    if (length & 1) {
        for (long long i = 0; i < half - 1; i++) {
            left[half - i - 2] = num % 10;
            num /= 10;
        }
        left[half - 1] = right[half - 1];
    }
    else {
        for (long long i = 0; i < half; i++) {
            left[half - i - 1] = num % 10;
            num /= 10;
        }
    }
 
    int p = piecenumber(left, 0, half - 1);
    bool isss = isplus(left, right, half);
    return piecenumber(left, 0, half - 1) + (isplus(left, right, half) ? 1 : 0);
}
 
 
int main() {
    long long times;
    cin >> times;
    while (times-- > 0) {
        long long num;
        cin >> num;
        if (num / 10 == 0) {
            cout << num + 1 << endl;
            continue;
        }
        int ttt = func(len(num) - 1);
        long long total = zonepart(num) + func(len(num) - 1);
        cout << total << endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1248
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1908 kb
****************************************************************/

Problem E: Down, Right and Up!

Description

How to count an infinity set? For example, all the points in a 2-D space which have positive integer coordinates. lanran finds a way to solve that, ‘Down, Right and Up!’ Let’s see how we count first several points by the above way.

How do we count more?

Hopefully, you have understood this procedure well. Similarly, we can expand the ‘matrix’ to infinitely large, that is, we can count all the points which have positive integer coordinates in a 2-D space.

Given a coordinate, you need to return its index and given an index, you need to return its coordinate.

Input

The first line of input is the number of test cases $T$ ($1\leq T \leq 100,000$)
For each test case, there could only be a coordinate,$(x,y)$ or an index a.($1\leq x,y\leq 109$ , $1\leq a\leq 1018$) You may need ‘long long’ in C++, or ‘long’ in Java to store the value of a.

Output

The coordinate or index that matches each query.

Sample Input

1	2
2	1
3	(1,2)

Sample Output

1	(1,1)
2	4

Code

#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
 
 
using namespace std;
 
 
long long point[2] = { 1, 1 };
long long p[2] = { 0, 0 };
long long number;
stringstream ss;
 
 
long long num2point(long long num) {
    if (num <= 4) {
        switch (num) {
        case 2: point[0] += 1;
        case 1:
        default: return 0;
        case 3: point[0] += 1;
        case 0:
        case 4: point[1] += 1;
        }
        return 0;
    }
 
    long long piece = floor(logbl(num - 1) / 2);
    long long blocksize = powl(4, piece);
    long long blocknum = num / blocksize;
    long long blocklen = sqrtl(blocksize);
    long long least = num - blocksize * blocknum;
    if (num % blocksize == 0) least = blocksize;
 
    switch ((num - 1) / blocksize) {
    case 1: {
        point[0] += blocklen;
        break;
    }
    case 2: point[0] += blocklen;
    case 3: point[1] += blocklen;
    }
 
    return num2point(least);
}
 
 
void findpoint(long long num) {
    point[0] = point[1] = 1;
    num2point(num);
}
 
 
long long* point2num(long long* p) {
    long long maxp = fmaxl(p[0], p[1]);
    if (maxp <= 2) {
        switch (p[0]) {
            case 1: {
                switch (p[1]) {
                case 2: number += 3;
                case 1: number += 1;
                default: {
                    p[0] = p[1] = 0;
                    return p;
                }
                }
            }
            case 2: {
                switch (p[1]) {
                case 2: number += 1;
                case 1: number += 2;
                default: {
                    p[0] = p[1] = 0;
                    return p;
                }
                }
            }
        }
    }
    long long piece = floor(logbl(maxp-1));
    long long blocksize = powl(4, piece);
    long long blocklen = sqrtl(blocksize);
    bool isaxisX = p[0] > blocklen;
    bool isaxisY = p[1] > blocklen;
    switch (isaxisX && isaxisY) {
    case true: {
        number += blocksize * 2;
        p[0] -= blocklen;
        p[1] -= blocklen;
        return point2num(p);
    }
    case false: {
        if (isaxisX) {
            number += blocksize;
            p[0] -= blocklen;
            return point2num(p);
        }
        else {
            number += blocksize * 3;
            p[1] -= blocklen;
            return point2num(p);
        }
    }
    }
}
 
 
void findnum(long long* p) {
    number = 0;
    point2num(p);
}
 
long long* str2point(string str) {
    p[0] = 0;
    p[1] = 0;
    auto comma = str.find(",");
    if (comma == string::npos) return p;
    auto len = str.length();
    auto p0 = str.substr(1, comma - 1);
    auto p1 = str.substr(comma + 1, len - comma - 2);
    ss.clear();
    ss << p0;
    ss >> p[0];
    ss.clear();
    ss << p1;
    ss >> p[1];
    return p;
}
 
long long str2ll(string str) {
    long long ll;
    ss.clear();
    ss << str;
    ss >> ll;
    return ll;
}
 
int main() {
    long long times;
    cin >> times;
    while (times-- > 0) {
        string str;
        cin >> str;
        long long* p = str2point(str);
        if (p[0] == 0) {
            long long num = str2ll(str);
            findpoint(num);
            cout << "(" << point[0] << "," << point[1] << ")" << endl;
            continue;
        }
        findnum(p);
        cout << number << endl;
    }
}
/**************************************************************
    Problem: 1249
    User: 
    Language: C++
    Result: Accepted
    Time:1244 ms
    Memory:4844 kb
****************************************************************/

Problem F: Summer camp

Description

This summer holiday, members in SUSTechCPC went to Qinhuangdao to participate in a summer camp there. As they enjoyed a lot, they decided to take a group photo.

There are n member(s) in SUSTechCPC, and they want to stand in $k(k≥2)$ rows because it is too crowded to stand in only one row. To make the photo more beautiful, the number of people standing in the $i^{th}$ row should be exactly one more than the number of people standing in the $(i−1)^{th}$ row. Since they do not want to stand in too many rows, please tell them the minimum possible number of rows kk or determine that it is impossible to find any valid arrangement.

Input

The first line of the input contains one integer $T$, indicates the number of testcases.

For each testcase, there is only one line contains one integer $n$($1≤n≤1 000 000 000$).

Output

Print one single integer, the minimum possible $k$ described above.

If there is no such $k$, please output ‘impossible’ (without quotes).

Sample Input

1	3
2	8
3	10
4	24

Sample Output

1	impossible
2	4
3	3

HINT

10 = 1 + 2 + 3 + 4
24 = 7 + 8 + 9

#include <iostream>
#include <cmath>
 
 
using namespace std;
 
 
 
long double calX(long long n, long long members) {
    return (members - (n * n - n) / 2l) / (long double)n;
}
 
 
bool islongeger(long double num) {
    return abs(num - llround(num)) < 0.000000000000001;
}
 
 
long long calRow(long long members) {
    long double uplim = (sqrtl(1 + 8 * members) - 1) / 2;
    for (long i = 2; i <= uplim; i++) {
        long double x = calX(i, members);
        if (islongeger(x)) return i;
    }
    return -1;
}
 
 
int main() {
    long long times;
    cin >> times;
    while (times-- > 0) {
        long long members;
        cin >> members;
        long row = calRow(members);
        if (row == -1) {
            cout << "impossible" << endl;
            continue;
        }
        cout << row << endl;
    }
    return 0;
}
/**************************************************************
    Problem: 1246
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1740 kb
****************************************************************/

Lab1_Algorithm

Problem A: [Easy I] Crazy Plan

Description

Neko is crazy at solving the algorithm problems recently. He sets a plan for himself:

The $1^{st}$ day, he will get on 1 problem solved.

The $2^{nd}$ day, he will get on 3 problems solved.

The $3^{rd}$ day, he will get on 6 problems solved.

…

The $nth$ day, he will get on $n(n+1)/2$ problems solved.

Neko wants to know how many problems he will solve after $K$ days.

Input

The ﬁrst line contains a single integer $T$($1≤T≤1.1∗106$) —— the number of test case.

The 2nd2nd line to the $(T+1)th$ line, each line contains a single integer $K$($1≤K≤106$)—— the number of days.

Output

Print the number of problems Neko solved. Each test case for one line.

Sample Input

1	3
2	1
3	2
4	3

Sample Output

1	1
2	4
3	10

Code

1	#include <stdio.h>
2
3	using namespace std;
4
5
6	int main() {
7	long long times;
8	scanf("%lld", &times);
9	while (times-- > 0) {
10	long long n;
11	scanf("%lld", &n);
12	printf("%lld\n", n * (n + 1) * (n + 2) / 6);
13	}
14	return 0;
15	}
16
17	/**************************************************************
18	Problem: 1250
19	User:
20	Language: C++
21	Result: Accepted
22	Time:172 ms
23	Memory:1092 kb
24	****************************************************************/

1	public class Main {
2	public static void main(String[] args) {
3	java.util.Scanner input = new java.util.Scanner(System.in);
4	long times = input.nextLong();
5	while(times-->0) {
6	long n = input.nextLong();
7	System.out.println(n(n+1)(n+2)/6);
8	}
9	input.close();
10	}
11	}
12
13	/**************************************************************
14	Problem: 1250
15	User:
16	Language: Java
17	Result: Accepted
18	Time:3232 ms
19	Memory:41656 kb
20	****************************************************************/

Problem B: [Easy II] Nearest Price

Description

Neko likes to eat fish recently. There are various kinds of fish in the market and Neko has XX dollars. If the market happens to have a fish with a price of XX, Neko will say “Meow“. Otherwise, Neko will buy the most expensive fish which he can afford and say the change. (If Neko can’t afford any fish, he will come back directly and say the money he has.)

Neko will go to the market with XX dollars for TT days. XX may change everyday but the kinds of fish in the market will never change.

Input

The ﬁrst line contains a single integer $T$($1≤T≤106$) —— the number of the days when Neko needs to buy fish.

The second line contains a single integer $N$($1≤N≤106$) —— denoting there are/is NN kind(s) of fish in the market.

The third line contains TT integers$ x_1,x_2,x_3,…,x_T($1≤xi≤109$,$1≤i≤T$) —— the money Neko has for each day.

The fourth line contains NN integers $p_1,p_2,p_3,…,p_N$($1≤pi≤109,1≤i≤N$) which are the prices of the fish in the market.

It is guaranteed that prices are in ascending order.

Output

For each day, print only one line for what Neko said.

Sample Input

1	2
2	2
3	1 3
4	2 3

Sample Output

1	1
2	Meow

Code

#include <stdio.h>
 
using namespace std;
 
int read_int();
int* binarysearch(int* info);
 
int info[4] = { 0 };
int* prices;
 
 
int main() {
    int days = read_int();
    int kinds = read_int();
    int* money = new int[days];
    prices = new int[kinds];
    for (int i = 0; i < days; i++) money[i] = read_int();
    for (int i = 0; i < kinds; i++) prices[i] = read_int();
 
    for (int i = 0; i < days; i++) {
        info[0] = 0;
        info[1] = kinds - 1;
        info[2] = money[i];
        binarysearch(info);
        if (info[3] == -1) {
            if (prices[info[0]] > info[2]) printf("%d\n", info[2]);
            else if (prices[info[0]] < info[2] && info[2] < prices[info[1]]) printf("%d\n", info[2] - prices[info[0]]);
            else printf("%d\n", info[2] - prices[info[1]]);
        }
        else printf("Meow\n");
    }
    return 0;
}
 
 
int read_int() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0'>9) && r != '-' && !start) {
            continue;
        }
        if ((r - '0' < 0 || r - '0'>9) && r != '-' && start) {
            break;
        }
        if (start)ret *= 10;
        start = true;
        if (r == '-')neg = true;
        else ret += r - '0';
    }
    if (!neg)
        return ret;
    else
        return -ret;
}
 
 
int* binarysearch(int* info) {
    if (info[1] - info[0] == 1) {
        if (prices[info[0]] == info[2]) {
            info[3] = info[0];
            return info;
        }
        else if (prices[info[1]] == info[2]) {
            info[3] = info[1];
            return info;
        }
        else {
            info[3] = -1;
            return info;
        }
    }
    auto mid = (info[0] + info[1]) / 2;
    if (prices[mid] < info[2]) info[0] = mid;
    else info[1] = mid;
    return binarysearch(info);
}
 
/**************************************************************
    Problem: 1251
    User: 
    Language: C++
    Result: Accepted
    Time:216 ms
    Memory:9032 kb
****************************************************************/

Problem C: [Median I] Factorial Magic

Description

Neko is a freshman at SUSTech and he is good at fractorial problems. He wants to challenge you to see if you can solve the following problem: Caculate the value of $((n!)!)!(mod m)$.

Input

There is only one line contains two integers $n,m$($0≤n≤109,1≤m≤109$).

Output

Print the value of $((n!)!)!(mod m)$.

Sample Input

1 2019

Sample Output

HINT

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n: For example, The value of 0! is 1, according to the convention for an empty product.

Code

1	import java.util.Scanner;
2	import java.math.BigInteger;
3
4	public class Main {
5	public static void main(String[] args) {
6	Scanner input = new Scanner(System.in);
7	int n = input.nextInt();
8	int m = input.nextInt();
9	input.close();
10	BigInteger result = new BigInteger("0");
11	switch(n) {
12	case 0:
13	case 1: {
14	if(m != 1) result = new BigInteger("1");
15	break;
16	}
17	case 2: {
18	if(m > 2) result = new BigInteger("2");
19	break;
20	}
21	case 3: if (m > 720) result = new BigInteger("2601218943565795100204903227081043611191521875016945785727541837850835631156947382240678577958130457082619920575892247259536641565162052015873791984587740832529105244690388811884123764341191951045505346658616243271940197113909845536727278537099345629855586719369774070003700430783758997420676784016967207846280629229032107161669867260548988445514257193985499448939594496064045132362140265986193073249369770477606067680670176491669403034819961881455625195592566918830825514942947596537274845624628824234526597789737740896466553992435928786212515967483220976029505696699927284670563747137533019248313587076125412683415860129447566011455420749589952563543068288634631084965650682771552996256790845235702552186222358130016700834523443236821935793184701956510729781804354173890560727428048583995919729021726612291298420516067579036232337699453964191475175567557695392233803056825308599977441675784352815913461340394604901269542028838347101363733824484506660093348484440711931292537694657354337375724772230181534032647177531984537341478674327048457983786618703257405938924215709695994630557521063203263493209220738320923356309923267504401701760572026010829288042335606643089888710297380797578013056049576342838683057190662205291174822510536697756603029574043387983471518552602805333866357139101046336419769097397432285994219837046979109956303389604675889865795711176566670039156748153115943980043625399399731203066490601325311304719028898491856203766669164468791125249193754425845895000311561682974304641142538074897281723375955380661719801404677935614793635266265683339509760000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000").mod(new BigInteger(m+""));
22	}
23	System.out.println(result);
24	}
25	}
26
27	/**************************************************************
28	Problem: 1252
29	User:
30	Language: Java
31	Result: Accepted
32	Time:220 ms
33	Memory:19184 kb
34	****************************************************************/

Problem D: [Median II] Two-Product

Description

Neko thinks the two-sum problem is easy for you, so he tests you by a new problem —— the two-product problem.

Given an array of integers, $a_1,a_2,a_3,…,a_N$, and an integer $M$. Please output the number of pairs$ (a_i,a_j)$,$i<j$, such that $a_i∗a_j=M$.

Input

The ﬁrst line contains a single integer $N$($1≤N≤106$) —— the length of the array.

The second line contains a single integer $M$($−1018≤M≤1018$) —— the specific target.

The third line contains NN integers $a_1,a_2,a_3,…,a_N$($−109≤a_i≤109,1≤i≤N$) —— an array of integers.

It is guaranteed that the array is sorted in ascending order.

Output

For each specific target, print only one line for the number of a numbers pairs $(a_i,a_j)$ satisfying $a_i∗a_j=M$.

Sample Input

1	9
2	4
3	-4 -4 -2 -1 0 1 2 2 4

Sample Output

HINT

Duplicate pairs $(a_i,a_j)$ count only once!

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
int* array;
int info[4] = { 0 };
 
int binarysearch();
 
 
int main() {
    int arrlen;
    scanf("%d", &arrlen);
    long long int target;
    scanf("%lld", &target);
    array = new int[arrlen];
    bool* isSameBefore = new bool[arrlen];
    isSameBefore[0] = false;
    for (int i = 0; i < arrlen; i++) {
        scanf("%d", &(array[i]));
        if (i != 0 && array[i] != array[i - 1]) {
            isSameBefore[i] = false;
        }
        else if (i != 0) {
            isSameBefore[i] = true;
        }
    }
 
    int times = 0;
    if (target == 0) {
        info[0] = 0;
        info[1] = arrlen - 1;
        info[2] = 0;
        info[3] = -2;
        binarysearch();
        if (info[3] != -1) {
            for (int i = 0; i < arrlen; i++) {
                if (!isSameBefore[i] && array[i] != 0) {
                    times++;
                }
                else if (array[i] == 0) {
                    if (i == arrlen - 1) {
                        break;
                    }
                    if (array[i + 1] == 0) {
                        times++;
                        for (int j = i + 1; j < arrlen; j++) {
                            if (!isSameBefore[j]) {
                                i = j - 1;
                                break;
                            }
                            else if (j == arrlen - 1) {
                                i = j;
                                break;
                            }
                        }
                    }
                }
            }
        }
    }
    else {
        for (int i = 0; i < arrlen - 1; i++) {
            if (isSameBefore[i] || array[i] == 0) continue;
            if (target % array[i] == 0) {
                info[2] = target / array[i];
                if (info[2] < array[i]) continue;
                info[0] = (long long int)i + 1;
                info[1] = arrlen - 1;
                info[3] = -2;
                binarysearch();
                if (info[3] != -1) times++;
            }
        }
    }
    printf("%i\n", times);
    return 0;
}
 
 
int binarysearch() {
    if (info[1] - info[0] <= 1) {
        if (array[info[0]] == info[2]) {
            info[3] = info[0];
            return 0;
        }
        else if (array[info[1]] == info[2]) {
            info[3] = info[1];
            return 0;
        }
        else {
            info[3] = -1;
            return -1;
        }
    }
    auto mid = (info[0] + info[1]) / 2;
    if (array[mid] < info[2]) info[0] = mid;
    else info[1] = mid;
    return binarysearch();
}
 
/**************************************************************
    Problem: 1253
    User: 
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:6104 kb
****************************************************************/

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int arrayLength = input.nextInt();
        long target = input.nextLong();
        long[] array = new long[arrayLength];
        boolean[] isSameBefore = new boolean[arrayLength];
        for(int i = 0; i<arrayLength; i++) {
            array[i] = input.nextLong();
            if(i != 0 && array[i] == array[i - 1]) {
                isSameBefore[i] = true;
            }
        }
        input.close();
 
        long times = 0;
        if(target==0) {
            if(Arrays.binarySearch(array, 0, arrayLength, 0) >= 0) {
                for(int i = 0; i < arrayLength; i++) {
                    if(!isSameBefore[i] && array[i] != 0) {
                        times++;
                    }
                    else if(array[i] == 0) {
                        if(i == arrayLength - 1) {
                            break;
                        }
                        if(array[i + 1] == 0) {
                            times++;
                            for(int j = i + 1; j < arrayLength; j++) {
                                if(!isSameBefore[j]) {
                                    i = j - 1;
                                    break;
                                }
                                else if(j == arrayLength - 1) {
                                    i = j;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
        else {
            for(int i = 0; i < arrayLength - 1; i++) {
                if(isSameBefore[i] || array[i] == 0) continue;
                if(target % array[i] == 0) {
                    long key = target/array[i];
                    if(key<array[i]) continue;
                    if(Arrays.binarySearch(array, i+1, arrayLength, key) >= 0) {
                        times++;
                    }
                }
            }
        }
        System.out.println(times);
    }
}
 
/**************************************************************
    Problem: 1253
    User: 
    Language: Java
    Result: Accepted
    Time:1092 ms
    Memory:42520 kb
****************************************************************/

Problem E: [Hard] Catch Neko

Description

Neko is running away! Eve wants to catch him. At first, Eve is standing at the point with coordinates $(x1,y1)$, while Neko is standing at the point with coordinates $(x2,y2)$. For every minute, Eve can choose to go up, down, left, or right with 1 unit distance. For instance, if she is at $(x,y)$ now, she can go to $(x,y+1),(x,y−1),(x−1,y)$ or $(x+1,y)$.

Eve noticed that Neko also moves 1 unit distance every minute, but he only moves according to a sequence periodically. The sequence only contains ‘U’,’D’,’L’,’R’, denoting that Neko moves up, down, left, right respectively.

Eve is now wondering how many minutes she needs at least to catch Neko.

Input

The first line contains two integers $x_1,y_1$($0≤x_1,y_1≤109$) —— the initial coordinate of Eve.

The second line contains two integers $x_2,y_2$($0≤x_2,y_2≤109$) —— the initial coordinate of Neko.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer $N$($1≤N≤105$) —— the length of the sequence $S$.

The fourth line contains the string $S$ itself, consisting only four letters $U,D,L,R$.

Output

Please output the minimum minutes Eve needs to catch Neko. If she can not catch Neko forever, please output -1.

Sample Input

1	0 0
2	4 6
3	3
4	DDD

Sample Output

HINT

Eve can choose not to move at every minute.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
long long int seq[100000][2];
 
void move(long long int* p0, long long int* p1, char direction);
long long int calDistance(long long int p00, long long int p01, int* p1);
bool canCatch(long long int seq[][2], int seqlen, long long int* moveDistance, int* evePoint, long long int time);
long long int binarySearch(long long int seq[][2], int seqlen, long long int* moveDistance, int* evePoint, long long int low, long long int high);
 
int main() {
    int evePoint[2];
    scanf("%i %i", &evePoint[0], &evePoint[1]);
    int nekoPoint[2];
    scanf("%i %i", &nekoPoint[0], &nekoPoint[1]);
    int seqLength;
    scanf("%i", &seqLength);
    char* sequence = new char[seqLength];
    scanf("%s", sequence);
    if (nekoPoint[0] == evePoint[0] && nekoPoint[1] == evePoint[1]) {
        printf("%i\n", 0);
        return 0;
    }
    move(new long long int[2]{ nekoPoint[0], nekoPoint[1] }, seq[0], sequence[0]);
    for (int i = 1; i < seqLength; i++) {
        move(seq[i - 1], seq[i], sequence[i]);
    }
 
    long long int moveDistance[] = { seq[seqLength - 1][0] - nekoPoint[0], seq[seqLength - 1][1] - nekoPoint[1] };
 
    if (!canCatch(seq, seqLength,moveDistance, evePoint, 1000000000000000000L)) {
        printf("%i\n", -1);
        return 0;
    }
 
    long long int time = binarySearch(seq, seqLength, moveDistance, evePoint, 0, 1000000000000000000L) + 1;
    printf("%lli\n", time);
    return 0;
}
 
void move(long long int* p0, long long int* p1, char direction) {
    switch (direction) {
        case 'R': {
            p1[0] = p0[0] + 1;
            p1[1] = p0[1];
            break;
        }
        case 'L': {
            p1[0] = p0[0] - 1;
            p1[1] = p0[1];
            break;
        }
        case 'U': {
            p1[0] = p0[0];
            p1[1] = p0[1] + 1;
            break;
        }
        case 'D': {
            p1[0] = p0[0];
            p1[1] = p0[1] - 1;
            break;
        }
    }
}
 
long long int calDistance(long long int p00, long long int p01, int* p1) {
    return abs(p00 - p1[0]) + abs(p01 - p1[1]);
}
 
bool canCatch(long long int seq[][2], int seqlen, long long int* moveDistance, int* evePoint, long long int time) {
    return time + 1 >= calDistance(
        seq[(int)(time % seqlen)][0] + time / seqlen * moveDistance[0],
        seq[(int)(time % seqlen)][1] + time / seqlen * moveDistance[1],
        evePoint
    );
}
 
long long int binarySearch(long long int seq[][2], int seqlen, long long int* moveDistance, int* evePoint, long long int low, long long int high) {
    if (high - low <= 1) {
        if (!canCatch(seq, seqlen, moveDistance, evePoint, low) && canCatch(seq, seqlen, moveDistance, evePoint, high)) {
            return high;
        }
        if (canCatch(seq, seqlen, moveDistance, evePoint, low) && canCatch(seq, seqlen, moveDistance, evePoint, high)) {
            return low;
        }
    }
    long long int mid = (high + low) / 2;
    if (canCatch(seq, seqlen, moveDistance, evePoint, mid)) {
        return binarySearch(seq, seqlen, moveDistance, evePoint, low, mid);
    }
    else {
        return binarySearch(seq, seqlen, moveDistance, evePoint, mid, high);
    }
}
/**************************************************************
    Problem: 1254
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:2780 kb
****************************************************************/

public class Main {
    public static void main(String[] args) {
        java.util.Scanner input = new java.util.Scanner(System.in);
        int[] evePoint = {input.nextInt(), input.nextInt()};
        int[] nekoPoint = {input.nextInt(), input.nextInt()};
        int seqLength = input.nextInt();
        String sequence = input.next();
        input.close();
        if(nekoPoint[0]==evePoint[0] && nekoPoint[1]==evePoint[1]) {
            System.out.printf("%d\n", 0);
            return;
        }
        long[][] seq = new long[seqLength][2];
        seq[0] = move(new long[]{nekoPoint[0], nekoPoint[1]}, sequence.charAt(0));
        for(int i = 1; i < seqLength; i++) {
            seq[i] = move(seq[i-1], sequence.charAt(i));
        }
 
        long[] moveDistance = {seq[seqLength-1][0]-nekoPoint[0], seq[seqLength-1][1]-nekoPoint[1]};
 
        if(!canCatch(seq, moveDistance, evePoint, 1000000000000000000L)) {
            System.out.printf("%d\n", -1);
            return;
        }
 
        System.out.printf("%d\n", binarySearch(seq, moveDistance, evePoint, 0, 1000000000000000000L) + 1);
    }
 
    private static long[] move(long[] point, char direction) {
        long[] p = point.clone();
        switch(direction) {
            case 'R': {
                p[0]++;
                break;
            }
            case 'L': {
                p[0]--;
                break;
            }
            case 'U': {
                p[1]++;
                break;
            }
            case 'D': {
                p[1]--;
                break;
            }
            default:
        }
        return p;
    }
 
    private static long calDistance(long p00, long p01, int[] p1) {
        return Math.abs(p00 - p1[0]) + Math.abs(p01 - p1[1]);
    }
 
    private static boolean canCatch(long[][] seq, long[] moveDistance, int[] evePoint, long time) {
        return time + 1 >= calDistance(
                seq[(int)(time%seq.length)][0] + time/seq.length*moveDistance[0],
                seq[(int)(time%seq.length)][1] + time/seq.length*moveDistance[1],
                evePoint
        );
    }
 
    private static long binarySearch(long[][] seq, long[] moveDistance, int[] evePoint, long low, long high) {
        if(high - low <= 1) {
            if(!canCatch(seq, moveDistance, evePoint, low) && canCatch(seq, moveDistance, evePoint, high)) {
                return high;
            }
            if(canCatch(seq, moveDistance, evePoint, low) && canCatch(seq, moveDistance, evePoint, high)) {
                return low;
            }
        }
        long mid = (high+low) / 2;
        if(canCatch(seq, moveDistance, evePoint, mid)) {
            return binarySearch(seq, moveDistance, evePoint, low, mid);
        }
        else {
            return binarySearch(seq, moveDistance, evePoint, mid, high);
        }
    }
}
 
/**************************************************************
    Problem: 1254
    User: 
    Language: Java
    Result: Accepted
    Time:328 ms
    Memory:19356 kb
****************************************************************/

Problem F: [Bonus] Suffix Zero

Description

Neko thinks math is interesting but he has got stuck at a math problem, so he asks you for help.

Find the number of consecutive zeros at the end of n!n! (in decimal representation).

Input

The ﬁrst line contains a single integer $T$($1≤T≤10^6$) —— the number of test case.

The $2^{nd}$ line to the $(n+1)^{th}$ line, each line contains a single integer $n$($0≤n≤1018$).

Output

Print the number of consecutive zeros at the end of $n!4.

Sample Input

1	3
2	5
3	3
4	10

Sample Output

1	1
2	0
3	2

HINT

For the third case, 10! = 3628800, which have 2 consecutive zeros at the end.

Code

1	#include <stdio.h>
2
3	using namespace std;
4
5
6	int read_int() {
7	char r;
8	bool start = false, neg = false;
9	int ret = 0;
10	while (true) {
11	r = getchar();
12	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && !start) {
13	continue;
14	}
15	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && start) {
16	break;
17	}
18	if (start)ret *= 10;
19	start = true;
20	if (r == '-')neg = true;
21	else ret += r - '0';
22	}
23	if (!neg)
24	return ret;
25	else
26	return -ret;
27	}
28
29
30	long long read_ll() {
31	char r;
32	bool start = false, neg = false;
33	long long ret = 0;
34	while (true) {
35	r = getchar();
36	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && !start) {
37	continue;
38	}
39	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && start) {
40	break;
41	}
42	if (start)ret *= 10;
43	start = true;
44	if (r == '-')neg = true;
45	else ret += r - '0';
46	}
47	if (!neg)
48	return ret;
49	else
50	return -ret;
51	}
52
53
54	long long func(long long n) {
55	if (n < 5) return 0;
56	return n / 5 + func(n / 5);
57	}
58
59
60	int main() {
61	int times = read_int();
62	while (times-- > 0) {
63	long long n = read_ll();
64	printf("%lld\n", func(n - n % 5));
65	}
66	return 0;
67	}
68
69	/**************************************************************
70	Problem: 1255
71	User:
72	Language: C++
73	Result: Accepted
74	Time:368 ms
75	Memory:1092 kb
76	****************************************************************/

Lab2_Sorting

Problem A: Interesting number

Description

You are given $n$($n≥3$) numbers. Lanran thinks that the third largest number is interesting, but lanran does not like multiple numbers with the same value. If there are more than one numbers equal to the third largest number, please output ‘wa’ (without quotes), otherwise please print it out.

Input

There are multiple testcases.

The first line of the input contains a single integer $T$($1≤T≤10$), indicates the number of the testcases.

Then T testcases follow:

For each testcase, the first line contains a single integer $n$($3≤n≤100$).

The second line contains n integers $a_1,a_2,…,a_n$($0≤a_i≤100$), separated by a space.

Output

Output T integers for the answers of T testcases.

Sample Input

1	7
2	3
3	1 1 1
4	4
5	2 3 3 3
6	5
7	1 2 3 4 2
8	3
9	3 1 2
10	4
11	4 9 13 13
12	5
13	20 1 20 1 9
14	10
15	6 7 8 9 10 1 2 3 4 5

Sample Output

1	wa
2	wa
3	wa
4	1
5	9
6	9
7	8

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
void insertSort(int* array, int left, int right);
void swap(int* a, int* b);
int generatePivot(int* array, int left, int right);
void quickSort(int* array, int left, int right);
 
int main() {
    int times;
    std::scanf("%i", &times);
    while (times-- > 0) {
        int length;
        std::scanf("%i", &length);
        int* list = new int[length];
        for (int i = 0; i < length; i++) {
            std::scanf("%i", &list[i]);
        }
        quickSort(list, 0, length-1);
 
        if (list[length - 2] != list[length - 3] && (length == 3 || length > 3 && list[length - 4] != list[length - 3])) {
            printf("%i\n", list[length - 3]);
            continue;
        }
        printf("wa\n");
    }
    return 0;
}
 
void insertSort(int* array, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        auto key = array[i];
        auto j = i - 1;
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}
 
void swap(int* a, int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
int generatePivot(int* array, int left, int right) {
    auto mid = (left + right) >> 1;
    if (array[left] > array[mid]) swap(&array[left], &array[mid]);
    if (array[left] > array[right]) swap(&array[left], &array[right]);
    if (array[mid] > array[right]) swap(&array[mid], &array[right]);
    swap(&array[mid], &array[right - 1]);
    return array[right - 1];
}
 
void quickSort(int* array, int left, int right) {
    if (left >= right) return;
    if (right - left < 10) {
        insertSort(array, left, right);
        return;
    }
    auto pivot = generatePivot(array, left, right);
    int i = left, j = right - 1;
    while (true) {
        while (array[++i] < pivot);
        while (array[--j] > pivot);
        if (i < j) swap(&array[i], &array[j]);
        else break;
    }
    swap(&array[i], &array[right - 1]);
    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
}
/**************************************************************
    Problem: 1218
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1216 kb
****************************************************************/

1	#include <stdio.h>
2	#include <stdlib.h>
3
4
5	int cmpfunc (const void * a, const void * b) {
6	return (int)a - (int)b;
7	}
8
9	int main() {
10	int times;
11	scanf("%i", &times);
12	while (times-- > 0) {
13	int length;
14	scanf("%i", &length);
15	int list[100];
16	for (int i = 0; i < length; i++) {
17	scanf("%i", &list[i]);
18	}
19	qsort(list, length, sizeof(int), cmpfunc);
20
21	if (list[length - 2] != list[length - 3] && (length == 3 \|\| length > 3 && list[length - 4] != list[length - 3])) {
22	printf("%i\n", list[length - 3]);
23	continue;
24	}
25	printf("wa\n");
26	}
27	return 0;
28	}
29
30	/**************************************************************
31	Problem: 1218
32	User:
33	Language: C
34	Result: Accepted
35	Time:0 ms
36	Memory:1092 kb
37	****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
 
int main() {
    int times;
    std::scanf("%i", &times);
    while (times-- > 0) {
        int length;
        std::scanf("%i", &length);
        int* list = new int[length];
        for (int i = 0; i < length; i++) {
            std::scanf("%i", &list[i]);
        }
        std::sort(list, list + length);
 
        if (list[length - 2] != list[length - 3] && (length == 3 || length > 3 && list[length - 4] != list[length - 3])) {
            printf("%i\n", list[length - 3]);
            continue;
        }
        printf("wa\n");
    }
}
 
/**************************************************************
    Problem: 1218
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1220 kb
****************************************************************/

Problem B: Lucky number

Description

Given $n$ numbers $a_1,a_2,…,a_n$ and an integer $k$, Lanran thinks that the $k^{th}$ smallest number is a lucky number. Please tell him what is the value of the lucky number.

Input

The first line of the input contains two integers $n,k$($1≤n≤1 000 000,1≤k≤n$).

The second line contains $n$ integers $a_1,a_2,…,a_n$($0≤ai≤1 000 000$).

Output

Output one integer indicates the answer.

Sample Input

1	5 3
2	1 4 2 6 8

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
void insertSort(int* array, int left, int right);
void swap(int* a, int* b);
int generatePivot(int* array, int left, int right);
void quickSort(int* array, int left, int right);
 
int main() {
    int length;
    std::scanf("%i", &length);
    int kth;
    std::scanf("%i", &kth);
    int* list = new int[length];
    for (int i = 0; i < length; i++) {
        std::scanf("%i", &list[i]);
    }
    quickSort(list, 0, length-1);
 
    printf("%i", list[kth-1]);
    return 0;
}
 
void insertSort(int* array, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        auto key = array[i];
        auto j = i - 1;
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}
 
void swap(int* a, int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
int generatePivot(int* array, int left, int right) {
    auto mid = (left + right) >> 1;
    if (array[left] > array[mid]) swap(&array[left], &array[mid]);
    if (array[left] > array[right]) swap(&array[left], &array[right]);
    if (array[mid] > array[right]) swap(&array[mid], &array[right]);
    swap(&array[mid], &array[right - 1]);
    return array[right - 1];
}
 
void quickSort(int* array, int left, int right) {
    if (left >= right) return;
    if (right - left < 10) {
        insertSort(array, left, right);
        return;
    }
    auto pivot = generatePivot(array, left, right);
    int i = left, j = right - 1;
    while (true) {
        while (array[++i] < pivot);
        while (array[--j] > pivot);
        if (i < j) swap(&array[i], &array[j]);
        else break;
    }
    swap(&array[i], &array[right - 1]);
    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
}
/**************************************************************
    Problem: 1256
    User: 
    Language: C++
    Result: Accepted
    Time:372 ms
    Memory:5124 kb
****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
 
int main() {
    int length;
    std::scanf("%i", &length);
    int kth;
    std::scanf("%i", &kth);
    int* list = new int[length];
    for (int i = 0; i < length; i++) {
        std::scanf("%i", &list[i]);
    }
    std::sort(list, list + length);
 
    printf("%i", list[kth-1]);
    return 0;
}
 
/**************************************************************
    Problem: 1256
    User: 
    Language: C++
    Result: Accepted
    Time:408 ms
    Memory:5128 kb
****************************************************************/

1	#include <stdio.h>
2	#include <stdlib.h>
3
4	int compare (const void * a, const void * b) {
5	return (int)a - (int)b;
6	}
7
8	int main() {
9	int length;
10	scanf("%i", &length);
11	int kth;
12	scanf("%i", &kth);
13	int list[1000000];
14	for (int i = 0; i < length; i++) {
15	scanf("%i", &list[i]);
16	}
17	qsort(list, length, sizeof(int), compare);
18
19	printf("%i\n", list[kth-1]);
20	return 0;
21	}
22
23	/**************************************************************
24	Problem: 1256
25	User:
26	Language: C
27	Result: Accepted
28	Time:212 ms
29	Memory:8780 kb
30	****************************************************************/

Problem C: Only 3-sum

Description

Given $n$ numbers $a_1,a_2,…,a_n$ and a lucky number mm, please output the number of triple $(i,j,k)$,satisfying$a_i+a_j+a_k=m$($i<j<k$).

Input

The first line of the input contains two integers $n,m$($1≤n≤3000,1≤m≤1 000 000 000$).

The second line contains $n$ integers $a_1,a_2,…,a_n$($1≤a_i≤1 000 000 000$).

Output

Output one integer indicates the answer.

Sample Input

1	4 9
2	1 3 5 3

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int list0[3000];
int num[3000] = { 0 };
map<int, int> content;
 
int binarySearch(int* array, int low, int high, int key);
void insertSort(int* array, int left, int right);
void swap(int* a, int* b);
int generatePivot(int* array, int left, int right);
void quickSort(int* array, int left, int right);
 
int main() {
    int length;
    scanf("%i", &length);
    int sum;
    scanf("%i", &sum);
    for (int i = 0; i < length; i++) scanf("%i", &list0[i]);
    quickSort(list0, 0, length-1);
    num[0] = 1;
    for (int i = 1; i < length; i++) {
        if (list0[i] == list0[i - 1]) {
            num[i] = num[i - 1] + 1;
        }
        else {
            num[i] = 1;
            content.insert(pair<int, int>(list0[i - 1], i - 1));
        }
    }
    content.insert(pair<int, int>(list0[length - 1], length - 1));
 
    long long int time = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            int det = sum - list0[i] - list0[j];
            if (det > list0[length - 1]) continue;
            if (det < list0[j] || det < 1) break;
            int index = binarySearch(list0, j + 1, length - 1, det);
            if (index != -1) {
                if (list0[index] == list0[j]) {
                    time += num[content[list0[index]]] - num[j];
                }
                else {
                    time += num[content[list0[index]]];
                }
            }
        }
        if (list0[i] >= sum) break;
    }
    printf("%lli\n", time);
    return 0;
}
 
int binarySearch(int* array, int low, int high, int key) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (array[mid] == key) return mid;
    else if (array[mid] < key) return binarySearch(array, mid + 1, high, key);
    else return binarySearch(array, low, mid - 1, key);
}
 
 
void insertSort(int* array, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        auto key = array[i];
        auto j = i - 1;
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}
 
void swap(int* a, int* b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
 
int generatePivot(int* array, int left, int right) {
    auto mid = (left + right) >> 1;
    if (array[left] > array[mid]) swap(&array[left], &array[mid]);
    if (array[left] > array[right]) swap(&array[left], &array[right]);
    if (array[mid] > array[right]) swap(&array[mid], &array[right]);
    swap(&array[mid], &array[right - 1]);
    return array[right - 1];
}
 
void quickSort(int* array, int left, int right) {
    if (left >= right) return;
    if (right - left < 10) {
        insertSort(array, left, right);
        return;
    }
    auto pivot = generatePivot(array, left, right);
    int i = left, j = right - 1;
    while (true) {
        while (array[++i] < pivot);
        while (array[--j] > pivot);
        if (i < j) swap(&array[i], &array[j]);
        else break;
    }
    swap(&array[i], &array[right - 1]);
    quickSort(array, left, i - 1);
    quickSort(array, i + 1, right);
}
/**************************************************************
    Problem: 1258
    User: 
    Language: C++
    Result: Accepted
    Time:264 ms
    Memory:1280 kb
****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int list0[3000];
int num[3000] = { 0 };
map<int, int> content;
 
int binarySearch(int* array, int low, int high, int key);
 
int main() {
    int length;
    scanf("%i", &length);
    int sum;
    scanf("%i", &sum);
    for (int i = 0; i < length; i++) scanf("%i", &list0[i]);
    std::sort(list0, list0 + length);
    num[0] = 1;
    for (int i = 1; i < length; i++) {
        if (list0[i] == list0[i - 1]) {
            num[i] = num[i - 1] + 1;
        }
        else {
            num[i] = 1;
            content.insert(pair<int, int>(list0[i - 1], i - 1));
        }
    }
    content.insert(pair<int, int>(list0[length - 1], length - 1));
 
    long long int time = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            int det = sum - list0[i] - list0[j];
            if (det > list0[length - 1]) continue;
            if (det < list0[j] || det < 1) break;
            int index = binarySearch(list0, j + 1, length - 1, det);
            if (index != -1) {
                if (list0[index] == list0[j]) {
                    time += num[content[list0[index]]] - num[j];
                }
                else {
                    time += num[content[list0[index]]];
                }
            }
        }
        if (list0[i] >= sum) break;
    }
    printf("%lli\n", time);
    return 0;
}
 
int binarySearch(int* array, int low, int high, int key) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (array[mid] == key) return mid;
    else if (array[mid] < key) return binarySearch(array, mid + 1, high, key);
    else return binarySearch(array, low, mid - 1, key);
}
 
/**************************************************************
    Problem: 1258
    User: 
    Language: C++
    Result: Accepted
    Time:256 ms
    Memory:1284 kb
****************************************************************/

Problem D: Vinceblack’s store

Description

Vinceblack has a candy store with $n$ candies in a row, and the volume of each candy is $v_i$. To make the candy store more beautiful, Vince wants to move some candies to make them sorted in increasing order in volume. However, he can only exchange two adjacent candies, and the cost of the movement equals to the sum of volumes. Now Vince wants you to tell him what is the minimum cost to sort the candies.

Input

The first line of the input contains one integer $n$($1≤n≤100 000$).
The second line contains $n$ integers $v_1,v_2,…,v_n$($1≤vi≤100 000 000$).
It is guaranteed that the volume of all the candies are distinct.

Output

Output one integer indicates the minimum cost.

Sample Input

1	3
2	2 3 1

Sample Output

HINT

2 3 1 -> 2 1 3 cost: 4

2 1 3 -> 1 2 3 cost: 3

total cost: 4+3=7

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
int array[100000];
long long int sum[100000];
int temp[100000];
long long int cost = 0;
 
void mergeSort(int low, int mid, int high);
void mergeSort(int low, int high);
 
int main() {
    int length;
    scanf("%i", &length);
    for (int i = 0; i < length; i++) {
        scanf("%i", &array[i]);
        sum[i] = array[i];
    }
    mergeSort(0, length - 1);
    printf("%lli", cost);
    return 0;
}
 
void mergeSort(int low, int mid, int high) {
    sum[high] = sum[mid] + sum[high];
    long midSum = sum[mid];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (array[i] > array[j]) {
            cost += (long long int)array[j] * ((long long int)mid - i + 1);
            cost += midSum;
            temp[k++] = array[j++];
        }
        else {
            midSum -= array[i];
            temp[k++] = array[i++];
        }
    }
    while (i <= mid) temp[k++] = array[i++];
    while (j <= high) temp[k++] = array[j++];
    for (k = 0; k < high - low + 1; k++) array[low + k] = temp[k];
}
 
void mergeSort(int low, int high) {
    if (low >= high) return;
    int mid = (low + high) >> 1;
    mergeSort(low, mid);
    mergeSort(mid + 1, high);
    mergeSort(low, mid, high);
}
 
/**************************************************************
    Problem: 1257
    User: 
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:2652 kb
****************************************************************/

import java.util.Scanner;
 
public class Main {
    private static int[] array;
    private static long cost;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int len = input.nextInt();
        array = new int[len];
        for(int i = 0; i < len; i++) array[i] = input.nextInt();
        input.close();
        mergeSort(0, len-1);
        System.out.printf("%d\n", cost);
    }
 
    private static void mergeSort(int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;
        while(i <= mid && j <= high) {
            if (array[i] > array[j]) {
                cost += (long)array[j] * (mid - i + 1);
                for(int t = i; t <= mid; t++) cost += array[t];
                temp[k++] = array[j++];
            }
            else {
                temp[k++] = array[i++];
            }
        }
        while(i <= mid) temp[k++] = array[i++];
        while(j <= high) temp[k++] = array[j++];
        for(int t = 0; t < high - low + 1; t++) array[low + t] = temp[t];
    }
 
    private static void mergeSort(int low, int high) {
        if (low >= high) return;
        int mid = (low + high) >> 1;
        mergeSort(low, mid);
        mergeSort(mid + 1, high);
        mergeSort(low, mid, high);
    }
}
 
/**************************************************************
    Problem: 1257
    User: 
    Language: Java
    Result: Accepted
    Time:2136 ms
    Memory:42024 kb
****************************************************************/

import java.util.Scanner;
 
public class Main {
    private static int[] array;
    private static long[] sum;
    private static long cost;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int len = input.nextInt();
        array = new int[len];
        sum = new long[len];
        for(int i = 0; i < len; i++) sum[i] = array[i] = input.nextInt();
        input.close();
        mergeSort(0, len-1);
        System.out.printf("%d\n", cost);
    }
 
    private static void mergeSort(int low, int mid, int high) {
        sum[high] = sum[mid] + sum[high];
        long midSum = sum[mid];
        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;
        while(i <= mid && j <= high) {
            if (array[i] > array[j]) {
                cost += midSum;
                cost += (long)array[j] * (mid - i + 1);
                //for(int t = i; t <= mid; t++) cost += array[t];
                temp[k++] = array[j++];
            }
            else {
                midSum -= array[i];
                temp[k++] = array[i++];
            }
        }
        while(i <= mid) temp[k++] = array[i++];
        while(j <= high) temp[k++] = array[j++];
        for(int t = 0; t < high - low + 1; t++) array[low + t] = temp[t];
    }
 
    private static void mergeSort(int low, int high) {
        if (low >= high) return;
        int mid = (low + high) >> 1;
        mergeSort(low, mid);
        mergeSort(mid + 1, high);
        mergeSort(low, mid, high);
    }
}
 
/**************************************************************
    Problem: 1257
    User: 
    Language: Java
    Result: Accepted
    Time:684 ms
    Memory:41692 kb
****************************************************************/

Problem E: Excellent power

Description

In the tale, there was a great wizard at SUSTech called SUSTechDaFaShi with excellent power. With his great power, DFS led a scourge army with $n$ ultimate soldiers. Each soldier has 2 attributes, hp and attack. What’s more, DFS can cast at most $p$ times of spell1 to make one soldier double its hp, and at most $q$ times of spell2 to make one soldier’s attack equal to its hp. DFS wants to know the maximum sum of the attack of all his soldiers after casting two kinds of spells.

Input

The first line of the input contains three integers $n,p,q$($1≤n≤200 000,0≤p≤20,0≤q≤200 000$).

Then $n$ lines follow, each line contains two integers $hp_i,attack_i$($1≤hp_i,attack_i≤1 000 000 000$), indicates the hp and attack of the $i^{th}$ soldier.

Output

Print one single integer, the sum of the attack of all the soldiers.

Sample Input

1	2 1 1
2	10 8
3	6 1

Sample Output

HINT

DFS can choose not to cast any spell.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
long long soldiers[200000][2];
long long tempS[200000][2];
long long profit[200000];
long long temp[200000];
long long attack;
 
void mergeSort(long long* array, int low, int high);
int findMax(long long* array, int len);
 
int main() {
    int soldierNum, divineSpirit, innerFire; 
    scanf("%i %i %i", &soldierNum, &divineSpirit, &innerFire);
    for (int i = 0; i < soldierNum; i++) scanf("%lli %lli", &soldiers[i][0], &soldiers[i][1]);
    if (innerFire == 0) {
        for (int i = 0; i < soldierNum; i++) attack += soldiers[i][1];
        printf("%lli\n", attack);
        return 0;
    }
    for (int i = 0; i < soldierNum; i++) profit[i] = soldiers[i][0] - soldiers[i][1];
    mergeSort(profit, 0, soldierNum - 1);
    long long times = 1;
    times <<= divineSpirit;
    int lastIF = innerFire;
    int last = 0;
    auto atk = soldiers[0][1];
    for (int i = 0, iF = innerFire; i < soldierNum && iF > 0; i++, iF--, lastIF--) {
        if (profit[i] > 0) {
            last = i;
            atk = soldiers[i][1];
            soldiers[i][1] = soldiers[i][0];
        }
        else break;
    }
    for (int i = 0; i < soldierNum; i++) {
        profit[i] = soldiers[i][0] * times - soldiers[i][1];
        if (i >= innerFire - lastIF && profit[last] > 0 && lastIF == 0) {
            profit[i] = soldiers[i][0] * times - soldiers[i][1] - soldiers[last][0] + atk;
        }
    }
    auto index = findMax(profit, soldierNum);
    if (index > last && profit[last] > 0 && lastIF == 0) soldiers[last][1] = atk;
    if (profit[index] > 0) soldiers[index][1] = soldiers[index][0] * times;
    for (int i = 0; i < soldierNum; i++) attack += soldiers[i][1];
    printf("%lli\n", attack);
    return 0;
}
 
bool comparator(long long a, long long b) {
    return a >= b;
}
 
void copyArray(int indexA, long long* A, long long As[][2], int indexB, long long* B, long long Bs[][2]) {
    A[indexA] = B[indexB];
    As[indexA][0] = Bs[indexB][0];
    As[indexA][1] = Bs[indexB][1];
}
 
void mergeSort(long long* array, int low, int mid, int high) {
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (comparator(array[i], array[j])) copyArray(k++, temp, tempS, i++, array, soldiers);
        else copyArray(k++, temp, tempS, j++, array, soldiers);
    }
    while (i <= mid) copyArray(k++, temp, tempS, i++, array, soldiers);
    while (j <= high) copyArray(k++, temp, tempS, j++, array, soldiers);
    for (k = 0; k < high - low + 1; k++) copyArray(low + k, array, soldiers, k, temp, tempS);
}
 
void mergeSort(long long* array, int low, int high) {
    if (low >= high) return;
    auto mid = (low + high) >> 1;
    mergeSort(array, low, mid);
    mergeSort(array, mid + 1, high);
    mergeSort(array, low, mid, high);
}
 
int findMax(long long* array, int len) {
    auto max = array[0];
    int index = 0;
    for (int i = 1; i < len; i++) {
        if (array[i] > max) {
            max = array[i];
            index = i;
        }
    }
    return index;
}
/**************************************************************
    Problem: 1221
    User: 
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:10464 kb
****************************************************************/

Problem F: YYJ’s magic beads

Description

YYJ has many magic beads with two colors, red and blue. If a red bead is on the left of a blue bead and they are next to each other, they will disappear and release 1 unit of magic power. YYJ has $n$ strings of beads, each string is consists of $a_i$ blue beads on the left and $b_i$ red beads on the right (To make sure they will disappear). Note that $a_i$ and $b_i$ can be zero.

YYJ now wants to connect these strings in some order and she is wondering how many units of magic power she can get at most.

Input

The first line contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$($1≤n≤100 000$), indicating the number of string of beads.

Each of the next $n$ lines contains two integers $a_i,b_i$($1≤a_i+b_i≤10 000$).

It is guaranteed that $∑(a_i+b_i)≤500 000$.

Output

Output one integer, indicating the answer.

Sample Input

1	2
2	2
3	1 2
4	2 1
5	2
6	1 3
7	2 1

Sample Output

1	2
2	2

HINT

We use ‘R’ to denote red beads and ‘B’ to denote blue beads.

We have 2 strings: BRR, BBR at first.

The string after connection is: BRRBBR, which can gain 2 units of magic power.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
int strings[100000][2];
int temp[100000][2];
 
bool comparator(int* a, int* b);
void mergeSort(int array[][2], int low, int mid, int high);
void mergeSort(int array[][2], int low, int high);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase-- > 0) {
        int stringNum;
        long long int mana = 0;
        scanf("%i", &stringNum);
        for (int i = 0; i < stringNum; i++) scanf("%i %i", &strings[i][0], &strings[i][1]);
        mergeSort(strings, 0, stringNum - 1);
        for (int i = 1; i < stringNum; i++) {
            int temp = strings[i - 1][1] - strings[i][0];
            if (temp > 0) {
                mana += strings[i][0];
                strings[i][1] += temp;
                strings[i][0] = 0;
                strings[i - 1][1] = 0;
            }
            else {
                mana += strings[i - 1][1];
                strings[i - 1][0] -= temp;
                strings[i][0] = 0;
                strings[i - 1][1] = 0;
            }
        }
        printf("%lli\n", mana);
    }
    return 0;
}
 
bool comparator(int* a, int* b) {
    if (a[0] < a[1]) {
        if (b[0] < b[1]) return a[0] < b[0];
        else return true;
    }
    else {
        if (b[0] < b[1]) return false;
        else return a[1] > b[1];
    }
}
 
void copyArray(int* a, int* b) {
    a[0] = b[0];
    a[1] = b[1];
}
 
void mergeSort(int array[][2], int low, int mid, int high) {
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if(comparator(array[i], array[j])) copyArray(temp[k++], array[i++]);
        else copyArray(temp[k++], array[j++]);
    }
    while (i <= mid) copyArray(temp[k++], array[i++]);
    while (j <= high) copyArray(temp[k++], array[j++]);
    for (k = 0; k < high - low + 1; k++) copyArray(array[low + k], temp[k]);
}
 
void mergeSort(int array[][2], int low, int high) {
    if (low >= high) return;
    int mid = (low + high) >> 1;
    mergeSort(array, low, mid);
    mergeSort(array, mid + 1, high);
    mergeSort(array, low, mid, high);
}
 
/**************************************************************
    Problem: 1259
    User: 
    Language: C++
    Result: Accepted
    Time:88 ms
    Memory:2652 kb
****************************************************************/

Lab3_Linked_List

Problem A: Add polynomials together

Description

As Narnal has learned in the class, a polynomial can be represented as a linked list, but he failed to add two given polynomials together. He asks you to help him to get the summation of two polynomials.

Input

First line will be a positive integer $T$, which is the number of test cases.

In each test case, the first line will be an integer $n$ for the number of terms of the first polynomial. Then the next $n$ lines will be the coefficients and exponents of the terms with the order of increasing exponents.

After $n+1$ lines, there will be an integer $m$ for the number of terms of the second polynomial. Then the next $m$ lines will be the coefficients and exponents of the terms with the order of increasing exponents.

After $n+m+2$ lines, there will be an integer $q$ denoting the number of queries. Then one line containing $q$ ascending numbers will follow, where each number $k$ represents a query for the coefficient of exponent of $k$.

$1≤T≤200,1≤n,m≤103,1≤q≤2×10^3,0≤k≤10^9$. The coefficients will be in range $[−104,104]$. The exponents will be in range $[0,109]$.

Output

For each case, output one line contains $q$ answers of the corresponding queries.

Sample Input

1	1
2	2
3	1 1
4	2 3
5	3
6	1 100
7	3 150
8	5 170
9	4
10	1 20 100 170

Sample Output

1 0 1 5

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
struct Node {
    int coefficient;
    int exponent;
    Node* next;
};
 
class linkedList {
public:
    Node* head, * tail, * last;
 
    linkedList() {
        head = new Node;
        last = head;
        tail = new Node;
        head->next = tail;
        head->exponent = 0;
        tail->exponent = -1;
    }
 
    void addElement(int coefficient, int exponent) {
        Node* temp = new Node;
        temp->coefficient = coefficient;
        temp->exponent = exponent;
        temp->next = tail;
        last->next = temp;
        last = last->next;
    }
};
 
int readInt();
int queries[2000];
 
int main() {
    int testCase = readInt();
    int terms;
    int c;
    int e;
    while (testCase--) {
        terms = readInt();
        linkedList polynomial0 = linkedList();
        while (terms--) {
            c = readInt();
            e = readInt();
            polynomial0.addElement(c, e);
        }
        terms = readInt();
        linkedList polynomial1 = linkedList();
        while (terms--) {
            c = readInt();
            e = readInt();
            polynomial1.addElement(c, e);
        }
        terms = readInt();
        bool isContinue = true;
        for (int i = 0; i < terms; i++) queries[i] = readInt();
        linkedList p = linkedList();
        Node* temp0 = polynomial0.head->next;
        Node* temp1 = polynomial1.head->next;
        while (temp0 != NULL && temp1 != NULL) {
            if (temp0->exponent == -1) {
                if (temp1->exponent == -1) break;
                p.addElement(temp1->coefficient, temp1->exponent);
                temp1 = temp1->next;
            }
            else if (temp1->exponent == -1) {
                if (temp0->exponent == -1) break;
                p.addElement(temp0->coefficient, temp0->exponent);
                temp0 = temp0->next;
            }
            else if (temp0->exponent > temp1->exponent) {
                p.addElement(temp1->coefficient, temp1->exponent);
                temp1 = temp1->next;
            }
            else if (temp0->exponent < temp1->exponent) {
                p.addElement(temp0->coefficient, temp0->exponent);
                temp0 = temp0->next;
            }
            else {
                p.addElement(temp0->coefficient + temp1->coefficient, temp0->exponent);
                temp0 = temp0->next;
                temp1 = temp1->next;
            }
        }
        Node* temp = p.head->next;
        for (int i = 0; i < terms; i++) {
            if (queries[i] > p.last->exponent) {
                for (; i < terms; i++) printf("%d ", 0);
                break;
            }
            for (; temp->exponent > -1; temp = temp->next) {
                if (queries[i] == temp->exponent) {
                    printf("%d ", temp->coefficient);
                    break;
                }
                else if (queries[i] < temp->exponent) {
                    printf("%d ", 0);
                    break;
                }
            }
        }
        printf("\n");
    }
    return 0;
}
 
 
int readInt() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) continue;
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) break;
        if (start) ret *= 10;
        start = true;
        if (r == '-')neg = true;
        else ret += r - '0';
    }
    if (!neg)
        return ret;
    else
        return -ret;
}
 
/**************************************************************
    Problem: 1261
    User: 
    Language: C++
    Result: Accepted
    Time:132 ms
    Memory:24456 kb
****************************************************************/

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
        InputReader input = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int testCase = input.nextInt();
        while(testCase-->0) {
            int terms = input.nextInt();
            LinkedList polynomial0 = new LinkedList();
            while(terms-->0) polynomial0.addElement(input.nextInt(), input.nextInt());
            terms = input.nextInt();
            LinkedList polynomial1 = new LinkedList();
            while(terms-->0) polynomial1.addElement(input.nextInt(), input.nextInt());
            terms = input.nextInt();
            int[] queries = new int[terms];
            boolean isContinue = true;
            for (int i = 0; i < terms; i++) queries[i] = input.nextInt();
            LinkedList p = new LinkedList();
            Node temp0 = polynomial0.head.next;
            Node temp1 = polynomial1.head.next;
            while (temp0!=null && temp1!=null) {
                if(temp0.exponent==-1) {
                    if(temp1.exponent==-1) break;
                    p.addElement(temp1.coefficient, temp1.exponent);
                    temp1 = temp1.next;
                }
                else if(temp1.exponent==-1) {
                    if(temp0.exponent==-1) break;
                    p.addElement(temp0.coefficient, temp0.exponent);
                    temp0 = temp0.next;
                }
                else if(temp0.exponent > temp1.exponent) {
                    p.addElement(temp1.coefficient, temp1.exponent);
                    temp1 = temp1.next;
                }
                else if(temp0.exponent < temp1.exponent) {
                    p.addElement(temp0.coefficient, temp0.exponent);
                    temp0 = temp0.next;
                }
                else {
                    p.addElement(temp0.coefficient+temp1.coefficient, temp0.exponent);
                    temp0 = temp0.next;
                    temp1 = temp1.next;
                }
            }
            Node temp = p.head.next;
            for (int i = 0; i < terms; i++) {
                if (queries[i] > p.last.exponent) {
                    for (; i < terms; i++) out.printf("%d ", 0);
                    break;
                }
                for (; temp.exponent > -1; temp = temp.next) {
                    if (queries[i] == temp.exponent) {
                        out.printf("%d ", temp.coefficient);
                        break;
                    }
                    else if (queries[i] < temp.exponent) {
                        out.printf("%d ", 0);
                        break;
                    }
                }
            }
            out.println();
        }
        out.close();
    }
 
    private static class Node {
        int coefficient;
        int exponent;
        Node next;
 
        Node(int coefficient, int exponent) {
            this.coefficient = coefficient;
            this.exponent = exponent;
        }
    }
 
    private static class LinkedList {
        Node head;
        Node tail;
        Node last;
 
        LinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, -1);
            last = head;
        }
 
        void addElement(Node node) {
            node.next = tail;
            last.next = node;
            last = last.next;
        }
 
        void addElement(int coefficient, int exponent) {
            addElement(new Node(coefficient, exponent));
        }
    }
 
    private static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
 
        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}
 
/**************************************************************
    Problem: 1261
    User: 
    Language: Java
    Result: Accepted
    Time:1948 ms
    Memory:126244 kb
****************************************************************/

Problem B: Black era

Description

The war in Ursus has broken out! Now, Wamiya and her teammates have to escape from this dangerous place immediately. In order to avoid the falling objects from the surrounding buildings, all the team members are lined up in a row while moving forward. In order to defend against enemy attacks, Wamiya should also constantly change the form of the team by exchanging two parts of the row, i.e., she will specify two continuous parts in the row, and exchange their locations without changing anything inside each part. There will be $N$ members in the team, and Wamiya will give $M$ orders one by one. Given the initial team, what will be the final team after their escape?

Input

First line contains one integer $T$, indicating that there will be $T$ cases.

For each case, the first line will be two integers $N$ and $M$. $N$ is the number of the members in the team, and $M$ is the number of orders.

The second line will be $N$ integers, indicating the initial formation of the team. Each number is unique and represents the ID of the member. We guarantee that ID is in the range of $[0,N−1]$.

The following $M$ lines represent $M$ orders. In each line, there are four integers $x_1,y_1,x_2,y_2$, which mean the part $[x_1,y_1]$ (starting from member with ID $x_1$ and ending at the member with ID $y_1$), should exchange the position with part $[x_2,y_2]$.

$T≤5,1≤N,M≤10^5$. We guarantee that in each order, members with ID $x_1,y_1,x_2,y_2$ will be arranged in order from front to back in the row. Notice that $x_1$ could be equal to $y_1$ and $x_2$ could be equal to $y_2$.

Output

For each case, output $N$ integer in one line to represent the final team consisting of member IDs.

Sample Input

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

Sample Output

1	6 5 0 7 9 8 1 2 3 4

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
struct Node {
    int id;
    Node* previous;
    Node* next;
    Node(int id) {
        this->id = id;
        previous = NULL;
        next = NULL;
    }
};
 
class linkedList {
public:
    Node* head;
    Node* tail;
 
    linkedList() {
        head = new Node(-2);
        tail = new Node(-1);
        head->next = tail;
        tail->previous = head;
    }
 
    void addElement(Node* node) {
        node->previous = tail->previous;
        node->next = tail;
        tail->previous->next = node;
        tail->previous = node;
    }
 
    void exchange(Node* x1, Node* y1, Node* x2, Node* y2) {
        Node* temp = x1->previous;
        temp->next = x2;
        x2->previous->next = x1;
        x1->previous = x2->previous;
        x2->previous = temp;
        temp = y2->next;
        temp->previous = y1;
        y1->next->previous = y2;
        y2->next = y1->next;
        y1->next = temp;
    }
 
    void print() {
        for (Node* i = head->next; i->id > -1; i = i->next) printf("%d ", i->id);
        printf("\n");
    }
 
    void destory() {
        Node* current = head;
        while (current != NULL) {
            Node* temp = current->next;
            delete current;
            current = temp;
        }
    }
};
 
int readInt();
Node* address[100000];
 
int main() {
    int testCase = readInt();
    while (testCase--) {
        int members = readInt();
        int reorders = readInt();
        linkedList team = linkedList();
        while (members--) {
            int id = readInt();
            address[id] = new Node(id);
            team.addElement(address[id]);
        }
        while (reorders--) {
            int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt();
            team.exchange(address[x1], address[y1], address[x2], address[y2]);
        }
        team.print();
        team.destory();
    }
    return 0;
}
 
 
int readInt() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) continue;
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) break;
        if (start) ret *= 10;
        start = true;
        if (r == '-')neg = true;
        else ret += r - '0';
    }
    if (!neg)
        return ret;
    else
        return -ret;
}
 
/**************************************************************
    Problem: 1262
    User: 
    Language: C++
    Result: Accepted
    Time:128 ms
    Memory:5036 kb
****************************************************************/

Problem C: Converted Vinux input

Description

Narnal is a huge fan of vim, so he has created a text editor called Vinux, which can only edit one line with several operations. Each line has an invisible undeletable tail character called EOL (end of line), which will always stay at the end of the line in any circumstance. Notice that the undeletable property of EOL means that EOL will revive immediately at the end of the line whenever it vanishes (been replaced or deleted). He wants to covert a one-line keyboard input containing operations and digits into a one-line real input with only digits.

Only the following operations are available:

r: next single input would replace the current character;

I: move the character pointer to the head of the line;

H: left shift the current character pointer unless it is at the leftmost place;

L: right shift the current character pointer unless it is at the rightmost place;

x: delete the current character;

Otherwise, each input would insert before the current character.

Input

First line will be a positive integer $T$, which is the number of test cases.

In each test case, the first line would be an integer $n$ for the length of the keyboard input of Vinux. Then the following line represents the keyboard input of Vinux.

$T≤20,20≤n≤10^5$. The aiming real input only contains digits without blanks. The input would always be valid (the input after r would never be an operation character).

Output

For each case, output one line shows the real input without EOL.

Sample Input

2
25
12345HHHr9Ir000LLLLL876Ix
20
r60xxxxHx4xHH3III1I2

Sample Output

1	002945876
2	2134

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
struct Node {
    char character;
    Node* previous;
    Node* next;
    Node(char character) {
        this->character = character;
        previous = NULL;
        next = NULL;
    }
};
 
class linkedList {
public:
    Node* head;
    Node* tail;
    Node* current;
 
    linkedList() {
        head = new Node(' ');
        tail = new Node('\n');
        head->next = tail;
        tail->previous = head;
        current = tail;
    }
 
    void addElement(Node* node) {
        node->previous = current->previous;
        node->next = current;
        current->previous->next = node;
        current->previous = node;
    }
 
    void addElement(char c) {
        addElement(new Node(c));
    }
 
    void print() {
        for (Node* i = head->next; i != NULL; i = i->next) putchar(i->character);
    }
 
    void destory() {
        current = head;
        while (current != NULL) {
            Node* temp = current->next;
            delete current;
            current = temp;
        }
    }
 
    void del(Node* node) {
        node->previous->next = node->next;
        node->next->previous = node->previous;
        delete(node);
    }
};
 
int readInt();
bool isDigit(char c);
 
int main() {
    int testCase = readInt();
    while (testCase--) {
        int input = readInt();
        linkedList str = linkedList();
        while (input--) {
            char c = getchar();
            if (isDigit(c)) str.addElement(c);
            else {
                switch (c) {
                case 'r': {
                    if (input == 0) break;
                    c = getchar();
                    input--;
                    if (str.current->character == '\n') {
                        str.addElement('\n');
                        str.current = str.current->previous;
                    }
                    str.current->character = c;
                    break;
                }
                case 'I': {
                    str.current = str.head->next;
                    break;
                }
                case 'H': {
                    if (str.current->previous->character == ' ') break;
                    str.current = str.current->previous;
                    break;
                }
                case 'L': {
                    if (str.current->character == '\n') break;
                    str.current = str.current->next;
                    break;
                }
                case 'x': {
                    if (str.current->character == '\n') break;
                    str.current = str.current->next;
                    str.del(str.current->previous);
                }
                }
            }
        }
        str.print();
        str.destory();
    }
    return 0;
}
 
bool isDigit(char c) {
    return '0' <= c && c <= '9';
}
 
int readInt() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) continue;
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) break;
        if (start) ret *= 10;
        start = true;
        if (r == '-') neg = true;
        else ret += r - '0';
    }
    if (!neg) return ret;
    else return -ret;
}
 
/**************************************************************
    Problem: 1263
    User: 
    Language: C++
    Result: Accepted
    Time:144 ms
    Memory:3856 kb
****************************************************************/

Problem D: Difficult Josephus problem

Description

Josephus problem is a theoretical problem related to a certain counting-out game. However, Narnal thought this problem is too easy for him, so he constructed a more complex Josephus problem as following.

There are nn people standing in a circle indexing from $1$ to $n$, and each person in the circle holds a note marked with a positive integer. At first, given a positive integer mm, people count the number from one to the next starting from index $1$ in clockwise ($1,2,…,n,1,2,…$). When the counted number reaches $m$, the corresponding person will be eliminated from the circle and yell the number in his/her note, denoted by $k_i$, and then people restart counting from the next person targeting for number $k_i$ until, eventually, only one person is left in the circle.

Input

First line will be a positive integer $T$, which is the number of test cases.

In each test case, the first line would be two integers $n$ and $m$, where $n$ is the initial number of people, and $m$ is the initial target counting number.

Then there will be a single line containing $n$ integers, indicating the number on each person’s note, from index $1$ to index $n$.

$T≤100,1≤n≤10^4$. $m$ and each number on the notes will be in the range of $[1,108]$. We guarantee that there are no more than $20$ cases with $n>5×10^3$.

Output

For each case, output one line with one integer for the index of the remaining people.

Sample Input

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

Sample Output

1	3
2	1

Code

#include <stdio.h>
 
using namespace std;
 
struct Node {
    int id;
    int count;
    Node* previous;
    Node* next;
    Node(int id, int count) {
        this->id = id;
        this->count = count;
        previous = NULL;
        next = NULL;
    }
};
 
class linkedList {
public:
    Node* head, * tail;
    int length;
 
    linkedList(int id, int count) {
        length = 1;
        head = new Node(id, count);
        tail = head;
    }
 
    void addElement(Node* node) {
        length++;
        tail->next = node;
        node->previous = tail;
        tail = node;
    }
 
    void addElement(int id, int count) {
        addElement(new Node(id, count));
    }
 
    void del(Node* node) {
        if (node == head) head = head->previous;
        node->previous->next = node->next;
        node->next->previous = node->previous;
        delete(node);
        length--;
    }
 
    void loop() {
        if (length == 1) return;
        head->previous = tail;
        tail->next = head;
    }
};
 
int readInt();
 
int main() {
    int testCase = readInt();
    while (testCase--) {
        int members = readInt();
        int loop = readInt();
        linkedList circle = linkedList(1, readInt());
        for (int i = 2; i <= members; i++) circle.addElement(i, readInt());
        circle.loop();
        Node* start = circle.head;
        while (circle.length != 1) {
            loop %= circle.length;
            Node* temp = start;
            if (circle.length - loop >= circle.length >> 1) {
                while (loop--) temp = temp->next;
                start = temp;
                loop = temp->previous->count;
                circle.del(temp->previous);
            }
            else {
                loop = circle.length - loop;
                while (loop--) temp = temp->previous;
                start = temp;
                loop = temp->previous->count;
                circle.del(temp->previous);
            }
        }
        printf("%d\n", circle.head->id);
    }
    return 0;
}
 
int readInt() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) continue;
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) break;
        if (start) ret *= 10;
        start = true;
        if (r == '-') neg = true;
        else ret += r - '0';
    }
    if (!neg) return ret;
    else return -ret;
}
 
/**************************************************************
    Problem: 1264
    User: 
    Language: C++
    Result: Accepted
    Time:1240 ms
    Memory:1480 kb
****************************************************************/

Problem E: Eccentric calculator

Description

Yuki is a clever girl and she is playing an eccentric calculator. The eccentric calculator can only display $n$ digits, which really annoys her.

She enters a number $m$ in the calculator first, and then just repeatedly squares it until the result overflows. When it overflows, only the $n$ most significant digits can still be displayed on the screen, and an error will appear at the same time. Yuki can clear the error flag and continue squaring the displayed number. She wonders what is the largest number she can get by repeatedly doing this procedure for given $n$ and $m$.

Input

The first line contains an integer $t$ ($1≤t≤200$) — the number of test cases. Each test case contains one line with two integers: $n$ and $m$ ($1≤n≤9,0≤m<10^n$) — the number of digits and the starting number.

Output

For each test case, print one line with the maximum number that Yuki can obtain.

Sample Input

1	2
2	1 5
3	2 99

Sample Output

1	5
2	99

HINT

Yuki can obtain $5→2(5)→4→1(6)→1→1→⋯$ respectively in the first case by repeatedly squaring it.

Code

#include <stdio.h>
 
using namespace std;
 
int readInt();
int generateNext(int number, int maxLen);
 
int max;
 
int main() {
    auto testCase = readInt();
    while (testCase--) {
        auto digit = readInt();
        auto number = readInt();
        if (number == 0) {
            printf("%d\n", number);
            continue;
        }
        int maxLen = 1;
        while (digit--) maxLen *= 10;
        max = number;
        auto slow = generateNext(number, maxLen);
        auto fast = generateNext(slow, maxLen);
        while (slow != fast) {
            slow = generateNext(slow, maxLen);
            fast = generateNext(generateNext(fast, maxLen), maxLen);
        }
        printf("%d\n", max);
    }
    return 0;
}
 
int readInt() {
    char r;
    bool start = false, neg = false;
    int ret = 0;
    while (true) {
        r = getchar();
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && !start) continue;
        if ((r - '0' < 0 || r - '0' > 9) && r != '-' && start) break;
        if (start) ret *= 10;
        start = true;
        if (r == '-') neg = true;
        else ret += r - '0';
    }
    if (!neg) return ret;
    else return -ret;
}
 
int generateNext(int number, int maxLen) {
    auto temp = (long long)number * (long long)number;
    while (temp / maxLen != 0) temp /= 10;
    if (temp > max) max = (int)temp;
    return (int)temp;
}
/**************************************************************
    Problem: 1265
    User: 
    Language: C++
    Result: Accepted
    Time:1632 ms
    Memory:1092 kb
****************************************************************/

#include <stdio.h>
 
int generateNext(int number, int maxLen);
 
int max;
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        int digit, number;
        scanf("%d %d", &digit, &number);
        if (number == 0) {
            printf("%d\n", number);
            continue;
        }
        int maxLen = 1;
        while (digit--) maxLen *= 10;
        max = number;
        int slow = generateNext(number, maxLen);
        int fast = generateNext(slow, maxLen);
        while (slow != fast) {
            slow = generateNext(slow, maxLen);
            fast = generateNext(generateNext(fast, maxLen), maxLen);
        }
        printf("%d\n", max);
    }
    return 0;
}
 
int generateNext(int number, int maxLen) {
    long long temp = (long long)number * (long long)number;
    while (temp / maxLen != 0) temp /= 10;
    if (temp > max) max = (int)temp;
    return (int)temp;
}
/**************************************************************
    Problem: 1265
    User: 
    Language: C
    Result: Accepted
    Time:1644 ms
    Memory:1092 kb
****************************************************************/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static int max;
    public static void main(String[] args) {
        InputReader input = new InputReader(System.in);
        int testCase = input.nextInt();
        while (testCase-- > 0) {
            int digit = input.nextInt();
            int number = input.nextInt();
            if (number == 0) {
                System.out.printf("%d\n", number);
                continue;
            }
            int maxLen = 1;
            while (digit-->0) maxLen *= 10;
            max = number;
            int slow = generateNext(number, maxLen);
            int fast = generateNext(slow, maxLen);
            while (slow != fast) {
                slow = generateNext(slow, maxLen);
                fast = generateNext(generateNext(fast, maxLen), maxLen);
            }
            System.out.printf("%d\n", max);
        }
    }
 
    private static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
 
        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
 
    private static int generateNext(int number, int maxLen) {
        long temp = (long)number * (long)number;
        while (temp / maxLen != 0) temp /= 10;
        if (temp > max) max = (int)temp;
        return (int)temp;
    }
}
 
/**************************************************************
    Problem: 1265
    User: 
    Language: Java
    Result: Accepted
    Time:1820 ms
    Memory:19344 kb
****************************************************************/

Problem F: From-now-on minimum difference

Description

Yuki is a clever girl and she is good at mathematics. One day, she gets an array $a$ of $n$ integers: $a_1,a_2,…,a_n$. She wants to know the from-now-on minimum difference of $a_1,a_2,…,a_{n−1}$, and your task is to help her to calculate them. The from-now-on minimum difference of $a_i$, denoted by $h_i$, is defined as: $h_i=min_{j>i}|a_j−a_i|$.

Input

The first line contains one integer: $n$ ($2≤n≤2×10^6$). The second line contains $n$ space-separated integers: $a_1,a_2,…,a_n$ — elements of the array $a$ ($1≤a_i≤10^9$ ).

Output

Print one line with $n−1$ space-separated intergers: $h_1,h_2,…,h_{n−1}$.

Sample Input

1	5
2	1 2 3 4 5

Sample Output

1 1 1 1

HINT

You may solve this problem using some ~~advanced data structures~~. However, it can be solved in a simple and efficient way merely by sorting algorithm\ and linked list\.

Please note that the size of input might be really large, so you might want to use an efficient way to read the input data.

Code

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
struct Node {
    int number;
    Node* next;
    Node* previous;
    Node* exNext;
    Node* exPrevious;
    Node(int number) {
        this->number = number;
        this->next= this->previous = this->exNext = this->exPrevious = NULL;
    }
};
 
class linkedList {
public:
    Node* head, * tail, * current;
    linkedList() {
        this->current = this->head = new Node(-1);
        this->tail = new Node(0);
        this->head->next = tail;
        this->tail->previous = head;
    }
 
    void addNode(Node* node) {
        node->next = this->current->next;
        node->previous = this->current;
        this->current->next->previous = node;
        this->current->next = node;
        this->current = node;
    }
};
 
class pairedLinkedList {
public:
    Node* head, * tail, * current;
    pairedLinkedList() {
        this->current = this->head = new Node(-1);
        this->tail = new Node(0);
        this->head->exNext = tail;
        this->tail->exPrevious = head;
    }
 
    pairedLinkedList(Node* head, Node* tail) {
        this->current = this->head = head;
        this->tail = tail;
        head->exNext = tail;
        tail->exPrevious = head;
    }
 
    void addNode(Node* node) {
        node->exNext = this->current->exNext;
        node->exPrevious = this->current;
        this->current->exNext->exPrevious = node;
        this->current->exNext = node;
        this->current = node;
    }
};
 
int readInt();
bool compare(Node* n1, Node* n2);
 
Node* index[2000000];
 
int main() {
    int len = readInt();
    linkedList rigion = linkedList();
    for (int i = 0; i < len; i++) {
        index[i] = new Node(readInt());
        rigion.addNode(index[i]);
    }
    std::sort(index, index + len, compare);
    pairedLinkedList sortedL = pairedLinkedList(rigion.head, rigion.tail);
    for (int i = 0; i < len; i++) sortedL.addNode(index[i]);
    for (Node* i = rigion.head->next, *temp; i->next->next!=NULL; i = temp) {
        temp = i->next;
        if (i->exPrevious == sortedL.head) printf("%d ", i->exNext->number - i->number);
        else if (i->exNext == sortedL.tail) printf("%d ", i->number - i->exPrevious->number);
        else if (i->number - i->exPrevious->number > i->exNext->number - i->number) printf("%d ", i->exNext->number - i->number);
        else printf("%d ", i->number - i->exPrevious->number);
        i->next->previous = i->previous;
        i->previous->next = i->next;
        i->exNext->exPrevious = i->exPrevious;
        i->exPrevious->exNext = i->exNext;
        delete(i);
    }
    return 0;
}
 
int readInt() {
    int num = 0;
    char l = getchar();
    bool sign = false, negative = false;
    switch (l) {
    case '-': negative = true;
    case '+': sign = true;
    }
    if (sign) l = getchar();
    while ('0' <= l && l <= '9') {
        num = num * 10 + l - '0';
        l = getchar();
    }
    if (negative) return -num;
    return num;
}
 
bool compare(Node* n1, Node* n2) {
    return n1->number < n2->number;
}
/**************************************************************
    Problem: 1266
    User: 
    Language: C++
    Result: Accepted
    Time:1360 ms
    Memory:110568 kb
****************************************************************/

Problem G: Gnisrever

Description

Narnal loves reversing and Fibonacci sequence. When he gets an array with length $N$, he would reverse the array in the intervals determined by Fibonacci sequence for $K$ times.

Let $F_n$ is the $n$-th Fibonacci number: $F_1=F_2=1,F_n=F_{n−1}+F_{n−2}$ for all $n≥3$.

Let $s_n=F_{2n−1} mod N$ and let $t_n=F_{2n} mod N$.

Narnal’s reversing always starts with an array of integers $A=(A[0],…,A[N−1])$ where initially every $A[i]$ is equal to $i$. Now perform $K$ successive operations on $A$, where the $j$-th operation consists of reversing the order of those elements in $A$ with indices between $s_j$ and $t_j$ (both ends inclusive).

Finally, Narnal’s happiness is defined as $R(N,K)=\sum_{i=0}^{N-1}i*A[i]$ after $K$ operations.

$1≤N≤10^{15},1≤K≤5×10^3$.

Input

One line gives $N$ and $K$, separated by space.

Output

One line with only $R(N,K) mod 10^6$.

Sample Input

5 4

Sample Output

HINT

Consider using nodes to represent the sequences of consecutive numbers.

Using linked list reversing!

$R(5,4)=27$ can be seen from the following procedure:
Initial position: $(0,1,2,3,4)$
Step 1 - Reverse $A[1]$ to $A[1]$: $(0,1,2,3,4)$
Step 2 - Reverse $A[2]$ to $A[3]$: $(0,1,3,2,4)$
Step 3 - Reverse $A[0]$ to $A[3]$: $(2,3,1,0,4)$
Step 4 - Reverse $A[3]$ to$A[1]$: $(2,0,1,3,4)$
$R(5,4)=0×2+1×0+2×1+3×3+4×4=27$.
Also, $R(10^2,10^2)=246597$.

Lab4_Stack_and_Queue

Problem A: Magic Queue

Description

IceRuler likes Queues. So he gives you an empty queue initially and some operations on this queue.

The operations contains:

E x Enqueue x
D Dequeue
A Print the head of the queue.

Finally, You should output all elements in the queue after all operations.

Input

There is only one testcase. The first line is integer n, the number of operations. ($1 \leq n \leq 20000000$) Then n lines for these operations, x in int range.

Output

Do each operation, if it is type ‘A’, print current queue head in one line. After doing all operations, output the final queue elements in one line, if the queue is empty, print nothing. It is guaranteed that all operations are legal.

Sample Input

1	7
2	E 1
3	E 2
4	E 3
5	A
6	D
7	E 1
8	A

Sample Output

1	1
2	2
3	2 3 1

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
struct Node {
    int number;
    Node* next;
    Node* previous;
    Node(int number) {
        this->number = number;
        this->next = this->previous = NULL;
    }
};
 
class Queue {
private:
    Node* head, * tail;
    void addNode(Node* node) {
        node->next = this->tail;
        node->previous = this->tail->previous;
        node->next->previous = node;
        node->previous->next = node;
    }
 
    void deleteNode(Node* node) {
        node->next->previous = node->previous;
        node->previous->next = node->next;
        delete(node);
    }
 
public:
    Queue() {
        this->head = new Node(-1);
        this->tail = new Node(0);
        this->head->next = tail;
        this->tail->previous = head;
    }
 
    void enQueue(int n) { this->addNode(new Node(n)); }
 
    int deQueue() {
        int ret = this->head->next->number;
        this->deleteNode(this->head->next);
        return ret;
    }
 
    int getHead() { return this->head->next->number; }
 
    void print() {
        for (Node* i = this->head->next; i->next != NULL; i = i->next) printf("%d ", i->number);
        printf("\n");
    }
};
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    Queue queue = Queue();
    while (testCase--) {
        char c[2];
        scanf("%s", &c);
        switch (c[0]) {
        case 'E': {
            int i;
            scanf("%d", &i);
            queue.enQueue(i);
            break;
        }
        case 'D': {
            queue.deQueue();
            break;
        }
        case 'A': printf("%d\n", queue.getHead());
        }
    }
    queue.print();
    return 0;
}
 
/**************************************************************
    Problem: 1269
    User: 
    Language: C++
    Result: Accepted
    Time:504 ms
    Memory:1216 kb
****************************************************************/

Problem B: Magic brackets

Description

IceRuler likes Brackets. He has n brackets sequences. And you should tell him whether they are matched. The brackets will only contain {, }, (, ), [, ]. The matching rules are the same as in Math.

Input

The first line is integer $T$, the number of test cases ($1 \leq T \leq 20$). For each test case, there is an integer n in one line($1 \leq n \leq 30000$) and $n$ lines means $n$ brackets sequences.

Output

For each brackets sequences, print “YES” if it is matched. Otherwise, print “NO”.

Sample Input

1	7
2	1
3	(
4	2
5	()
6	2
7	{]
8	6
9	[(){}]
10	4
11	(])[
12	8
13	[[{{}}]]
14	6
15	[][{]]

Sample Output

NO
YES
NO
YES
NO
YES
NO

HINT

Origin pro.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stack>
 
using namespace std;
 
char getBracket();
char getPair(char c);
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        int len;
        scanf("%d", &len);
        char c;
        if (len == 1) {
            c = getBracket();
            printf("NO\n");
            continue;
        }
        std::stack<char> brackets;
        bool hasRight = false;
        while (len--) {
            c = getBracket();
            switch (c) {
            case ')':
            case ']':
            case '}': {
                if (brackets.empty()) {
                    hasRight = true;
                    break;
                }
                if (getPair(c) == brackets.top()) brackets.pop();
                else hasRight = true;
                break;
            }
            case '(':
            case '[':
            case '{': brackets.push(c);
            }
        }
        if(!hasRight && brackets.empty()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
 
bool isBracket(char c) {
    return c == '(' || c == '[' || c == '{' || c == ')' || c == ']' || c == '}';
}
 
char getBracket() {
    char c = getchar();
    while (!isBracket(c)) c = getchar();
    return c;
}
 
char getPair(char c) {
    switch (c) {
    case '(': return ')';
    case ')': return '(';
    case '[': return ']';
    case ']': return '[';
    case '{': return '}';
    case '}': return '{';
    default: return ' ';
    }
}
/**************************************************************
    Problem: 1214
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1252 kb
****************************************************************/

Problem C: Magic Sequences

Description

IceRuler has a sequence $A = [a_1,a_2,…,a_n]$. With a magic number m, he wants you to tell him the maximum element in these intervals $[a_1,..a_m], [a_2,…a_{m+1}],…[a_{n-m+1},…,a_n]$.

Input

The first line is the magic number m. The second line contains n integers, where the $i$th integer represents the integer ai. Input ends with a number -1. Constraints: $1 ≤ m < n$ $1 ≤ n ≤ 2000000$ $0 ≤ a_i ≤ 1000000000$

Output

Print one integer K in one line, represents the XOR sum of the maximum elements in $a[i]..a[i +m-1]$s. $K = the max number in [a1,..am] ⊕ the max number in [a2,..am+1] …….⊕ the max number in [an-m+1,..an]$. ⊕ is the bit operation exclusive OR.

Sample Input

1	5
2	121 123 122 13 12 12 52 2 6 7 32 7 324 34 124 213 214 1412 -1

Sample Output

HINT

Easy pro.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <deque>
 
using namespace std;
 
int main() {
    int size;
    scanf("%d", &size);
    int XORsum = 0;
    deque<int> window;
    deque<int> INDEX;
    int index = 0;
    int t;
    scanf("%d", &t);
    for (; index < size; index++) {
        while (!window.empty() && t > window.back()) {
            window.pop_back();
            INDEX.pop_back();
        }
        window.push_back(t);
        INDEX.push_back(index);
        scanf("%d", &t);
    }
    XORsum ^= window.front();
    while (t != -1) {
        while (!window.empty() && t > window.back()) {
            window.pop_back();
            INDEX.pop_back();
        }
        if (!INDEX.empty() && INDEX.front() <= index - size) {
            INDEX.pop_front();
            window.pop_front();
        }
        window.push_back(t);
        INDEX.push_back(index);
        XORsum ^= window.front();
        scanf("%d", &t);
        index++;
    }
    printf("%d\n", XORsum);
    return 0;
}
 
/**************************************************************
    Problem: 1215
    User: 
    Language: C++
    Result: Accepted
    Time:324 ms
    Memory:1252 kb
****************************************************************/

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        Deque<Integer> window = new LinkedList<>();
        Deque<Integer> indexs = new LinkedList<>();
        int size = input.nextInt();
        int n = input.nextInt();
        int index = 0;
        int XORsum = 0;
        for (; index < size; index++) {
            while(!window.isEmpty() && n > window.getLast()) {
                window.pollLast();
                indexs.pollLast();
            }
            window.addLast(n);
            indexs.addLast(index);
            n = input.nextInt();
        }
        XORsum ^= window.getFirst();
        while(n != -1) {
            while(!window.isEmpty() && n > window.getLast()) {
                window.pollLast();
                indexs.pollLast();
            }
            if(!indexs.isEmpty() && indexs.getFirst() <= index - size) {
                window.pollFirst();
                indexs.pollFirst();
            }
            window.addLast(n);
            indexs.addLast(index);
            XORsum ^= window.getFirst();
            n = input.nextInt();
            index++;
        }
        System.out.printf("%d\n", XORsum);
    }
}
 
/**************************************************************
    Problem: 1215
    User: 
    Language: Java
    Result: Accepted
    Time:1648 ms
    Memory:47180 kb
****************************************************************/

Problem D: Exciting Spider

Description

Ancient Spider is a very popular card game, and Vince loves to play it. Today he wants to play Ancient Spider again, but he changes the rule to make it more exciting. At the beginning of the game, Vince has an empty slot on the table. There are n different cards numbered from 1 to n, and Vince will receive them one by one in a given order and put the cards onto the top of the slot. At any time, Vince can pick up a card from the top of slot and discard it. If Vince discards all n cards, the game is over. Vince wants you to help him find the smallest lexicographical order among all possible discarding orders at the end of the game.
If you don’t know the concept of lexicographical order, you can see the reference in the following link: https://en.wikipedia.org/wiki/Lexicographical_order

Input

The first line is an integer $T$, which is the number of test cases.
Each test case contains two lines. The first line has an integer, $n$.
The second line contains a sequence A of length n, which is a permutation of 1 to n, representing the order Vince receives the cards.
($1\leq T\leq5, 1\leq n\leq 300000$)

Output

For each test case, print n integers in a line, which is the order discarding the card with the smallest lexicographical order.

Sample Input

1	2
2	3
3	1 3 2
4	4
5	3 4 1 2

Sample Output

1	1 2 3
2	1 2 4 3

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stack>
#include <queue>
 
using namespace std;
 
bool isUsed[300001];
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        stack<int> slot;
        queue<int> pile;
        int size;
        scanf("%d", &size);
        for (int i = 0; i < size; i++) isUsed[i] = false;
        int t;
        int index = 0;
        scanf("%d", &t);
        while (t != 1) {
            slot.push(t);
            isUsed[t] = true;
            scanf("%d", &t);
            index++;
        }
        int toSearch = 1;
        while (index < size) {
            if (!slot.empty() && toSearch > slot.top()) {
                pile.push(slot.top());
                slot.pop();
            }
            else if (isUsed[toSearch]) {
                if (toSearch != slot.top()) {
                    toSearch++;
                    continue;
                }
                else {
                    toSearch++;
                    pile.push(slot.top());
                    slot.pop();
                }
            }
            else {
                slot.push(t);
                isUsed[t] = true;
                if(index < size - 1) scanf("%d", &t);
                index++;
            }
        }
        while (!slot.empty()) {
            pile.push(slot.top());
            slot.pop();
        }
        while (!pile.empty()) {
            printf("%d ", pile.front());
            pile.pop();
        }
        printf("\n");
    }
    return 0;
}
 
/**************************************************************
    Problem: 1175
    User: 
    Language: C++
    Result: Accepted
    Time:472 ms
    Memory:2756 kb
****************************************************************/

Problem E: Magic Number

Description

There is a queue of n students, indexed from 1 to n from left to right. The height of every student has been given. Because students are standing on one stright line, for every student Ai in the queue, he can only see whom between him and the first student which is taller than him whether he looks left or right. Today teacher wants every student to find two partners, who are the highest one the student can see when he looks left and right respectively. Please help students find their partners. Notice that for every student the partners must shorter than himself.

Input

The first line is integer $T$ ($1≤T≤1000$), the number of test cases. Each test case consists of two lines. The first line is an integer $n$ ($0< n \leq 50000$) which represents the number of students. The second line lists the heights of students from left to right. It is guaranteed that heights of students are less than $2^{31} – 1$ and no two students share the same height in one queue.

Output

For each case, print the case number in one line. Then for every student in the testcase, print the index of his two partners in one line seprated by whitespace. If the eligible partner can not be found, the index should be 0. For example, for the student of height 5 in first testcase, he can not see anyone on his left so he can not find left parter and index should be 0. And because he is the highest one in the queue, he can see all the others on his right and the tallest one will be chosen as his right partner. so he choose the student with height 4 and index 3.

Sample Input

1	2
2	5
3	5 2 4 3 1
4	5
5	2 1 4 3 5

Sample Output

1	Case 1:
2	0 3
3	0 0
4	2 4
5	0 5
6	0 0
7	Case 2:
8	0 2
9	0 0
10	1 4
11	0 0
12	3 0

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stack>
#include <queue>
 
using namespace std;
 
int seq[50001];
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    for (int tc = 1; tc <= testCase; tc++) {
        int size;
        scanf("%d", &size);
        for (int i = 1; i <= size; i++) scanf("%d", &seq[i]);
        printf("Case %d:\n", tc);
        stack<int> list;
        queue<int> left;
        for (int i = 1; i <= size; i++) {
            if (list.empty()) {
                list.push(i);
                left.push(0);
            }
            else {
                int aibo = 0;
                while (!list.empty() && seq[list.top()] < seq[i]) {
                    aibo = list.top();
                    list.pop();
                }
                list.push(i);
                left.push(aibo);
            }
        }
        while (!list.empty()) list.pop();
        stack<int> right;
        for (int i = size; i >= 1; i--) {
            if (list.empty()) {
                list.push(i);
                right.push(0);
            }
            else {
                int aibo = 0;
                while (!list.empty() && seq[list.top()] < seq[i]) {
                    aibo = list.top();
                    list.pop();
                }
                list.push(i);
                right.push(aibo);
            }
        }
        while (!right.empty()) {
            printf("%d %d\n", left.front(), right.top());
            left.pop();
            right.pop();
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1270
    User: 
    Language: C++
    Result: Accepted
    Time:912 ms
    Memory:1452 kb
****************************************************************/

Problem F: Magic Matrix

Description

A matrix is magic , if the difference between its maxmium and mimimum elements ≤ m. IceRuler has a large N×N matrix M. He would like to know size of the biggest magic sub-matrix of M.

Input

Input contains multiple testcases. The first line of Input contains a single integer $T$ ($1≤T≤1000$).The number of testcases. For each case，first line contains two numbers $N$ ($1≤N≤500$) and $M$($0≤M≤100000$)，represent the given matrix is $N$ square matrix and magic equilibrium value is $M$. Each of the next $N$ rows contains $N$ integers, representing the large matrix. Elements are positive integers and not larger than $10^5$ . It is guaranteed that the sum of $N^3$ for all testcases is not exceed $2⋅10^8$.

Output

For each case, print size of the biggest magic sub-matrix of M in one line.

Sample Input

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

Sample Output

1	2
2	4

Problem G: Magic Calculator

Description

IceRuler has a magic calculator. It can calculate the answers for expressions, with constants only containing integers in the range 0-9 and operators only appearing in the following table.

Priority Level	Operator	Name	Combination Law
1	()	Bracket
2	+	Positive Sign	Right to left
	-	Negative Sign
	~	Bitwise Not
3	*	Multiplication	Left to Right
4	+	Addition	Left to Right
	-	Subtraction	Left to Right
5	&	Bitwise And	Left to Right
6	^	Bitwise Xor	Left to Right
7	\		Bitwise Or	Left to Right

Operators will be operated following their priority levels. For example, in 1+2&3, addition will be calculated first, then bitwise and. For 1-+2, positive sign will be calculated first, then subtraction.
Operators with same priority level will be operated following the combination law. For example, in 1+2-3, the combination law of addition and subtraction is “Left to Right”, addition should be calculated first, then subtraction. In -~1 , bitwisenot will be calculated first, then negative sign.
The expressions uses 32-bits signed integer type in the calculate process. You do not need to consider type conversion and overflow processing. For example, the result of ~1 should be -2, and the result of multiplying 2 by 32 times should be 0.
Please write a program to simulate the IceRuler’s calculator. Given expressions, you are required to return the results of this calculator.

Input

Integer $T$ in one line means testcases ($1≤T≤1000000$). For each case，you are given an expression in one line, and you should print its result in one line. The length of each expression is not exceed 50.

Output

You should print result of each expression in one line.

Sample Input

1	3
2	3&(2\|1)
3	+-~3
4	2222222222222222222222222222222*2

Sample Output

1	3
2	4
3	0

Lab5_String

Problem A: How many substrings

Description

Give you a string, you should print how many none empty substrings it has.

Input

The first line is number of tests. $T$ ($1 \leq T \leq 10$)

The second line is a string S. The length of S doesn’t exceed $1000$, that is $|S| \leq 1000$

S will only contain lower case English letters.

Output

For each test, you should print an integer in a single line, which is the number of none empty substrings of S.

Sample Input

1	1
2	hello

Sample Output

HINT

Easy problem.

Code

1	#define _CRT_SECURE_NO_WARNINGS
2	#include <stdio.h>
3
4	using namespace std;
5
6	int main() {
7	int testCase;
8	scanf("%d", &testCase);
9	while (testCase--) {
10	char str[1000];
11	scanf("%s", &str);
12	int len = 0;
13	while (str[len++] != '\0');
14	len -= 1;
15	printf("%d\n", (1 + len) * len / 2);
16	}
17	return 0;
18	}
19
20	/**************************************************************
21	Problem: 1045
22	User:
23	Language: C++
24	Result: Accepted
25	Time:0 ms
26	Memory:1092 kb
27	****************************************************************/

Problem B: Matching Problem [Easy]

Description

Hong haves two strings s and t. The length of the string s equals n, the length of the string t equals m. The string s consists of lowercase letters and at most one wildcard character ‘*’, while the string t consists only of lowercase letters.

The wildcard character ‘‘ in the string s (if any) can be replaced with an arbitrary sequence (possibly void sequence) of lowercase letters. If it is possible to replace a wildcard character ‘‘ in s to obtain a string t, then the string t matches the pattern s.

If the given string t matches the given string s, print “YES”, otherwise print “NO”.

Input

The first line will be an integer $T$ ($1≤T≤10$), which is the number of test cases.

For each test data:

The first line contains two integers $n$ and $m$ ($1≤n, m≤2⋅10^5$) — the length of the string s and the length of the string t, respectively.

The second line contains string s of length n, which consists of lowercase letters and at most one wildcard character ‘*’.

The third line contains string t of length m, which consists only of lowercase letters.

Output

For each test cases, print “YES” (without quotes), if you can obtain the string t from the string s. Otherwise print “NO” (without quotes).

Sample Input

1	1
2	7 10
3	aba*aba
4	abazzzzaba

Sample Output

YES

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        int str0len, str1len;
        scanf("%d %d", &str0len, &str1len);
        char* str0 = new char[str0len+1];
        char* str1 = new char[str1len+1];
        scanf("%s", str0);
        scanf("%s", str1);
        if (str0len - str1len > 1) {
            printf("%s\n", "NO");
            continue;
        }
        int position = -1;
        bool isSame = true;
        while (position < str0len - 1 && str0[++position] != '*');
        if (position == str0len - 1 && str0[str0len - 1] != '*') {
            if (str0len != str1len) isSame = false;
            for (int i = 0; i < str0len; i++) {
                if (str0[i] != str1[i]) {
                    isSame = false;
                    break;
                }
            }
        }
        else {
            for (int i = 0; i < position; i++) {
                if (str0[i] != str1[i]) {
                    isSame = false;
                    break;
                }
            }
            for (int i = str0len - 1, j = str1len - 1; i > position; i--, j--) {
                if (str0[i] != str1[j]) {
                    isSame = false;
                    break;
                }
            }
        }
        if(isSame) printf("%s\n", "YES");
        else  printf("%s\n", "NO");
        delete[] str0;
        delete[] str1;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1146
    User: 
    Language: C++
    Result: Accepted
    Time:12 ms
    Memory:1596 kb
****************************************************************/

Problem C: Repeat!

Description

Amayama finds that some “repeaters” have joined the computer science group. However, these people seem to update to the unordinary repeaters who only repeat part of the last sentence. Now, Amayama published some sentences in the group, and he wishes you to check out the number of “repeaters” who repeat him. He believes that if a person publishes a sentence that contains the prefix of the last one sentence, and this prefix is at least one-third the length of the last sentence (round up, e.g. for 100 then at least 34), then he is a “repeater”.

Input

The first line contains a number $N$, which is the number of suspicious accounts. ($1\leq N\leq 1000$) Then there are $2*N$ lines.

The $2*i-1$ line is a string s, which is the sentence published by Amayama. ($1\leq |s|\leq 10000$)

The $2*i$ line is a string p, which is the sentence published by a suspicious account. ($1\leq |p|\leq 10000$)

Output

The output contains an integer, which is the number of repeaters.

Sample Input

2 
lanranwudi 
lanranwudi 
aaa
bbcc

Sample Output

HINT

The prefix of a string means a substring which must start from the first letter.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
char saying[10001];
char response[10001];
int nextSeq[3400];
 
//int fastRead_string(char* str);
void generateNext(char* str);
bool KMP(char* matcher, int matcherLen, char* pattern);
 
int getLen(char* str) {
    int i = 0;
    while (str[i++] != '\0');
    return i - 1;
}
 
int main() {
    int suspicious;
    scanf("%d", &suspicious);
    int repeaters = 0;
    while (suspicious--) {
        //int sayingLen = fastRead_string(saying);
        //int responseLen = fastRead_string(response);
        scanf("%s", saying);
        int sayingLen = getLen(saying);
        scanf("%s", response);
        int responseLen = getLen(response);
        nextSeq[0] = sayingLen / 3 + ((sayingLen % 3 == 0) ? 0 : 1);
        generateNext(saying);
        if (KMP(response, responseLen, saying)) repeaters += 1;
    }
    printf("%d\n", repeaters);
    return 0;
}
 
/*
int fastRead_string(char* str) {
    char c;
    int i = 0;
    do c = getchar(); while (c < 33);
    while (c != ' ' && c != '\n' && c != '\r' && c != '\t') {
        str[i] = c;
        c = getchar();
        i += 1;
    }
    str[i] = '\0';
    return i;
}
*/
 
/*
void generateNext(char* str) {
    nextSeq[1] = 0;
    for (int i = 2, j = 0; i <= nextSeq[0];) {
        if (j == 0 || str[i - 1] == str[j - 1]) nextSeq[i++] = j++;
        else j = nextSeq[j];
    }
}
*/
 
void generateNext(char* str) {
    nextSeq[1] = 0;
    for (int i = 2, j = 0; i <= nextSeq[0]; i++) {
        while (j > 0 && str[j] != str[i - 1]) j = nextSeq[j];
        if (str[j] == str[i - 1]) j += 1;
        nextSeq[i] = j;
    }
}
 
bool KMP(char* matcher, int matcherLen, char* pattern) {
    for (int i = 0, j = 0; i < matcherLen; i++) {
        while (j > 0 && matcher[i] != pattern[j]) j = nextSeq[j];
        if (matcher[i] == pattern[j]) j += 1;
        if (j == nextSeq[0]) return true;
    }
    return false;
}
/**************************************************************
    Problem: 1271
    User: 
    Language: C++
    Result: Accepted
    Time:164 ms
    Memory:1124 kb
****************************************************************/

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int suspicious = input.nextInt();
        int repeaters = 0;
        while (suspicious-->0) {
            String saying = input.next();
            String response = input.next();
            int[] nextSeq = new int[saying.length() / 3 + ((saying.length() % 3 == 0) ? 1 : 2)];
            nextSeq[0] = nextSeq.length - 1;
            String pattern = saying.substring(0, nextSeq.length);
            generateNext(nextSeq, pattern);
            if(KMP(response, pattern, nextSeq)) repeaters += 1;
        }
        input.close();
        System.out.printf("%d\n", repeaters);
    }
 
    private static void generateNext(int[] nextSeq, String str) {
        nextSeq[1] = 0;
        for(int k = 0, j = 2; j <= nextSeq[0]; j++) {
            while (k > 0 && str.charAt(k) != str.charAt(j-1)) k = nextSeq[k];
            if (str.charAt(k) == str.charAt(j-1)) k += 1;
            nextSeq[j] = k;
        }
    }
 
    private static boolean KMP(String matcher, String pattern, int[] nextSeq) {
        int q = 0;
        for(int i = 0; i < matcher.length(); i++) {
            while (q > 0 && matcher.charAt(i) != pattern.charAt(q)) q = nextSeq[q];
            if(matcher.charAt(i) == pattern.charAt(q)) q += 1;
            if(q == nextSeq[0]) return true;
        }
        return false;
    }
}
 
/**************************************************************
    Problem: 1271
    User: 
    Language: Java
    Result: Accepted
    Time:864 ms
    Memory:26232 kb
****************************************************************/

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int suspicious = input.nextInt();
        int repeaters = 0;
        while (suspicious-->0) {
            String saying = input.next();
            String response = input.next();
            Pattern pattern = Pattern.compile(saying.substring(0, saying.length() / 3 + ((saying.length() % 3 == 0) ? 0 : 1)));
            Matcher matcher = pattern.matcher(response);
            if (matcher.find()) repeaters += 1;
        }
        input.close();
        System.out.printf("%d\n", repeaters);
    }
}
 
/**************************************************************
    Problem: 1271
    User: 
    Language: Java
    Result: Accepted
    Time:996 ms
    Memory:43376 kb
****************************************************************/

Problem D: Necklace!

Description

D1rtyPaw5 wants to drink coco with his girlfriend! Unfortunately, he has no girlfriend now, but he still wishes to prepare a necklace for his future goddess.

This is a kind of special necklace which contains a sequence of diamonds with letters in, and it can be regarded as a string. D1rtyPaw5 gives Amayama a semi-finished necklace and askes Amayama to add as few as possible diamonds to the head or tail of the necklace to make the necklace consist of at least two same circulation sections. A circulation section of a string is a substring which could build the original string by repeating the circulation section several times.

Please answer the number of diamonds that Amayama should add.

Input

The first line contains an integer n, which is the number of test cases. ($1\leq n\leq1000$)

For each case, there is only one line of string containing lowercase letters, which indicates the semi-finished necklace. The length of each string is no more than 200000.

Output

The output for each test case is an integer which is the number of diamonds that Amayama should add.

Sample Input

1	2
2	wawawa
3	failed

Sample Output

1	0
2	6

HINT

If a necklace has contained two circulation sections and ended with an uncomplete circulation section, you should complete this section to finish the whole necklace.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
char necklace[200001];
int nextSeq[200001];
 
int getLen(char* str);
void generateNext(char* str);
int getInFirstSeq(int index);
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        scanf("%s", necklace);
        nextSeq[0] = getLen(necklace);
        generateNext(necklace);
        printf("%d\n", nextSeq[0] - nextSeq[nextSeq[0]] - getInFirstSeq(nextSeq[0]));
    }
    return 0;
}
 
int getLen(char* str) {
    int i = 0;
    while (str[i++] != '\0');
    return i - 1;
}
 
void generateNext(char* str) {
    nextSeq[1] = 0;
    for (int i = 2, j = 0; i <= nextSeq[0]; i++) {
        while (j > 0 && str[j] != str[i - 1]) j = nextSeq[j];
        if (str[j] == str[i - 1]) j += 1;
        nextSeq[i] = j;
    }
}
 
int getInFirstSeq(int index) {
    if (nextSeq[index] == 0 && index == nextSeq[0]) return 0;
    else if (index <= nextSeq[0] - nextSeq[nextSeq[0]]) return index;
    else return getInFirstSeq(nextSeq[index]);
}
/**************************************************************
    Problem: 1274
    User: 
    Language: C++
    Result: Accepted
    Time:92 ms
    Memory:2068 kb
****************************************************************/

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int testCase = input.nextInt();
        while(testCase-->0) {
            String necklace = input.next();
            int[] nextSeq = new int[necklace.length()+1];
            nextSeq[0] = nextSeq.length - 1;
            generateNext(nextSeq, necklace);
            System.out.printf("%d\n", nextSeq[0] - nextSeq[nextSeq[0]] - getInFirstSeq(nextSeq, nextSeq[0]));
        }
        input.close();
    }
 
    private static void generateNext(int[] nextSeq, String str) {
        nextSeq[1] = 0;
        for(int k = 0, j = 2; j <= nextSeq[0]; j++) {
            while (k > 0 && str.charAt(k) != str.charAt(j-1)) k = nextSeq[k];
            if (str.charAt(k) == str.charAt(j-1)) k += 1;
            nextSeq[j] = k;
        }
    }
 
    private static int getInFirstSeq(int[] nextSeq, int index) {
        if (nextSeq[index] == 0 && index == nextSeq[0]) return 0;
        else if (index <= nextSeq[0] - nextSeq[nextSeq[0]]) return index;
        else return getInFirstSeq(nextSeq, nextSeq[index]);
    }
}
 
/**************************************************************
    Problem: 1274
    User: 
    Language: Java
    Result: Accepted
    Time:708 ms
    Memory:36888 kb
****************************************************************/

Problem E: Stick!

Description

Lovely boys often play stick game. This is a two-player game, which goal is finding the longest common substring of the two players’ names, and the length of it is defined as the stick level. Now, Amayama wants you help him to calculate the stick level between two boys.

Input

The input contains two string s1, s2 ($1\leq|s_1|,|s_2|\leq100000$), which are two lovely boys’ names.

Output

A number stands the sticking level.

Sample Input

1	B.Tang
2	B.Tarjan

Sample Output

HINT

https://en.wikipedia.org/wiki/Universal_hashing#Hashing_strings

Problem F: Resque!

Description

Special spy Oken was caught by the defenders of Narnal country. Before he got caught, Oken tries to send a half-encrypted message to his friend, Secsip. However, due to the obstruction of Amayama, some part of the message was broken. Secsip knows that Oken’s original message is a string, and he also knows the first half of the original message is an encryption of the second half using substitution cipher. The substitution cipher is a method of encrypting which replaces each letter in a string to another corresponding fixed letter in a bijection table which is known by Secsip. Now, Secsip receives the broken message, and he knows a suffix (which length could be 0) of the second half of the original message has been lost. He wishes to recover this lost suffix as short as possible.

A suffix of a string is a substring which ends with the last letter.

Input

The first line is the code table for the substitution cipher, which contains 26 letters representing the encrypted letter for each letter in lexicographical order.

The second line is a string which is the Oken’s broken message. The length of the string is no longer than 500000.

All letters in this problem is in lowercase.

Output

An integer which stands the length of second half of Oken’s original message with the lost suffix as short as possible.

Sample Input

1	b c d e f g h i j k l m n o p q r s t u v w x y z a
2	bcdeabc

Sample Output

HINT

For the sample input, the strategy which can recover the second half of the original message as short as possible is to add a “d” at the end of the broken message, so that the second half “abcd” can be encrypted to the first half “bcde” using the given encryption table.

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
char DecryptMap[26];
char EncryptMap[26];
char str[500001];
char hal[250001];
int nextSeq[250001];
 
int getLen(char* str);
char Encrypt(char c);
char Decrypt(char c);
void generateNext(char* str);
int KMP(char* matcher, int matcherLen, char* pattern);
 
int main() {
    for (int i = 0; i < 26; i++) {
        scanf("%s", &str);
        EncryptMap[i] = str[0];
        DecryptMap[str[0] - 'a'] = 'a' + i;
    }
    scanf("%s", str);
    int len = getLen(str);
    nextSeq[0] = len >> 1;
    for (int i = 0; i < nextSeq[0]; i++) hal[i] = Decrypt(str[i]);
    generateNext(hal);
    printf("%d\n", len - KMP(str, len, hal));
    return 0;
}
 
int getLen(char* str) {
    int i = 0;
    while (str[i++] != '\0');
    return i - 1;
}
 
char Encrypt(char c) {
    return EncryptMap[c - 'a'];
}
 
char Decrypt(char c) {
    return DecryptMap[c - 'a'];
}
 
void generateNext(char* str) {
    nextSeq[1] = 0;
    for (int i = 2, j = 0; i <= nextSeq[0]; i++) {
        while (j > 0 && str[j] != str[i - 1]) j = nextSeq[j];
        if (str[j] == str[i - 1]) j += 1;
        nextSeq[i] = j;
    }
}
 
int KMP(char* matcher, int matcherLen, char* pattern) {
    int j = 0;
    for (int i = 0; i < matcherLen; i++) {
        while (j > 0 && matcher[i] != pattern[j]) j = nextSeq[j];
        if (matcher[i] == pattern[j]) j += 1;
    }
    return j;
}
/**************************************************************
    Problem: 1276
    User: 
    Language: C++
    Result: Accepted
    Time:20 ms
    Memory:2800 kb
****************************************************************/

Lab6_Tree

Problem A: K-ary tree

Description

Given a complete K-ary tree with N nodes, please find the number of leaf nodes of this tree.
a K-ary tree is a rooted tree where every internal node has at most K child nodes, a K-ary tree of height h is complete if
- Level 0,1,…,h-1 are all full
- At level h, the leaf nodes are as far left as possible.

Input

The first line will be an integer $T$ ($1≤T≤1000$), which is the number of test cases.
For each test data:
The first line contains two integer $N$ ($2≤N≤108$) and $K$ ($2≤K≤100$) — the number of nodes, and the number child nodes it has at most.

Output

For each test cases, print one line with one integer, the number of leaf nodes of this tree

Sample Input

1	2
2	5 2
3	10 3

Sample Output

1	3
2	7

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
typedef long long int lli;
 
lli makePower(int base, int power) {
    lli res = 1;
    while (power--) res *= base;
    return res;
}
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        lli nodes;
        lli cnodes;
        scanf("%lld %lld", &nodes, &cnodes);
        int level = rint(floor(log2((cnodes - 1) * nodes + 1) / log2(cnodes)));
        int lastLeaf = nodes - (makePower(cnodes, level) - 1) / (cnodes - 1);
        int secondLeaf = makePower(cnodes, level - 1) - rint(ceil(lastLeaf / (double)cnodes));
        printf("%d\n", lastLeaf + secondLeaf);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1277
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1120 kb
****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
 
typedef long long int lli;
 
lli makePower(int base, int power) {
    lli res = 1;
    while (power--) res *= base;
    return res;
}
 
int main() {
    int testCase;
    scanf("%d", &testCase);
    while (testCase--) {
        lli nodes;
        int cnodes;
        scanf("%lld %d", &nodes, &cnodes);
        int level = llrint(floor(log2((cnodes - 1) * nodes + 1) / log2(cnodes)));
        int secondary = (makePower(cnodes, level) - 1) / (cnodes - 1);
        int lastLeaf = nodes - (makePower(cnodes, level) - 1) / (cnodes - 1);
        printf("%d\n", lastLeaf + makePower(cnodes, level - 1) - llrint(ceil(lastLeaf / (double)cnodes)));
    }
    return 0;
}
 
/**************************************************************
    Problem: 1277
    User: 
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:1120 kb
****************************************************************/

Problem B: Find the depth

Description

Given a tree with $N$ nodes and $N-1$ edges, the length of each edge is 1, the root of the tree is node 1, please find the depth of all nodes. the depth for node 1 is 0.

Input

The first line will be a integer $T$ ($1≤T≤10$), which is the number of test cases.
For each test data:
The first line contains an integer $N$ ($1≤N≤10^5$) — the number of nodes.
the next N-1 lines contain two integers $a$ and $b$ ($1≤a,b≤N$), which means there is an edge between node $a$ and $b$.

Output

For each case, print one line with $N$ integers, the $i$-th integer indicates the depth of node i.

Sample Input

1	1
2	4
3	1 2
4	1 3
5	4 2

Sample Output

0 1 1 2

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
 
using namespace std;
 
void Trim(int parent, int node, int level);
vector<int> depth;
vector<vector<int>> Tree;
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int nodes;
        scanf("%i", &nodes);
        Tree.clear();
        Tree.resize(nodes + 1);
        depth.clear();
        depth.resize(nodes + 1);
        depth[0] = nodes;
        nodes -= 1;
        while (nodes--) {
            int a, b;
            scanf("%i %i", &a, &b);
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        Trim(0, 1, -1);
        for (int i = 1; i <= depth[0]; i++) printf("%i ", depth[i]);
        printf("\n");
    }
    return 0;
}
 
void Trim(int parent, int node, int level) {
    level += 1;
    if (Tree[node].size() != 1 || node == 1) {
        for (int i : Tree[node]) {
            if (i != parent) {
                Trim(node, i, level);
            }
        }
    }
    depth[node] = level;
}
 
/**************************************************************
    Problem: 1278
    User: 
    Language: C++
    Result: Accepted
    Time:252 ms
    Memory:9552 kb
****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
 
using namespace std;
 
void Trim(int parent, int node, int level);
//vector<int> depth;
vector<vector<int>> Tree;
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int nodes;
        scanf("%i", &nodes);
        Tree.clear();
        Tree.resize(nodes + 1);
        //depth.clear();
        //depth.resize(nodes + 1);
        //depth[0] = nodes;
        nodes -= 1;
        while (nodes--) {
            int a, b;
            scanf("%i %i", &a, &b);
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        Trim(0, 1, -1);
        //for (int i = 1; i <= depth[0]; i++) printf("%i ", depth[i]);
        for (int i = 1; i < Tree.size(); i++) printf("%i ", Tree[i][0]);
        printf("\n");
    }
    return 0;
}
 
void Trim(int parent, int node, int level) {
    level += 1;
    if (Tree[node].size() != 1 || node == 1) {
        for (int i : Tree[node]) {
            if (i != parent) {
                Trim(node, i, level);
            }
        }
    }
    //depth[node] = level;
    Tree[node].insert(Tree[node].begin(), level);
}
 
/**************************************************************
    Problem: 1278
    User: 
    Language: C++
    Result: Accepted
    Time:352 ms
    Memory:9940 kb
****************************************************************/

Problem C: Pre, in and post

Description

You are given the pre-order and in order traversal of the binary tree, please find the post-order of this tree.

Input

The first line will be an integer $T$ ($1≤T≤10$), which is the number of test cases.
For each test data:
The first line contains one integer $N$ ($1≤N≤10^3$) — the number of nodes of the tree
Then follows two lines:
The first line contains $N$ integers ranging from $1$ to $N$, indicating the pre-order traversal of the tree.
The second line contains $N$ integers ranging from $1$ to $N$, indicating the in-order traversal of the tree.

Output

For each case, contains one line with $N$ integer, the post-order traversal of the tree.

Sample Input

1	1
2	5
3	1 2 4 3 5
4	2 4 1 5 3

Sample Output

4 2 5 3 1

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
using namespace std;
 
int* preOrder;
int* inOrder;
 
void postOrder(int preL, int preR, int inL, int inR);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int n;
        scanf("%i", &n);
        preOrder = new int[n + 1];
        inOrder = new int[n + 1];
        preOrder[0] = inOrder[0] = n;
        for (int i = 1; i <= n; i++) scanf("%i", &preOrder[i]);
        for (int i = 1; i <= n; i++) scanf("%i", &inOrder[i]);
        postOrder(1, n, 1, n);
        printf("\n");
    }
    return 0;
}
 
void postOrder(int preL, int preR, int inL, int inR) {
    if(preL == preR) printf("%i ", inOrder[inR]);
    else if (preL < preR) {
        int root = inL - 1;
        while (preOrder[preL] != inOrder[++root]);
        int leftlen = root - inL;
        postOrder(preL + 1, preL + leftlen, inL, root - 1);
        postOrder(preL + leftlen + 1, preR, root + 1, inR);
        printf("%i ", inOrder[root]);
    }
}
/**************************************************************
    Problem: 1279
    User: 
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1216 kb
****************************************************************/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
 
int* preOrder;
int* inOrder;
 
void postOrder(int preL, int preR, int inL, int inR);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int n;
        scanf("%i", &n);
        preOrder = (int*)calloc(n + 1, sizeof(int));
        inOrder = (int*)calloc(n + 1, sizeof(int));
        preOrder[0] = inOrder[0] = n;
        for (int i = 1; i <= n; i++) scanf("%i", &preOrder[i]);
        for (int i = 1; i <= n; i++) scanf("%i", &inOrder[i]);
        postOrder(1, n, 1, n);
        printf("\n");
        free(preOrder);
        free(inOrder);
    }
    return 0;
}
 
void postOrder(int preL, int preR, int inL, int inR) {
    if (preL == preR) printf("%i ", inOrder[inR]);
    else if (preL < preR) {
        int root = inL - 1;
        while (preOrder[preL] != inOrder[++root]);
        int leftlen = root - inL;
        postOrder(preL + 1, preL + leftlen, inL, root - 1);
        postOrder(preL + leftlen + 1, preR, root + 1, inR);
        printf("%i ", inOrder[root]);
    }
}
/**************************************************************
    Problem: 1279
    User: 
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:1092 kb
****************************************************************/

Problem D: Cut the stick

Description

Lanran wants to cut one stick with length L into exactly N sticks with length $L_i$ ($i=1,2…,N$), so $L=∑L_i$. However, the cost to cut one stick in to two pieces is the length of the stick, that means cutting a stick with length x will cost x. Now he wants to know the minimal cost if he cuts stick optimally to get N sticks.

Input

The first line will be an integer $T$ ($1≤T≤100$), which is the number of test cases.
For each test data:
The first line contains an integer $N$ ($1≤N≤10^3$) — the number of sticks Lanran needs to get.
Then the next one line contains $N$ integers, the $i$-th integer $L_i$ ($1≤p_i≤10^5$) indicates the length of N sticks Lanran wants to get.

Output

For each case, contains one line, print the minimal minimal cost.

Sample Input

1	1
2	4
3	1 4 2 6

Sample Output

Code

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> sticks = new ArrayList<>();
        Scanner input = new Scanner(System.in);
        int testCase = input.nextInt();
        while(testCase-->0) {
            sticks.clear();
            int n = input.nextInt();
            while(n-->0) sticks.add(input.nextInt());
            int sum = 0;
            while(sticks.size() != 1) {
                sticks.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o2 - o1;
                    }
                });
                int tmp = sticks.get(sticks.size() - 1) + sticks.get(sticks.size() - 2);
                sticks.remove(sticks.size() - 1);
                sticks.remove(sticks.size() - 1);
                sticks.add(tmp);
                sum += tmp;
            }
            System.out.printf("%d\n", sum);
        }
    }
}
 
/**************************************************************
    Problem: 1280
    User: 
    Language: Java
    Result: Accepted
    Time:404 ms
    Memory:29132 kb
****************************************************************/

Problem E: Cut a tree

Description

You are given a tree with $N$ nodes. Every node is colored with one color: white, red or blue. For every edge in tree, cutting this edge will get two smaller parts. If one of two smaller parts has no red node and the other one has no blue node, the edge is “valuable”.
It is guaranteed that there is at least one red node and one blue node.
You need to find the number of “valuable” edges.

Input

The first line will be an integer $T$ ($1≤T≤10$), which is the number of test cases.
For each test data:
The first line contains an integer $N$ ($1≤N≤10^5$) — the number of nodes.
The next $N-1$ lines contain two integers $a$ and $b$ ($1≤a,b≤N$), which means there is an edge between node a and b.
Then the next one line contains n integers, the $i$-th integer $p_i$ ($p_i=0,1,2$) indicates the color of node i. If $p_i=0$, the node is white. If $p_i=1$, the node is red. If $p_i=2$, the node is blue.

Output

For each case, contains one line, print the number of these edges.

Sample Input

1	3
2	4
3	1 2
4	2 3
5	2 4
6	1 0 0 2
7	5
8	1 2
9	2 3
10	3 4
11	4 5
12	2 0 0 0 1
13	3
14	1 2
15	2 3
16	1 2 1

Sample Output

1	2
2	4
3	0

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
 
using namespace std;
 
vector<vector<int>> Tree;
int totalColor[3];
vector<vector<int>> nodeColor;
int valuableEdges;
 
void Judge(int parent, int node);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int n;
        scanf("%i", &n);
        Tree.clear();
        Tree.resize(n + 1);
        Tree[0].resize(n + 1);
        Tree[0][0] = n;
        totalColor[0] = totalColor[1] = totalColor[2] = 0;
        nodeColor.clear();
        nodeColor.resize(n + 1);
        for (int i = 1; i < n; i++) {
            int a, b;
            scanf("%i %i", &a, &b);
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%i", &Tree[0][i]);
            totalColor[Tree[0][i]] += 1;
        }
        valuableEdges = 0;
        Judge(0, 1);
        printf("%i\n", valuableEdges);
    }
    return 0;
}
 
void Judge(int parent, int node) {
    nodeColor[node].clear();
    nodeColor[node].resize(3);
    if (Tree[node].size() != 1 || node == 1) {
        for (auto i : Tree[node]) {
            if (i != parent) {
                Judge(node, i);
                nodeColor[node][0] += nodeColor[i][0];
                nodeColor[node][1] += nodeColor[i][1];
                nodeColor[node][2] += nodeColor[i][2];
                if (totalColor[1] == nodeColor[i][1] || totalColor[2] == nodeColor[i][2]) if(nodeColor[i][1] == 0 || nodeColor[i][2] == 0) valuableEdges += 1;
            }
        }
    }
    nodeColor[node][Tree[0][node]] += 1;
}
/**************************************************************
    Problem: 1281
    User: 
    Language: C++
    Result: Accepted
    Time:416 ms
    Memory:14468 kb
****************************************************************/

Problem F: K people travel on a tree

Description

There are N cities numbered from 1 to N and N-1 roads connecting these N cities, or consider it is a tree with N nodes. Each road takes 1 day to travel through. There are K people initially stays at different K cities. They decide to meet at the same city as soon as possible. Please find the minimal time needed.

Input

The first line will be an integer $T$ ($1≤T≤10$), which is the number of test cases.
For each test data:
The first line contains two integers $N$ ($1≤N≤10^5$) and $K$ ($1≤K≤N$) — the number of cities and the number of friends.
The next $N - 1$ lines contain two integers A and B, which means there is a road between city A and city B.
Then the next one line contains $K$ integers, the $i$-th integer $p_i$ indicates the place they initially stay.

Output

For each case, contains one line, print the minimal time.

Sample Input

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

Sample Output

Lab7_Advanced_Tree

Problem A: Complete binary tree [Easy I]

Description

Lanran has a binary tree with $n$ nodes, she does not know whether this tree is a complete binary tree or not. She turns to you for help. We guarantee that the input is a binary tree.

Input

The first line will be an integer $T$, which is the number of the test cases.($1≤T≤14$) For each test case, the first line will be an integer $n$.($1≤n≤150000$)Then followed by $n$ lines, each line will be two integers $x$ and $y$, the $i$-th line means the left child of node $i$ is $x$, the right child of node $i$ is $y$. If node $i$ has no left child, then $x$ will be 0. If node $i$ has no right child, then $y$ will be 0.

Output

For each test output Yes or No in one line.

Sample Input

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

Sample Output

No

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
struct Node {
    bool isRoot;
    Node* left;
    Node* right;
    Node() {
        this->isRoot = true;
        this->left = this->right = NULL;
    }
};
 
bool isCompleteBinaryTree(Node* root);
void deletTree(Node* root);
 
vector<Node*> Tree;
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int n;
        scanf("%i", &n);
        Tree.resize(n + 1);
        for (int i = 0; i <= n; i++) Tree[i] = new Node();
        for (int i = 1, a, b; i <= n; i++) {
            scanf("%i %i", &a, &b);
            Tree[i]->left = Tree[a];
            Tree[i]->right = Tree[b];
            Tree[a]->isRoot = false;
            Tree[b]->isRoot = false;
        }
        Node* root = Tree[0];
        for (int i = 1; i <= n; i++) {
            if (Tree[i]->isRoot) {
                root = Tree[i];
                break;
            }
        }
        if (isCompleteBinaryTree(root)) printf("Yes\n");
        else printf("No\n");
        deletTree(root);
    }
    return 0;
}
 
queue<Node*> shell;
 
bool isCompleteBinaryTree(Node* root) {
    while (!shell.empty()) shell.pop();
    shell.push(root);
    while (!shell.empty()) {
        if (shell.front()->right != Tree[0]) {
            if (shell.front()->left != Tree[0]) {
                shell.push(shell.front()->left);
                shell.push(shell.front()->right);
                shell.pop();
            }
            else return false;
        }
        else {
            if (shell.front()->left != Tree[0]) {
                shell.push(shell.front()->left);
                shell.pop();
            }
            while (!shell.empty()) {
                if (shell.front()->right == Tree[0] && shell.front()->left == Tree[0]) shell.pop();
                else return false;
            }
        }
    }
    return true;
}
 
void deletTree(Node* root) {
    while (!shell.empty()) shell.pop();
    shell.push(root);
    while (!shell.empty()) {
        if (shell.front()->left != Tree[0]) shell.push(shell.front()->left);
        if (shell.front()->right != Tree[0]) shell.push(shell.front()->right);
        delete shell.front();
        shell.pop();
    }
}
/**************************************************************
    Problem: 1121
    User: 
    Language: C++
    Result: Accepted
    Time:524 ms
    Memory:6896 kb
****************************************************************/

Problem B: Judgement [Easy II]

Description

Please judge whether the given tree is a binary heap.

A binary heap is defined as a binary tree with two additional constraints:

Shape property: a binary heap is a complete binary tree
Heap property: the value stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the the values in the node’s children

Input

The first line will be an integer $T$,which is the number of test cases.($1≤T≤10$) For each test case, the first line will be an integer $n$ ($1≤n≤105$).

The second line will be $n$ integers, $a_1,a_2,⋯,a_n$($1≤a_i≤10^9$). $a_i$ represents the value of the $i$-th node, then followed by $n−1$ lines, each line will be two integers $x$ and $y$, which means $y$-th node is a child of $x$-th node. Besides, The left child will appear first (The order of appearance of child nodes is from left to right).

Output

For each test, print the number of the test cases first, then print YES when the tree is a binary heap, else print NO.

We guarantee that $1≤x,y≤n$ and input is a tree.

Sample Input

1	3
2	4
3	1 2 3 4
4	3 1
5	3 4
6	3 2
7	3
8	2 1 3
9	2 1
10	2 3
11	3
12	2 1 3
13	3 1
14	3 2

Sample Output

1	Case #1: NO
2	Case #2: YES
3	Case #3: YES

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int>> Tree;
vector<bool> notRoot;
 
bool minmaxConsist;
int minmax[3];
bool Jugdement(int root);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    for(int tc = 1; tc <= testCase; tc++) {
        int n;
        scanf("%i", &n);
        notRoot.clear();
        notRoot.resize(n + 1);
        Tree.clear();
        Tree.resize(n + 1);
        Tree[0].push_back(n);
        for (int i = 1, tmp; i <= n; i++) {
            scanf("%i", &tmp);
            Tree[i].push_back(tmp);
        }
        for (int a, b; n-->1;) {
            scanf("%i %i", &a, &b);
            Tree[a].push_back(b);
            notRoot[b] = true;
        }
        int root = 0;
        bool isCBT = true;
        for (int i = 1; i <= Tree[0][0]; i++) {
            if(!notRoot[i]) root = i;
            if(Tree[i].size() > 3) isCBT = false;
        }
        if(root == 0 || !isCBT) {
            printf("Case #%i: NO\n", tc);
            continue;
        }
        minmax[0] = minmax[1] = minmax[2] = 0;
        isCBT = Jugdement(root);
        if(isCBT && ((minmax[1] == 0 && minmax[2] != 0) || (minmax[1] != 0 && minmax[2] == 0))) printf("Case #%i: YES\n", tc);
        else printf("Case #%i: NO\n", tc);
    }
    return 0;
}
 
void JudgeMinMax(vector<int>* root) {
    switch (root->size()) {
        case 3: {
            if (Tree[root->at(2)][0] > root->at(0)) minmax[1] += 1;
            else if (Tree[root->at(2)][0] < root->at(0)) minmax[2] += 1;
            else minmax[0] += 1;
        }
        case 2: {
            if (Tree[root->at(1)][0] > root->at(0)) minmax[1] += 1;
            else if (Tree[root->at(1)][0] < root->at(0)) minmax[2] += 1;
            else minmax[0] += 1;
        }
    }
}
 
queue<vector<int>*> shell;
 
bool Jugdement(int root) {
    while (!shell.empty()) shell.pop();
    shell.push(&Tree[root]);
    while (!shell.empty()) {
        switch (shell.front()->size()) {
            case 3:{
                shell.push(&Tree[shell.front()->at(1)]);
                shell.push(&Tree[shell.front()->at(2)]);
                JudgeMinMax(shell.front());
                shell.pop();
                break;
            }
            case 2: {
                shell.push(&Tree[shell.front()->at(1)]);
                JudgeMinMax(shell.front());
                shell.pop();
            }
            case 1: {
                while (!shell.empty()) {
                    if(shell.front()->size() == 1) shell.pop();
                    else return false;
                }
            }
        }
    }
    return true;
}
/**************************************************************
    Problem: 1282
    User: 
    Language: C++
    Result: Accepted
    Time:792 ms
    Memory:7184 kb
****************************************************************/

Problem C: Cut The Stick Pro [Middle I]

Description

Lanran wants to cut one stick with length $L$ into exactly $N$ sticks with length $L_i(i=1,2…N)$, so $L=∑^N_{i=1}Li$. However, the cost to cut one stick into two pieces is the length of the stick, which means cutting a stick with length $x$ will cost $x$. Now he wants to know the minimal cost if he cuts stick optimally to get N sticks.

Input

The first line will be an integer $T$ ($1≤T≤5$), which is the number of test cases.

For each test, the first line contains an integer $N$ ($1≤N≤10^5$) — the number of sticks Lanran needs to get. Then the next line contains $N$ integers, the $i$-th integer $L_i$ ($1≤pi≤10^5$) indicates the length of $N$ sticks Lanran wants to get.

Output

For each case print the minimal cost if Lanran cuts stick optimally to get $N$ sticks.

Sample Input

1	1
2	4
3	1 4 2 6

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
 
using namespace std;
 
typedef long long int lli;
 
priority_queue<lli, vector<lli>, greater<lli>> sticks;
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while (testCase--) {
        int n;
        scanf("%i", &n);
        while (n--) {
            lli tmp;
            scanf("%lli", &tmp);
            sticks.push(tmp);
        }
        lli Ssum = 0;
        while (sticks.size() != 1) {
            lli tmp = sticks.top();
            sticks.pop();
            tmp += sticks.top();
            sticks.pop();
            sticks.push(tmp);
            Ssum += tmp;
        }
        printf("%lli\n", Ssum);
        while(!sticks.empty()) sticks.pop();
    }
    return 0;
}
 
/**************************************************************
    Problem: 1283
    User: 
    Language: C++
    Result: Accepted
    Time:792 ms
    Memory:2788 kb
****************************************************************/

Problem D: Stream Processing [Middle II]

Description

VinceBlack is working on stream processing. There is now an infinite stream of data that can be thought of as producing an integer per second. Your task is to collect each number and then output the current $k$th largest number (for all the numbers collected) every 100 seconds . If the currently collected number is less than $k$, the smallest number is output.

The $k$th largest number indicates that if sorted in descending order, this number will be ranked in the $k$th position.

Input

The input contains three integers $t$ ($100≤t≤10^6$), $k$ ($1≤k≤1000$) and $s$ ($0≤s≤10^5$).

t is the number of seconds you need to process

Define $a(n)=n+sum of the digits of n$, and the number appearing at $i$-th ($i$ starts at 1) second in the data stream is $a(i+last_ans)$.

$last_ans=s$ in the beginning and will be updated after each answer is calculated.

Output

$⌊t/100⌋$ integers in a line, represents the answers in each 100 seconds.

Sample Input

1926 8 17

Sample Output

1	117 319 623 1024 1529 2131 2840 3649 4559 5571 6686 7906 9219 10624 12127 13737 15447 17258 19171

HINT

More information about a(n): ref

Code

1	#define _CRT_SECURE_NO_WARNINGS
2
3	#include <cstdio>
4	#include <queue>
5
6	using namespace std;
7
8	typedef long long int lli;
9
10	lli A062028(lli n);
11
12	int main() {
13	lli t, k, s;
14	scanf("%lli %lli %lli", &t, &k, &s);
15	priority_queue<lli, vector<lli>, greater<lli>> pq;
16	for(int i = 1; i <= t; i++) {
17	auto tmp = A062028(i + s);
18	if(pq.size() < k) pq.push(tmp);
19	else if(tmp > pq.top()) {
20	pq.pop();
21	pq.push(tmp);
22	}
23	if(i % 100 == 0) {
24	printf("%lli ", pq.top());
25	s = pq.top();
26	}
27	}
28	return 0;
29	}
30
31	lli A062028(lli n) {
32	lli res = n;
33	while (n != 0) {
34	res += n % 10;
35	n /= 10;
36	}
37	return res;
38	}
39
40	/**************************************************************
41	Problem: 1285
42	User:
43	Language: C++
44	Result: Accepted
45	Time:508 ms
46	Memory:1252 kb
47	****************************************************************/

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long t = input.nextInt(), k = input.nextInt(), s = input.nextInt();
        Queue<Long> pq = new PriorityQueue<>();
        for(int i = 1; i <= t; i++) {
            long tmp = A062028(i + s);
            if(pq.size() < k) pq.offer(tmp);
            else if(tmp > pq.peek()) {
                pq.poll();
                pq.offer(tmp);
            }
            if(i % 100 == 0) {
                System.out.printf("%d ", pq.peek());
                s = pq.peek();
            }
        }
    }
 
    private static long A062028(long n) {
        long res = n;
        while(n != 0) {
            res += n % 10;
            n /= 10;
        }
        return res;
    }
}
 
/**************************************************************
    Problem: 1285
    User: 
    Language: Java
    Result: Accepted
    Time:816 ms
    Memory:83224 kb
****************************************************************/

Problem E: Nth Element in Sliding Window [Hard I]

Description

Given a sequence $a_1,a_2,⋯,a_m$, there is a sliding window of size $k$ from the very left of the sequence to the very right. You can only see the $k$ numbers in the window. Each time the sliding window moves right by one position.

For each time there is $a_n$ integer $n_i$, you are asked the $n_i$-th element in the window. The $k$-th element indicates that the element will be in the $k$-th position after sorting in ascending order.

Input

The first line contains two integers $m$ and $k$, ($1≤m ≤105,1≤k≤m$)

The second line contains m distinct integers separated by space $a_i$ ($−2147483648≤ai≤2147483647$).

The next line contains $m−k+1$ integers separated by space $n_i$ ($1≤n_i≤k$)

Output

Output $m−k+1$ lines, each line contain a number represented the answer to each window

Sample Input

1	6 3
2	201 91 29 13 11 -5
3	3 1 2 1

Sample Output

1	201
2	13
3	13
4	-5

HINT

Balanced binary search tree

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
typedef long long int lli;
 
class AVLTree {
private:
    struct Node {
        lli key, height, size;
        Node* left, * right;
        explicit Node(lli key) {
            this->key = key;
            this->height = 0;
            this->size = 1;
            this->left = this->right = nullptr;
        }
 
        static lli getHeight(Node* node) {
            if (node == nullptr) return -1;
            return node->height;
        }
 
        static lli getSize(Node* node) {
            if (node == nullptr) return 0;
            return node->size;
        }
 
        void updateSize() { this->size = 1 + getSize(this->left) + getSize(this->right); }
 
        void updateHeight() { this->height = 1 + max(getHeight(this->left), getHeight(this->right)); }
    };
 
    static Node* rotateRight(Node* node) {
        auto tmp = node->left;
        node->left = tmp->right;
        tmp->right = node;
        tmp->size = node->size;
        node->updateSize();
        node->updateHeight();
        tmp->updateHeight();
        return tmp;
    }
 
    static Node* rotateLeft(Node* node) {
        auto tmp = node->right;
        node->right = tmp->left;
        tmp->left = node;
        tmp->size = node->size;
        node->updateSize();
        node->updateHeight();
        tmp->updateHeight();
        return tmp;
    }
 
    static lli getBalanceFactor(Node* node) {
        if(node == nullptr) return 0;
        return Node::getHeight(node->left) - Node::getHeight(node->right);
    }
 
    static Node* balance(Node* node) {
        if (getBalanceFactor(node) < -1) {
            if (getBalanceFactor(node->right) > 0) node->right = rotateRight(node->right);
            node = rotateLeft(node);
        }
        else if (getBalanceFactor(node) > 1) {
            if (getBalanceFactor(node->left) < 0) node->left = rotateLeft(node->left);
            node = rotateRight(node);
        }
        return node;
    }
 
    static Node* add(Node* node, lli key) {
        if (node == nullptr) return new Node(key);
        lli cmp = key - node->key;
        if (cmp < 0) node->left = add(node->left, key);
        else if (cmp > 0) node->right = add(node->right, key);
        node->updateSize();
        node->updateHeight();
        return balance(node);
    }
 
    static Node* min(Node* node) {
        if (node->left == nullptr) return node;
        return min(node->left);
    }
 
    static Node* deleteMin(Node* node) {
        if (node->left == nullptr) return node->right;
        node->left = deleteMin(node->left);
        node->updateSize();
        node->updateHeight();
        return balance(node);
    }
 
    static Node* deleteNode(Node* node, lli key) {
        lli cmp = key - node->key;
        if (cmp < 0) node->left = deleteNode(node->left, key);
        else if (cmp > 0) node->right = deleteNode(node->right, key);
        else {
            if (node->left == nullptr || node->right == nullptr) {
                auto tmp = node->left ? node->left : node->right;
                free(node);
                return tmp;
            }
            else {
                auto tmp = node;
                auto toFree = node;
                node = min(tmp->right);
                node->right = deleteMin(tmp->right);
                node->left = tmp->left;
                free(toFree);
            }
        }
        node->updateSize();
        node->updateHeight();
        return balance(node);
    }
 
    lli find(Node* node, lli index) {
        if(node == nullptr) return 0;
        if(Node::getSize(node->left) > index) return this->find(node->left, index);
        else if(Node::getSize(node->left) < index) return this->find(node->right, index - Node::getSize(node->left) - 1);
        return node->key;
    }
 
    lli size;
    Node* root;
 
public:
    AVLTree() {
        this->size = 0;
        this->root = nullptr;
    }
 
    lli getSize() { return size; }
 
    void add(lli key) {
        this->size += 1;
        if (this->size == 1) this->root = new Node(key);
        else this->root = AVLTree::add(this->root, key);
    }
 
    void deleteNode(lli key) {
        this->size -= 1;
        this->root = AVLTree::deleteNode(this->root, key);
    }
 
    lli find(lli key) { return this->find(this->root, key - 1); }
};
 
int main() {
    int m, k;
    scanf("%i %i", &m,  &k);
    vector<lli> array(m);
    for(lli i = 0; i < m; i++) scanf("%lli", &array[i]);
    AVLTree tree = AVLTree();
    int id;
    for(id = 0; tree.getSize() < k - 1; id++) tree.add(array[id]);
    for(lli tmp; id < m; id++) {
        tree.add(array[id]);
        scanf("%lli", &tmp);
        printf("%lli\n", tree.find(tmp));
        tree.deleteNode(array[id - k + 1]);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1203
    User: 
    Language: C++
    Result: Accepted
    Time:180 ms
    Memory:2428 kb
****************************************************************/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) {
        InputReader input = new InputReader(System.in);
        long m = input.nextInt(), k = input.nextInt();
        long[] array = new long[(int)m];
        for(long i = 0; i < m; i++) array[(int)i] = input.nextLong();
        AVLTree tree = new AVLTree();
        long id;
        for(id = 0; tree.getSize() < k - 1; id++) tree.add(array[(int)id]);
        for(long tmp; id < m; id++){
            tree.add(array[(int)id]);
            tmp = input.nextInt();
            System.out.printf("%d\n", tree.find(tmp));
            tree.delete(array[(int)(id - k + 1)]);
        }
    }
 
    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;
 
        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        private String next() {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                try { tokenizer = new StringTokenizer(reader.readLine()); }
                catch (IOException e) { throw new RuntimeException(e); }
            }
            return tokenizer.nextToken();
        }
 
        public long nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(this.next());
        }
    }
 
    private static class AVLTree {
        private long size;
        private Node root;
 
        AVLTree() {
            this.size = 0;
            this.root = null;
        }
 
        public long getSize() {
            return size;
        }
 
        public void add(long key) {
            this.size += 1;
            if (this.size == 1) this.root = new Node(key);
            else this.root = this.add(this.root, key);
        }
 
        public void delete(long key) {
            if (this.get(key) == null) return;//TODO
            this.size -= 1;
            this.root = this.delete(this.root, key);
        }
 
        private long find(Node node, long index) {
            if(node == null) return 0;
            if(Node.size(node.left) > index) return this.find(node.left, index);
            else if(Node.size(node.left) < index) return this.find(node.right, index - Node.size(node.left) - 1);
            return node.key;
        }
 
        public long find(long key) {
            return this.find(this.root, key - 1);
        }
 
        private static class Node {
            long key, height, size;
            Node left, right;
            Node(long key) {
                this.key = key;
                this.height = 0;
                this.size = 1;
                this.left = this.right = null;
            }
 
            private static long height(Node node) {
                if (node == null) return -1;
                return node.height;
            }
 
            private static long size(Node node) {
                if (node == null) return 0;
                return node.size;
            }
 
            void updateSize() {
                this.size = 1 + size(this.left) + size(this.right);
            }
 
            void updateHeight() {
                this.height = 1 + Math.max(height(this.left), height(this.right));
            }
        }
 
        private Node rotateRight(Node node) {
            Node tmp = node.left;
            node.left = tmp.right;
            tmp.right = node;
            tmp.size = node.size;
            node.updateSize();
            node.updateHeight();
            tmp.updateHeight();
            return tmp;
        }
 
        private Node rotateLeft(Node node) {
            Node tmp = node.right;
            node.right = tmp.left;
            tmp.left = node;
            tmp.size = node.size;
            node.updateSize();
            node.updateHeight();
            tmp.updateHeight();
            return tmp;
        }
 
        private long balanceFactor(Node node) {
            if(node == null) return 0;
            return Node.height(node.left) - Node.height(node.right);
        }
 
        private Node balance(Node node) {
            if (balanceFactor(node) < -1) {
                if (balanceFactor(node.right) > 0) {
                    node.right = rotateRight(node.right);
                }
                node = rotateLeft(node);
            }
            else if (balanceFactor(node) > 1) {
                if (balanceFactor(node.left) < 0) {
                    node.left = rotateLeft(node.left);
                }
                node = rotateRight(node);
            }
            return node;
        }
 
        private Node add(Node node, long key) {
            if (node == null) return new Node(key);
            long cmp = key - node.key;
            if (cmp < 0) {
                node.left = add(node.left, key);
            }
            else if (cmp > 0) {
                node.right = add(node.right, key);
            }
            node.updateSize();
            node.updateHeight();
            return balance(node);
        }
 
        private Node min(Node node) {
            if (node.left == null) return node;
            return min(node.left);
        }
 
        private Node deleteMin(Node node) {
            if (node.left == null) return node.right;
            node.left = deleteMin(node.left);
            node.updateSize();
            node.updateHeight();
            return balance(node);
        }
 
        private Node get(Node x, long key) {
            if (x == null) return null;
            long cmp = key - x.key;
            if (cmp < 0) return get(x.left, key);
            else if (cmp > 0) return get(x.right, key);
            else return x;
        }
 
        public Node get(long key) {
            return get(root, key);
        }
 
        private Node delete(Node node, long key) {
            long cmp = key - node.key;
            if (cmp < 0) node.left = delete(node.left, key);
            else if (cmp > 0) node.right = delete(node.right, key);
            else {
                if (node.left == null) return node.right;
                else if (node.right == null) return node.left;
                else {
                    Node y = node;
                    node = min(y.right);
                    node.right = deleteMin(y.right);
                    node.left = y.left;
                }
            }
            node.updateSize();
            node.updateHeight();
            return balance(node);
        }
    }
}
 
/**************************************************************
    Problem: 1203
    User: 
    Language: Java
    Result: Accepted
    Time:2484 ms
    Memory:180172 kb
****************************************************************/

Problem F: Pet Adoption [Hard II]

Description

Lanran opened a pet adoption center. Each pet has a characteristic value ($0<p<2^{31}$) and each adopter also hash a value $q$ ($0<q<2^{31}$).

Lanran needs to provide the following services:

For a pet with characteristic value $p$ arriving, it will be adopted by a person staying in the center whose $q$ is the minimum closest to $p$ or stay in the center if there is no adopter left.
For an adopter with value $q$ arriving, he/she will choose a pet staying in the center whose $p$ is the minimum closest to $q$ or stay in the center if there is no pet left.

a is the minimum closest to $v$ in set $S$ if and only if:

for all $a_x∈S$ there is $|a−v|≤|a_x−v|$
for all $a_i∈S$ and $|a−v|=|a_i−v|$ there is $a≤a_i$

the dissatisfaction for each adoption is defined as $|p−q|$

Input

The first line is a positive integer $n$ ($n≤80000$), which represents the total number of pets and adopters who come to the adoption center. The next n lines describe the pets and adopters who came to the adoption center in the order of arrival. Each line has two positive integers $a$, $b$, where $a=0$ for pets, $a=1$ for adopters, and b for character values.

Output

A positive integer representing the sum of the dissatisfaction of all adopted adopters of pets.

Sample Input

1	5
2	0 2
3	0 4
4	1 3
5	1 2
6	1 5

Sample Output

HINT

$|3−2|+|2−4|=3$ and the last adopter has no pets to adopt.

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
 
using namespace std;
 
typedef long long int lli;
 
class AVLTree {
private:
    struct Node {
        lli key, height;
        Node* left, * right;
        explicit Node(lli key) {
            this->key = key;
            this->height = 0;
            this->left = this->right = nullptr;
        }
 
        static lli getHeight(Node* node) {
            if (node == nullptr) return -1;
            return node->height;
        }
 
        void updateHeight() { this->height = 1 + max(getHeight(this->left), getHeight(this->right)); }
    };
 
    static Node* rotateRight(Node* node) {
        auto tmp = node->left;
        node->left = tmp->right;
        tmp->right = node;
        node->updateHeight();
        tmp->updateHeight();
        return tmp;
    }
 
    static Node* rotateLeft(Node* node) {
        auto tmp = node->right;
        node->right = tmp->left;
        tmp->left = node;
        node->updateHeight();
        tmp->updateHeight();
        return tmp;
    }
 
    static lli getBalanceFactor(Node* node) {
        if (node == nullptr) return 0;
        return Node::getHeight(node->left) - Node::getHeight(node->right);
    }
 
    static Node* balance(Node* node) {
        if (getBalanceFactor(node) < -1) {
            if (getBalanceFactor(node->right) > 0) node->right = rotateRight(node->right);
            node = rotateLeft(node);
        }
        else if (getBalanceFactor(node) > 1) {
            if (getBalanceFactor(node->left) < 0) node->left = rotateLeft(node->left);
            node = rotateRight(node);
        }
        return node;
    }
 
    static Node* add(Node* node, lli key) {
        if (node == nullptr) return new Node(key);
        lli cmp = key - node->key;
        if (cmp < 0) node->left = add(node->left, key);
        else if (cmp > 0) node->right = add(node->right, key);
        node->updateHeight();
        return balance(node);
    }
 
    static Node* min(Node* node) {
        if (node->left == nullptr) return node;
        return min(node->left);
    }
 
    static Node* deleteMin(Node* node) {
        if (node->left == nullptr) return node->right;
        node->left = deleteMin(node->left);
        node->updateHeight();
        return balance(node);
    }
 
    static Node* deleteNode(Node* node, lli key) {
        lli cmp = key - node->key;
        if (cmp < 0) node->left = deleteNode(node->left, key);
        else if (cmp > 0) node->right = deleteNode(node->right, key);
        else {
            if (node->left == nullptr || node->right == nullptr) {
                auto tmp = node->left ? node->left : node->right;
                free(node);
                return tmp;
            }
            else {
                auto tmp = node;
                auto toFree = node;
                node = min(tmp->right);
                node->right = deleteMin(tmp->right);
                node->left = tmp->left;
                free(toFree);
            }
        }
        node->updateHeight();
        return balance(node);
    }
 
    static Node* find(Node* node, lli key) {
        if (node == nullptr) return node;
        Node* res;
        if (key < node->key) res = find(node->left, key);
        else if (key > node->key) res = find(node->right, key);
        else return node;
        if (res == nullptr) res = node;
        if (res->key == key) return res;
        auto dif = abs(key - res->key) - abs(key - node->key);
        if (dif > 0 || (dif == 0 && node->key < res->key)) res = node;
        return res;
    }
 
    lli size;
    Node* root;
 
public:
    AVLTree() {
        this->size = 0;
        this->root = nullptr;
    }
 
    lli getSize() { return size; }
 
    void add(lli key) {
        this->size += 1;
        if (this->size == 1) this->root = new Node(key);
        else this->root = AVLTree::add(this->root, key);
    }
 
    void deleteNode(lli key) {
        this->size -= 1;
        this->root = AVLTree::deleteNode(this->root, key);
    }
 
    lli find(lli key) { return AVLTree::find(this->root, key)->key; }
};
 
int main() {
    int n;
    scanf("%i", &n);
    AVLTree pets = AVLTree();
    AVLTree adopters = AVLTree();
    AVLTree* wIn, * wOut;
    lli res = 0;
    while (n--) {
        int sig;
        lli flag;
        scanf("%i %lli", &sig, &flag);
        if (sig == 0) {
            wIn = &pets;
            wOut = &adopters;
        }
        else {
            wIn = &adopters;
            wOut = &pets;
        }
        if (wOut->getSize() == 0) wIn->add(flag);
        else {
            auto found = wOut->find(flag);
            res += abs(flag - found);
            wOut->deleteNode(found);
        }
    }
    printf("%lli", res);
    return 0;
}
 
/**************************************************************
    Problem: 1200
    User: 
    Language: C++
    Result: Accepted
    Time:36 ms
    Memory:1216 kb
****************************************************************/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;
 
public class Main {
    public static void main(String[] args) {
        InputReader input = new InputReader(System.in);
        int n = input.nextInt();
        TreeSet<Integer> pets = new TreeSet<>();
        TreeSet<Integer> adopters = new TreeSet<>();
        TreeSet<Integer> wIn, wOut;
        long res = 0;
        while(n-->0) {
            int sig = input.nextInt();
            int flag = input.nextInt();
            if(sig == 0) {
                wIn = pets;
                wOut = adopters;
            }
            else {
                wIn = adopters;
                wOut = pets;
            }
            if(wOut.size() == 0) wIn.add(flag);
            else {
                Integer lower = wOut.lower(flag);
                Integer higher = wOut.higher(flag);
                int found;
                if(lower == null) found = higher;
                else if(higher == null) found = lower;
                else found = (higher - flag) < (flag - lower) ? higher : lower;
                res += Math.abs(flag - found);
                wOut.remove(found);
            }
        }
        System.out.printf("%d", res);
    }
 
    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;
 
        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        private String next() {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                try { tokenizer = new StringTokenizer(reader.readLine()); }
                catch (IOException e) { throw new RuntimeException(e); }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}
 
/**************************************************************
    Problem: 1200
    User: 
    Language: Java
    Result: Accepted
    Time:444 ms
    Memory:45800 kb
****************************************************************/

Problem G: Gnisrever Pro [Bonus]

Description

Narnal loves reversing and Fibonacci sequence. When he gets an array with length N, he would reverse the array in the intervals determined by Fibonacci sequence for $K$ times.

Let $F_n$ is the n-th Fibonacci number: $F_1=F_2=1$, $F_n=F_{n−1}+F_{n−2}$ for all $n≥3$.

Let $s_n=F_{2n−1} mod N$ and let $t_n=F_{2n} mod N$.

Finally, Narnal’s happiness is defined as $R(N,K)=∑^{N−1}_{i=0}i×A[i]$ after $K$ operations.

$1≤N≤10^{18}$, $1≤K≤5×10^5$.

Input

One line gives $N$ and $K$, separated by space.

Output

One line with only $R(N,K) mod 10^9$.

Sample Input

5 4

Sample Output

HINT

Consider using nodes to represent the sequences of consecutive numbers.

Using splay tree or other balanced tree data structure!

$R(5,4)=27$ can be seen from the following procedure:
Initial position: (0,1,2,3,4)
Step 1 - Reverse $A[1]$ to $A[1]: (0,1,2,3,4)$
Step 2 - Reverse $A[2]$ to $A[3]: (0,1,3,2,4)$
Step 3 - Reverse $A[0]$ to $A[3]: (2,3,1,0,4)$
Step 4 - Reverse $A[3]$ to $A[1]: (2,0,1,3,4)$
$R(5,4)=0×2+1×0+2×1+3×3+4×4=27$.

Also, $R(10^2,10^2)=246597$.

Lab8_Graph

Problem A: Kingdom

Description

Long time ago, there was a handsome prince named Pisces, who ruled a powerful kingdom. In his kingdom, there were $n$ cities along with $m$ directed roads connecting them. To better govern his kingdom, Pisces had decided to draw an adjacent matrix to represent the circulation relationship among these cities. In his matrix, if there are $a_{ij}$ roads from city $i$ to city $j$, we have $A[i][j]=aij$. Please help him solve this problem.

Input

The first line contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

In each test case, the first line contains $2$ integers $n$ ($2≤n≤1000$) and $m$ ($1≤m≤2000$), indicating the number of cities and the number of roads. And in each of the next $m$ lines, there are $2$ integers $u$ and $v$ ($1≤u,v≤n$), representing that there is a directed road from city $u$ to city $v$.

Output

For each test case, print the adjacent matrix.

Sample Input

1	2
2	4 6
3	1 2
4	2 3
5	3 4
6	2 3
7	4 2
8	1 4
9	3 4
10	1 2
11	3 2
12	1 3
13	3 1

Sample Output

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

Code

1	#define _CRT_SECURE_NO_WARNINGS
2
3	#include <cstdio>
4	#include <vector>
5
6	using namespace std;
7
8	int main() {
9	int testCase;
10	scanf("%i", &testCase);
11	while(testCase--){
12	int n, m;
13	scanf("%i %i", &n, &m);
14	vector<vector<int>> kingdom(n + 1, vector<int>(n + 1));
15	while(m--) {
16	int u, v;
17	scanf("%i %i", &u, &v);
18	kingdom[u][v] += 1;
19	}
20	for(int i = 1; i <= n; i++) {
21	for(int j = 1; j <= n; j++) printf("%i ", kingdom[i][j]);
22	printf("\n");
23	}
24	}
25	return 0;
26	}
27
28	/**************************************************************
29	Problem: 1286
30	User:
31	Language: C++
32	Result: Accepted
33	Time:232 ms
34	Memory:5076 kb
35	****************************************************************/

Problem B: The Sword of Damocles

Description

One day, an elder told Pisces that there was a legendary sword at the end of the sky - the sword of Damocles. Pisces decided to get the sword at any cost. The area between Pisces and the sword can be described as a rectangular field of $n∗m$ square meters, with Pisces currently at the top left corner and the sword at the bottom right corner. However, $k$ monsters are living in this area, and to keep himself safe, Pisces must keep a distance longer than $S_i$ from the $i$-th monster (Euclidean Distance). Given the locations of these $k$ monsters, Pisces wants to find whether he can get the legendary sword.

Input

The first line of input contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

For each of the test case, the first line contains three integers, $N$, $M$, and $K$ ($10≤N,M≤104,1≤K≤1000$). Pisces is now at position $(0,0)$, and the sword at position $(N,M)$. Each of the next $K$ lines describes one of the $K$ monsters, it contains three integers, $X$,$Y$, and $S$ where $(X,Y)$ represents the location and $S$ represents the distance that must be kept. ($0≤X≤N,0≤Y≤M,0<S≤10^4$).

Output

For each test case, print “Yes” if Pisces can get the sword, and “No” otherwise.

Sample Input

1	1
2	10 10 2
3	3 7 4
4	5 4 4

Sample Output

No

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
#include <list>
 
using namespace std;
 
int square(int num);
int calDistance(vector<int> X, vector<int> Y);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while(testCase--){
        int swordX, swordY, monsterNum;
        scanf("%i %i %i", &swordX, &swordY, &monsterNum);
        vector<vector<int>> monsters(monsterNum, vector<int>(3));
        vector<vector<int>> adjacencyList(monsterNum + 2); //monsterNum -> lower bound, +1 upper bound
        for(int i = 0; i < monsterNum; i++) {
            scanf("%i %i %i", &monsters[i][0], &monsters[i][1], &monsters[i][2]);
            if(monsters[i][1] <= monsters[i][2] || swordX - monsters[i][0] <= monsters[i][2]) {
                adjacencyList[monsterNum].push_back(i);
                adjacencyList[i].push_back(monsterNum);
            }
            if(monsters[i][0] <= monsters[i][2] || swordY - monsters[i][1] <= monsters[i][2]) {
                adjacencyList[monsterNum+1].push_back(i);
                adjacencyList[i].push_back(monsterNum + 1);
            }
        }
        for(int i = 0; i < monsterNum; i++) {
            for(int j = i + 1; j < monsterNum; j++) {
                if(j != i) {
                    if(calDistance(monsters[i], monsters[j]) <= square(monsters[i][2] + monsters[j][2])) {
                        adjacencyList[i].push_back(j);
                        adjacencyList[j].push_back(i);
                    }
                }
            }
        }
        queue<int> level;
        vector<bool> isSearched(monsterNum + 2);
        isSearched[monsterNum] = true;
        for(auto e : adjacencyList[monsterNum]) {
            isSearched[e] = true;
            level.push(e);
        }
        while(!level.empty()) {
            for(auto i : adjacencyList[level.front()]) {
                if(!isSearched[i]) {
                    isSearched[i] = true;
                    level.push(i);
                    if(i == monsterNum + 1) goto out;
                }
            }
            level.pop();
        }
        out:
        if(isSearched[monsterNum + 1]) printf("%s\n", "No");
        else printf("%s\n", "Yes");
    }
    return 0;
}
 
int square(int num) {
    return num * num;
}
 
int calDistance(vector<int> X, vector<int> Y) {
    return square(X[0] - Y[0]) + square(X[1] - Y[1]);
}
/**************************************************************
    Problem: 1287
    User: 
    Language: C++
    Result: Accepted
    Time:680 ms
    Memory:1436 kb
****************************************************************/

Problem C: Valentine’s Day

Description

Today is Valentine’s day, and Pisces is going to date with the beautiful princess in the neighboring kingdom. There are $n$ cities numbered from $1$ to $n$ on the mainland, with Pisces in city $1$ and the princess in city $n$. There are m unidirectional roads among these $n$ cities. Usually, it takes Pisces $1$ unit of time to travel from one city to another, but due to the probable existence of thorns, rivers or even robbers, some of the roads will take $2$ units of time to travel. In other words, the cost of traveling from one city to another is either $1$ unit or $2$ units of time. Pisces wants to know the minimum time that he can meet the princess.

Input

The first line contains $2$ integers $n$ ($2≤n≤2∗10^5$) and $m$ ($1≤m≤4∗10^5$).

In each of the next $m$ lines, there are $3$ integers $u, v$ ($1≤u,v≤n$) and $w$ ($1≤w≤2$), which means there is a road from $u$ to $v$, and it takes $w$ unit(s) of time for Pisces to go through.

Output

Print the minimum time in one line. Or, if he cannot reach the destination, print “-1” (without quotes).

Sample Input

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

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
    int vertices, edges;
    scanf("%i %i", &vertices, &edges);
    vector<vector<int>> cities(vertices + 1);
    while(edges--) {
        int u, v, w;
        scanf("%i %i %i", &u, &v, &w);
        if(w == 2) cities[u].push_back(-v);
        else cities[u].push_back(v);
    }
    auto level = new queue<int>;
    auto tmp = new queue<int>;
    vector<bool> isSearched(vertices + 1);
    isSearched[1] = true;
    level->push(1);
    int time = 1;
    while(!level->empty()) {
        while(!level->empty()) {
            if(level->front() < 0) {
                if(!isSearched[-level->front()]) {
                    isSearched[-level->front()] = true;
                    if (isSearched[vertices]) goto out;
                    tmp->push(-level->front());
                }
            }
            else {
                for (auto i : cities[level->front()]) {
                    if (i < 0) tmp->push(i);
                    else {
                        if (!isSearched[i]) {
                            isSearched[i] = true;
                            if (isSearched[vertices]) goto out;
                            tmp->push(i);
                        }
                    }
                }
            }
            level->pop();
        }
        time += 1;
        auto t = level;
        level = tmp;
        tmp = t;
    }
    out:
    if(isSearched[vertices]) printf("%i", time);
    else printf("%i", -1);
    return 0;
}
 
/**************************************************************
    Problem: 1245
    User: 
    Language: C++
    Result: Accepted
    Time:236 ms
    Memory:14300 kb
****************************************************************/

Problem D: Defensive Tower

Description

On the mainland, there is a fire-breathing dragon called “lanran”, who is always burning cities and attacking people. So Pisces decides to build some defensive towers in the kingdom to protect his people. A defensive tower is able to protect the city where it is located and the cities adjacent to it. However, building a tower costs a lot, so Pisces could only build at most $⌊n/2$⌋ defensive towers ($n$ is the total number of cities in the kingdom). Please find a way to build defensive towers in order to protect the whole kingdom. If there are multiple answers, print any.

By saying that “two cities are adjacent”, it means that there is one undirected road connecting them.

Input

The first line contains a single integer $t$ ($1≤t≤2∗10^5$), which represents the number of test cases. Then $t$ test cases follow.

In each test case, the first line contains $2$ integers $n$ ($2≤n≤2∗10^5$) and $m$ ($n−1≤m≤min(2∗10^5,\frac{n∗(n−1)}{2})$), indicating the number of cities and the number of roads. And in each of the next $m$ lines, there are $2$ integers $u$ and $v$ ($1≤u,v≤n$) representing the indexes of the cities that this road connects.

There are no self-loops or multiple edges in the given graph. It is guaranteed that the given graph is connected and $∑m≤2∗10^5$.

Output

For each test case print two lines.

In the first line print $k$ — the number of chosen cities.

In the second line print $k$ distinct integers $c_1,c_2,…,c_k$ in any order, where ci is the index of the i-th chosen city.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

Sample Input

1	2
2	4 6
3	1 2
4	1 3
5	1 4
6	2 3
7	2 4
8	3 4
9	6 8
10	2 5
11	5 4
12	4 3
13	4 1
14	1 3
15	2 3
16	2 6
17	5 6

Sample Output

1	2
2	1 3
3	3
4	4 3 6

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while(testCase--) {
        int cities, roads;
        scanf("%i %i", &cities, &roads);
        vector<vector<int>> network(cities + 1);
        network[0].push_back(1);
        while(roads--) {
            int u, v;
            scanf("%i %i", &u, &v);
            network[u].push_back(v);
            network[v].push_back(u);
        }
        auto level = new queue<int>;
        auto temp = new queue<int>;
        vector<bool> isSearched(network.size());
        isSearched[0] = true;
        level->push(0);
        int odd = 0, even = 0;
        auto currentCounter = &odd, tmpCounter = &even;
        while(!level->empty()) {
            while(!level->empty()) {
                for(auto i : network[level->front()]) {
                    if(!isSearched[i]) {
                        isSearched[i] = true;
                        *currentCounter += 1;
                        temp->push(i);
                    }
                }
                level->pop();
            }
            auto t0 = level;
            level = temp;
            temp = t0;
            auto t1 = currentCounter;
            currentCounter = tmpCounter;
            tmpCounter = t1;
        }
        auto isOdd = odd <= even;
        if(isOdd) printf("%i\n", odd);
        else printf("%i\n", even);
        int shell = 1;
        isSearched[0] = false;
        level->push(0);
        while(!level->empty()) {
            while(!level->empty()) {
                for(auto i : network[level->front()]) {
                    if(isSearched[i]) {
                        isSearched[i] = false;
                        if(shell & 1) {
                            if(isOdd) printf("%i ", i);
                        }
                        else {
                            if(!isOdd) printf("%i ", i);
                        }
                        temp->push(i);
                    }
                }
                level->pop();
            }
            shell += 1;
            auto t0 = level;
            level = temp;
            temp = t0;
        }
        printf("\n");
        delete level;
        delete temp;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1229
    User: 
    Language: C++
    Result: Accepted
    Time:768 ms
    Memory:1956 kb
****************************************************************/

Problem E: Soldiers

Description

Pisces has many soldiers, and he wants to train them in a line. Considering the height, weight and other factors of soldiers, Pisces wants some soldiers to stand in front of others. Besides, if there are multiple orders available, soldiers with smaller indices must stand as in the front as possible. It is guaranteed that the answer exists.

Input

The first line contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

For each of the test cases, the first line contains $2$ integers $n$ and $m $ ($2≤n≤2∗10^5,1≤m≤4∗10^5$), which represents the number of soldiers and the number of constrains, respectively. Each of the next $m$ lines contains $2$ integers $u$ and $v$ ($1≤u,v≤n$), which means soldier $u$ must stand in front of soldier $v$.

Output

For each of the test cases, print the order.

Sample Input

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

Sample Output

1	6 5 1 4 3 2

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
 
using namespace std;
 
const int IN = 0, OUT = 1;
 
int main() {
    stack<int> output;
    priority_queue<int> priorityQueue;
 
    int testCase;
    scanf("%i", &testCase);
    while(testCase--) {
        int soldiers, constrains;
        scanf("%i %i", &soldiers, &constrains);
        vector<int[2]> degree(soldiers + 1);
        vector<vector<int>> adjacencyList(soldiers + 1);
        while(constrains--) {
            int u, v;
            scanf("%i %i", &u, &v);
            adjacencyList[v].push_back(u);
            degree[u][OUT] += 1;
            degree[v][IN] += 1;
        }
 
        for(int i = 1; i < soldiers + 1; i++) if(degree[i][OUT] == 0) priorityQueue.push(i);
        while(!priorityQueue.empty()) {
            auto top = priorityQueue.top();
            output.push(top);
            priorityQueue.pop();
            if(degree[output.top()][IN] != 0) {
                for(auto i : adjacencyList[top]) {
                    degree[i][OUT] -= 1;
                    if(degree[i][OUT] == 0) priorityQueue.push(i);
                }
            }
        }
 
        degree.clear();
        adjacencyList.clear();
 
        while(!output.empty()) {
            printf("%i ", output.top());
            output.pop();
        }
        printf("\n");
    }
    return 0;
}
 
/**************************************************************
    Problem: 1288
    User: 
    Language: C++
    Result: Accepted
    Time:232 ms
    Memory:3388 kb
****************************************************************/

import java.util.*;
 
public class Main {
    final static int IN = 0, OUT = 1;
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        Stack<Integer> stack = new Stack<>();
 
        int testCase = input.nextInt();
        while(testCase-->0) {
            int soldiers = input.nextInt();
            int constrains = input.nextInt();
            int[][] degree = new int[soldiers + 1][2];
            LinkedList<Integer>[] adjacencyList = new LinkedList[degree.length];
            for(int i = 1; i < adjacencyList.length; i++) adjacencyList[i] = new LinkedList<>();
            while(constrains-->0) {
                int u = input.nextInt();
                int v = input.nextInt();
                adjacencyList[v].push(u);
                degree[u][OUT] += 1;
                degree[v][IN] += 1;
            }
 
            while(!priorityQueue.isEmpty()) priorityQueue.poll();
            for(int i = 1; i < degree.length; i++) if(degree[i][OUT] == 0) priorityQueue.offer(i);
            while(!priorityQueue.isEmpty()) {
                int peek = priorityQueue.peek();
                stack.push(peek);
                priorityQueue.poll();
                if(degree[peek][IN] != 0) {
                    for(int i : adjacencyList[peek]) {
                        degree[i][OUT] -= 1;
                        if(degree[i][OUT] == 0) priorityQueue.offer(i);
                    }
                }
            }
 
            while(!stack.isEmpty()) System.out.printf("%d ", stack.pop());
            System.out.println();
        }
    }
}
 
/**************************************************************
    Problem: 1288
    User: 
    Language: Java
    Result: Accepted
    Time:2572 ms
    Memory:85164 kb
****************************************************************/

Problem F: Palace

Description

To celebrate the victory of the war, Pisces has decided to build a splendid palace. The craftsmen has brought back $n$ kinds of cube materials from the dwarf kingdom. The length, width, and height of each material are $a$, $b$ and $c$ respectively. To make the palace magnificent, the craftsmen have to stack these materials together. Material $i$ can be stacked on material $j$ if and only if $a_i<a_j⋂b_i<b_j$, or $a_i<b_j⋂b_i<a_j$. Pisces wants to know how high these materials can stack at most.

Input

The first line contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

For each of the test cases, the first line contains an integer $n$ ($1≤n≤2∗10^3$), which represents the number of materials. Each of the next $n$ lines contains $3$ integers $a$, $b$ and $c$ ($1≤a,b,c≤1000$), which represents the size of a material.

Output

For each test case, print the maximum height.

Sample Input

1	1
2	3
3	2 3 5
4	4 3 4
5	3 3 3

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
 
using namespace std;
 
int maxHeight(vector<int> &bHeight, vector<vector<int>> &adjacencyList, vector<int[2]> &degree);
 
int main() {
    int testCase;
    scanf("%i", &testCase);
    while(testCase--) {
        int quantity;
        scanf("%i", &quantity);
        vector<int[2]> bricks(quantity);
        vector<int> bHeight(quantity);
        for(int i = 0; i < quantity; i++) scanf("%i %i %i", &bricks[i][0], &bricks[i][1], &bHeight[i]);
 
        vector<vector<int>> adjacencyList(quantity);
        vector<int[2]> degree(quantity); // 0 --> IN; 1 --> OUT;
        for(int i = 0; i < quantity; i++) {
            for(int j = i + 1; j < quantity; j++) {
                if((bricks[i][0] < bricks[j][0] && bricks[i][1] < bricks[j][1]) || (bricks[i][0] < bricks[j][1] && bricks[i][1] < bricks[j][0])) {
                    adjacencyList[i].push_back(j);
                    degree[i][1] += 1;
                    degree[j][0] += 1;
                }
                else if((bricks[j][0] < bricks[i][0] && bricks[j][1] < bricks[i][1]) || (bricks[j][0] < bricks[i][1] && bricks[j][1] < bricks[i][0])) {
                    adjacencyList[j].push_back(i);
                    degree[i][0] += 1;
                    degree[j][1] += 1;
                }
            }
        }
        bricks.clear();
 
        printf("%i\n", maxHeight(bHeight, adjacencyList, degree));
    }
    return 0;
}
 
vector<int>* dp;
vector<int>* bHeightP;
vector<vector<int>>* adjacencyListP;
vector<int[2]>* degreeP;
 
 
int DP(int i) {
    if(dp->at(i) > 0) return dp->at(i);
    if(degreeP->at(i)[1] == 0) {
        dp->at(i) = bHeightP->at(i);
    }
    else {
        for(auto e : adjacencyListP->at(i)) {
            dp->at(i) = max(dp->at(i), DP(e) + bHeightP->at(i));
        }
    }
    return dp->at(i);
}
 
int maxHeight(vector<int> &bHeight, vector<vector<int>> &adjacencyList, vector<int[2]> &degree) {
    bHeightP = &bHeight;
    adjacencyListP = &adjacencyList;
    degreeP = &degree;
    dp = new vector<int>(bHeight.size());
    int maxH = 0;
    for(int i = 0; i < degree.size(); i++) {
        if(degree[i][0] == 0) {
            DP(i);
            if(dp->at(i) > maxH) maxH = dp->at(i);
        }
    }
    dp->clear();
    return maxH;
}
/**************************************************************
    Problem: 1289
    User: 
    Language: C++
    Result: Accepted
    Time:696 ms
    Memory:9824 kb
****************************************************************/

Problem G: Hunting

Description

Pisces likes hunting very much. There are $n$ camps in the forest, with $m$ directed weighted forest roads connecting them. Pisces would choose the path for hunting in accordance to his mood. The length of the path is the sum of the weight $w$ of the roads he has passed. Note that he can pass any road for multiple times.

Now, Pisces wants to know the $k$-th minimum length of all the paths. There are $q$ queries you need to answer.

Input

The first line contains an integer $t$ ($1≤t≤100$), which represents the number of the test cases.

The first line of each test case contains three positive integers $n$, $m$, $q$ ($1≤n,m,q≤5∗10^4$).

Each of the next $m$ lines contains $3$ integers $u$, $v$, $w$, indicating that there is a forest road from $u$ to $v$ and it weights $w$ ($1≤u,v≤n,1≤w≤10^9$).

Each of the next $q$ lines contains one integer $k$ ($1≤k≤5∗10^4$) as mentioned above. It’s guaranteed that $Σn$,$Σm$,$Σq$,$Σmax(k)≤2.5∗10^5$ and $max(k)$ won’t exceed the number of paths in the forest.

Output

For each query, print one integer indicates the answer in line.

Sample Input

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

Sample Output

1	3
2	3

Problem H: Magic

Description

Pisces is learning to build a magic field with a great magician. To build a magic field, Pisces must build some directed channels between $N$ nodes to let the mana flow into it. Unfortunately, Pisces finds that these channels may have some circles, where the mana will get stuck in them forever! To maintain the stability of this magic field, Pisces wants to know whether it is possible to destroy at most one channel to make the magic field acyclic.

Input

The first line contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

For each test case, the first line contains $2$ integers $n$ and $m$ ($2 ≤n ≤ 500,1 ≤ m ≤min(n(n − 1), 100000)$) — the number of nodes and the number of channels, respectively. Each of the next $m$ lines contains $2$ integers $u$ and $v$ denoting a directed channel going from node $u$ to node $v$ ($1≤u,v ≤ n,u ≠v$). There is at most one directed channel from $u$ to $v$.

Output

For each test case, print “Yes” (without quotes) if it’s possible, and “No” (without quotes) otherwise.

Sample Input

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

Sample Output

No

Problem I: The Elves

Description

To make the kingdom more prosperous, Pisces decides to ally with the elves living in the forest. However, the elven elders want to test Pisces, so they give him a simple question. Given a DAG with n nodes and m edges, the elven elders want to know the value of $∑^n_{i=1}∑^n_{j=1}count(i,j)⋅a_i⋅b_j mod 1e9+7$, where $count(x,y)$ is defined by the number of different paths from $x$ to $y$, and $a$, $b$ are $2$ given arrays. It is too hard for Pisces to answer this question, so he turns to you for help.

Input

The first line contains an integer $T$ ($1≤T≤10$), which denotes the number of test cases.

For each test case, the first line contains $2$ integers $n$ and $m$ ($1 ≤n,m ≤ 10^5$) — the number of nodes and the number of edges, respectively. Each of the next $n$ lines contains $2$ integers $a_i$ and $b_i$. And for the next $m$ lines, each line contains $2$ integers $u$ and $v$ denoting a directed edge going from node $u$ to node $v$ ($1≤u,v ≤ n$).

Output

For each test case, print the answer.

Sample Input

1	3
2	3 3
3	1 1
4	1 1
5	1 1
6	1 2
7	1 3
8	2 3
9	2 2
10	1 0
11	0 2
12	1 2
13	1 2
14	2 1
15	500000000 0
16	0 500000000
17	1 2

Sample Output

1	4
2	4
3	250000014

Lab9_Advanced_Graph

Problem A: Traveling

Description

Yuki is a playful girl and she enjoys traveling.

One day, she is planning to play in the Disneyland. The resort is so large that she cannot find the shortest path between two sights immediately, so she wants to ask for your help.

Specifically, there are n sights and m roads in the Disneyland. Each road, with a certain distance, connects two sights. The sights are numbered from 1 to n and the roads are all bidirectional, that is the road from sight u to sight v can be passed from sight v to u. You are asked to find the shortest distance between sight S and sight T.

Input

The first line contains two integers: n and m ($1≤n≤1 000, 1≤m≤5 000$) — the number of sights and roads in Disneyland.

Each of the next m lines contains three space-separated integers: u, v and w ($1≤u, v≤n, 1≤w≤10^5$), meaning that there is a bidirectional road from sight u to sight v with distance w.

The last line contains two integers: S and T ($1≤S, T≤n$) — the origin and destination.

Output

Print the result — the shortest distance between sight S and sight T.

If there are no paths from sight S to sight T, print −1 instead.

Sample Input

1	3 3
2	1 2 5
3	2 3 5
4	3 1 2
5	1 3

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <climits>
 
using namespace std;
 
auto main() -> int {
    int sights, roads;
    scanf("%i %i", &sights, &roads);
    vector<vector<pair<int,int>>> park(sights + 1);
    while(roads--) {
        int u, v, w;
        scanf("%i %i %i", &u, &v, &w);
        park[u].push_back(make_pair(v, w));
        park[v].push_back(make_pair(u, w));
    }
    int sp, ep;
    scanf("%i %i", &sp, &ep);
    vector<int> dist(sights + 1, INT_MAX);
    vector<bool> mark(sights + 1);
    dist[sp] = 0;
 
    for(int c = 1; c < sights;) {
        int minLen = INT_MAX, minIndex = 0;
        for(int i = 1; i < sights; i++) {
            if(!mark[i] && dist[i] < minLen) {
                minLen = dist[i];
                minIndex = i;
            }
        }
        mark[minIndex] = true;
        c++;
        for(auto e : park[minIndex]) {
            if(!mark[e.first] && dist[minIndex] != INT_MAX && dist[minIndex] + e.second < dist[e.first]) {
                dist[e.first] = dist[minIndex] + e.second;
            }
        }
    }
 
    if(dist[ep] == INT_MAX) printf("%i", -1);
    else printf("%i", dist[ep]);
    return 0;
}
 
/**************************************************************
    Problem: 1192
    User:
    Language: C++
    Result: Accepted
    Time:60 ms
    Memory:2216 kb
****************************************************************/

Problem B: Construction

Description

Yuki is a wise girl and she rules a country named Blossom.

Blossom is a big country with n cities, and there are m roads determined to be constructed. Due to many reasons during construction, different roads might have different costs to be built. The roads are bidirectional, that is a road from u to v can be passed from v to u.

Since Yuki wants to make the construction more economical, she decides to choose some of the roads to construct and wants to spend the least money. However, to make the traffic in Blossom convenient, all the cities in Blossom are needed to be connected after construction. Your task is to determine the minimum cost of construction.

Input

The first line contains two integers: n and m ($1≤n≤1 000, 1≤m≤10 000$) — the number of cities and roads to be constructed in Blossom.

Each of the next m lines contains three space-separated integers: u, v and w ($1≤u, v≤n, 1≤w≤10^6$), meaning that there is a bidirectional road from city u to city v considered to be built. And the cost of this edge is w. Cities are numbered from 1 to n.

It is guaranteed that there is at least one plan to connect all cities.

Output

Print one line with an integer — the minimum cost of the construction.

Sample Input

1	4 4
2	1 2 2
3	2 3 2
4	3 4 2
5	4 1 2

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <climits>
 
using namespace std;
 
struct Edge {
    int a, b, w;
 
    Edge(int a, int b, int w) {
        this->a = a;
        this->b = b;
        this->w = w;
    }
} *maxEdge = new Edge(-1, -1, INT_MAX);
 
auto main() -> int {
    int vertexN, edgeN;
    scanf("%i %i", &vertexN, &edgeN);
    vector<char> vertices(vertexN + 1, 0);
    vector<Edge *> edges;
    edges.reserve(edgeN);
    while(edgeN--) {
        int u, v, w;
        scanf("%i %i %i", &u, &v, &w);
        edges.emplace_back(new Edge(u, v, w));
    }
 
    int length = 0;
    Edge *minEdge = maxEdge;
    for(auto edge : edges) {
        if(edge->w < minEdge->w) minEdge = edge;
    }
    do {
        length += minEdge->w;
        vertices[minEdge->a] = vertices[minEdge->b] = 1;
        minEdge = maxEdge;
        for(auto edge : edges) {
            if(vertices[edge->a] != vertices[edge->b] && edge->w < minEdge->w) minEdge = edge;
        }
    } while(minEdge != maxEdge);
 
    printf("%i\n", length);
    return 0;
}
 
/**************************************************************
    Problem: 1193
    User: 
    Language: C++
    Result: Accepted
    Time:172 ms
    Memory:2360 kb
****************************************************************/

Problem C: Maze

Description

Yuki is a careless girl and she is designing mazes.

A maze consists of n rooms and m passageways. The rooms are numbered from 1 to n and all the passageways are unidirectional, that is the passageway from room u to v cannot be passed from room v to u. Besides, to avoid tourists being trapped in the maze, all the rooms should be connected, that is for every pair of integers (u,v) such that $1≤u,v≤n,u≠v$, there should be a path from room u to room v.

Yuki has already designed a “maze”. However, due to her carelessness, you need to check whether the maze she designed is a real maze, that is all the rooms in her maze are connected.

Input

The first line contains two integers: n and m ($1≤n,m≤200 000$) —- the number of rooms and passageways in the maze.

Each of the next m lines contains two integers: u and v ($1≤u, v≤n$), meaning that there is a unidirectional passageway from room u to room v.

Output

If all the rooms in the maze are connected, print “Bravo” (without quotation).

Otherwise print “ovarB” (without quotation).

Sample Input

1	3 3
2	1 2
3	2 3
4	3 2

Sample Output

ovarB

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <stack>
 
using namespace std;
 
auto main() -> int {
    int vertexN, edgeN;
    scanf("%i %i", &vertexN, &edgeN);
    vector<vector<int>> graph(vertexN + 1);
    vector<vector<int>> graphR(vertexN + 1);
    while(edgeN--) {
        int u, v;
        scanf("%i %i", &u, &v);
        graph[u].push_back(v);
        graphR[v].push_back(u);
    }
 
    vector<int> sequence;
    stack<int> dfsContainer;
    sequence.reserve(vertexN);
    vector<bool> mark(vertexN + 1, true);
 
    dfsContainer.push(1);
    mark[1] = false;
    while(!dfsContainer.empty()) {
        auto top = dfsContainer.top();
        for(auto vertex : graphR[top]) {
            if(mark[vertex]) {
                dfsContainer.push(vertex);
                mark[vertex] = false;
                break;
            }
        }
        if(dfsContainer.top() == top) {
            sequence.push_back(top);
            dfsContainer.pop();
        }
    }
    graphR.clear();
 
    dfsContainer.push(sequence.back());
    mark[dfsContainer.top()] = true;
    sequence.clear();
    while(!dfsContainer.empty()) {
        auto top = dfsContainer.top();
        for(auto v : graph[top]) {
            if(!mark[v]) {
                dfsContainer.push(v);
                mark[v] = true;
                break;
            }
        }
        if(dfsContainer.top() == top) {
            sequence.push_back(top);
            dfsContainer.pop();
        }
    }
 
    if(sequence.size() == vertexN) printf("Bravo\n");
    else printf("ovarB\n");
    return 0;
}
 
/**************************************************************
    Problem: 1292
    User: 
    Language: C++
    Result: Accepted
    Time:116 ms
    Memory:8000 kb
****************************************************************/

Problem D: Points

Description

Yuki is an ambitious girl and she is addicted to a game called Honor of Kings.

In the game, Yuki is controlling the King to move in a grid of n rows and m columns, where rows are numbered from 1 to n and columns are numbered from 1 to m. The cell at the i-th row and the j-th column is denoted by (i,j). Each cell in the grid contains a point coefficient, denoted by $C_{ij}$.

At first, Yuki can place the King on the grid arbitrarily, that is any cells in the grid can be the initial position for the King. Every turn Yuki can move the King between the cells sharing a common edge. For example, when the King is at (i,j), it can be chosen to move to (i−1,j), (i+1,j), (i,j−1) or (i,j+1), if the destination is not out of the boundary.

Now every time when the King is moved from one cell to an unvisited cell, Yuki will gain the points which is equal to the product of two point coefficients. It means that Yuki will get $C_{xy}⋅C_{ij}$ points when the King moves from (i,j) to (x,y) and visits (x,y) at the first time.

Yuki can stop the game at any time, and she wonders the maximum score she can gain.

Input

The first line contains two integers: n and m ($1≤n,m≤50 000,1≤n⋅m≤50 000$) —- rows and columns of the grid.

Each of the next n lines contains m integers. The j-th number in the i-th line denotes $C_{ij}$ ($1≤C_{ij}≤5 000$).

Output

Print one line with the result — the maximum points.

Sample Input

1	1 4
2	1 2 3 3

Sample Output

Code

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
int rows, columns;
 
struct Edge {
    int a, b, w;
 
    Edge(int a, int b, int w) {
        this->a = a;
        this->b = b;
        this->w = w;
    }
};
 
struct Vertex {
    int weight;
    vector<Edge *> adjoin;
    bool mark = false;
 
    Vertex(int row, int column, int weight) {
        this->weight = weight;
        int initSize = 4;
        if(row == 0 || row == rows - 1) {
            if(column == 0 || column == columns - 1) initSize = 2;
            else initSize = 3;
        }
        else if(column == 0 || column == columns - 1) initSize = 3;
        this->adjoin.reserve(initSize);
    }
};
 
struct cmp {
    bool operator()(Edge *a, Edge *b) {
        return a->w < b->w;
    }
};
 
auto main() -> int {
    scanf("%i %i", &rows, &columns);
    vector<Vertex *> cells;
    cells.reserve(rows * columns);
    for(int i = 0, w; i < rows; i++)
        for(int j = 0; j < columns; j++) {
            scanf("%i", &w);
            cells.emplace_back(new Vertex(i, j, w));
        }
 
    auto maxEdge = new Edge(-1, -1, 0);
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < columns; j++) {
            int index = i * columns + j;
            if(i + 1 < rows) {
                int down = index + columns;
                int point = cells[index]->weight * cells[down]->weight;
                cells[index]->adjoin.emplace_back(new Edge(index, down, point));
                cells[down]->adjoin.emplace_back(new Edge(down, index, point));
                if(point > maxEdge->w) maxEdge = cells[index]->adjoin.back();
            }
            if(j + 1 < columns) {
                int right = index + 1;
                int point = cells[index]->weight * cells[right]->weight;
                cells[index]->adjoin.emplace_back(new Edge(index, right, point));
                cells[right]->adjoin.emplace_back(new Edge(right, index, point));
                if(point > maxEdge->w) maxEdge = cells[index]->adjoin.back();
            }
        }
    }
 
    vector<int> visited;
    visited.reserve(cells.size());
    visited.emplace_back(maxEdge->a);
    visited.emplace_back(maxEdge->b);
    cells[maxEdge->a]->mark = true;
    cells[maxEdge->b]->mark = true;
    priority_queue<Edge *, vector<Edge *>, cmp> EdgeQueue;
    for(auto e : cells[visited[0]]->adjoin) if(!cells[e->b]->mark) EdgeQueue.push(e);
    long long int length = maxEdge->w;
    while(visited.size() != cells.size()) {
        for(auto e : cells[visited.back()]->adjoin) if(!cells[e->b]->mark) EdgeQueue.push(e);
        while(cells[maxEdge->b]->mark) {
            maxEdge = EdgeQueue.top();
            EdgeQueue.pop();
        }
        cells[maxEdge->b]->mark = true;
        visited.emplace_back(maxEdge->b);
        length += maxEdge->w;
    }
 
    printf("%lli\n", length);
    return 0;
}
 
/**************************************************************
    Problem: 1295
    User: 
    Language: C++
    Result: Accepted
    Time:148 ms
    Memory:14276 kb
****************************************************************/

Problem E: Portal

Description

Yuki is a magical girl and she has the ability to activate portals.

The country Yuki lives in has n cities and m roads at certain distances. The cities are numbered from 1 to n and all the roads are unidirectional, that is a road from u to v cannot be passed from v to u. Also, there are p portals in the country, each of them connects two cities unidirectional with no distance. Since Yuki doesn’t grasp magic thoroughly, she can activate at most k portals.

Now Yuki is curious about what is the minimum distance between S and T if she activates at most k portals.

Input

The first line contains four integers: n, m, p and k ($1≤n,m,p≤50 000,0≤k≤10$) —- the number of cities, roads, portals and the number of portals Yuki can activate at most.

Each of the next m lines contains three integers: u, v and w ($1≤u, v≤n,1≤w≤1 000 000$), meaning that there is a unidirectional road from city u to city v at distance w.

Each of the next p lines contains two integer: u and v ($1≤u, v≤n$), meaning that there is an inactive portal from city u to city v. Please note that when it is active, Yuki can only be teleported from city u to v unidirectionally.

The last line contains two integers: S and T ($1≤S,T≤n$) —- the origin and destination.

Output

Print one line with the result —- the minimum distance between city S and T.

It is guaranteed that Yuki can move from city S to T by activating at most k portals.

Sample Input

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

Sample Output

Problem F: Boom

Description

Yuki is a grumpy girl and she always wants to make some noise.

One day, Yuki goes to the amusement ground in her university and sets n bombs. The i-th bomb set at the position $(x_i,y_i)$ has exploding radius $r_i$ and lighting-cost $t_i$, which means that Yuki needs to spend $t_i $seconds to config the bomb and make it exploded by remote control.

A bomb will explode instantly if it is in the exploding area (including the boundaries) of any other exploded bombs.

Yuki wants to know the minimum time needed to make all the bombs exploded, and could you give her the answer?

Input

The first line contains an integer n ($1≤n≤1 000$) —- the number of bombs.

In the following n lines, the i-th line contains four integers: $x_i, y_i, r_i$ and $t_i$ ($−10^8≤x_i,y_i≤10^8,0≤r_i,t_i≤10 000$) —- parameters of the bomb.

Output

Print one line with the result —- the minimum time cost.

Sample Input

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

Sample Output

Problem G: NPC

Description

Yuki is a clever girl and she firmly believes that $NP≠P$.

One day TruthBoy, a friend of Yuki, claims that he has found a polynomial-time algorithm to solve Hamiltonian cycle problem, a famous NP-Complete problem.

There is a graph $G=(V,E)$ with n nodes and m edges. Each road is unidirectional, that is an edge from u to v cannot be passed from v to u. Let node 1 be the capital. The path starting at the capital node, visiting every non-capital node exactly once, and finishing in the capital is called a Hamiltonian cycle. And to determine the existence of Hamiltonian cycles in a given graph is called the Hamiltonian cycle problem.

Yuki does not think that TruthBoy has really solved the problem. However, TruthBoy can always give the correct answers to Yuki’s tests. To know the truth, Yuki turns to you for help. Can you help her to find out how TruthBoy solves the problem?

Input

The first line contains two integers: n and m ($2≤n≤100 000, 0≤m≤n+20$) — the number of nodes and directed edges in the graph.

Each of the next m lines contains two integers: u and v ($1≤u, v≤n$), meaning that there is a directional edge from node u to node v.

Nodes are numbered from 1 to n. The capital is numbered as 1.

Output

If there are multiple Hamiltonian cycles, you can print any of them. Print one line with n+1 space-separated integers — a list of nodes along the cycle.

If there is no Hamiltonian cycle, just print “ovarB” (without quotation).

Sample Input

1	4 6
2	1 4
3	4 1
4	4 2
5	2 1
6	3 4
7	1 3

Sample Output

1 3 4 2 1

HINT

Please remind that your code is judged by a special judge, and any valid answers will be accepted.

1	public class Main {
2	private static int[][] sudoku = new int[9][9];
3	private static java.util.Stack<Integer[]> coordinates = new java.util.Stack<>();
4	private static int[][] coo;
5
6	public static void main(String[] args) {
7	java.util.Scanner input = new java.util.Scanner(System.in);
8	for(int i=0; i<sudoku.length; i++) {
9	for(int j=0; j<sudoku[i].length; j++) {
10	String s = input.next();
11	if(s.equals("\|")) {s = input.next();}
12	if(s.equals("x")) {
13	Integer[] coordinate = {i, j, position(i, j)};
14	coordinates.push(coordinate);
15	continue;
16	}
17	sudoku[i][j] = Integer.parseInt(s);
18	}
19	}
20	input.close();
21
22	exchange();
23	int n = coo.length;
24
25	do {
26	boolean[][] ways = Judge();
27	for(int i=0; i<coo.length; i++) {
28	if(ways[i][0] && ways[i][1] && ways[i][2]) {
29	Integer[] t = {coo[i][0], coo[i][1], coo[i][2]};
30	coordinates.push(t);
31	}
32	else {
33	if(!ways[i][0]) way0(coo[i]);
34	else if(!ways[i][1]) way1(coo[i]);
35	else if(!ways[i][2]) way2(coo[i]);
36	}
37	}
38	exchange();
39	if(n==coo.length) {
40	System.out.println("The test data is incorrect!");
41	return;
42	}
43	else {
44	n = coo.length;
45	}
46	} while(coo.length != 0);
47
48	printSudoku();
49	}
50
51	private static int position(int x, int y) {
52	int a = 0;
53	switch(x/3) {
54	case 2: a += 3;
55	case 1: a += 3;
56	case 0:
57	}
58	return a + y/3;
59	}
60
61	private static void exchange() {
62	coo = new int[coordinates.size()][3];
63	for(int i=coo.length-1; i>=0; i--) {
64	Integer[] temp = coordinates.pop();
65	coo[i][0] = temp[0];
66	coo[i][1] = temp[1];
67	coo[i][2] = temp[2];
68	}
69	}
70
71	private static boolean[][] Judge() {
72	boolean[][] ways = new boolean[coo.length][3];
73	for(int i=0; i<coo.length; i++) {
74	for (int j = i + 1; j < coo.length; j++) {
75	if (coo[i][0] == coo[j][0]) {
76	ways[i][0] = true;
77	ways[j][0] = true;
78	}
79	if (coo[i][1] == coo[j][1]) {
80	ways[i][1] = true;
81	ways[j][1] = true;
82	}
83	if (coo[i][2] == coo[j][2]) {
84	ways[i][2] = true;
85	ways[j][2] = true;
86	}
87	}
88	}
89	return ways;
90	}
91
92	private static void way0(int[] coo) {
93	int sum = 0;
94	for(int i=0; i<sudoku.length; i++) {
95	sum += sudoku[coo[0]][i];
96	}
97	sudoku[coo[0]][coo[1]] = 45 - sum;
98	}
99
100	private static void way1(int[] coo) {
101	int sum = 0;
102	for(int i=0; i<sudoku.length; i++) {
103	sum += sudoku[i][coo[1]];
104	}
105	sudoku[coo[0]][coo[1]] = 45 - sum;
106	}
107
108	private static void way2(int[] coo) {
109	int[] startPoint = new int[2];
110	switch(coo[2]) {
111	case 2: startPoint[1] += 3;
112	case 1: startPoint[1] += 3;
113	case 0: break;
114	case 5: startPoint[1] += 3;
115	case 4: startPoint[1] += 3;
116	case 3: {
117	startPoint[0] = 3;
118	break;
119	}
120	case 8: startPoint[1] += 3;
121	case 7: startPoint[1] += 3;
122	case 6: startPoint[0] = 6;
123	}
124	int sum = 0;
125	for(int i=startPoint[0]; i<startPoint[0]+3; i++) {
126	for(int j=startPoint[1]; j<startPoint[1]+3; j++) {
127	sum += sudoku[i][j];
128	}
129	}
130	sudoku[coo[0]][coo[1]] = 45 - sum;
131	}
132
133	private static void printSudoku() {
134	for(int i=0; i<sudoku.length; i++) {
135	for(int j=0; j<sudoku[i].length; j++) {
136	System.out.print(sudoku[i][j]+" ");
137	if(j%3 == 2) {
138	System.out.print('\|');
139	if(j==sudoku[i].length-1) System.out.println();
140	else System.out.print(' ');
141	}
142	}
143	if(i%3 == 2) System.out.println();
144	}
145	}
146	}
147
148	/**************************************************************
149	Problem: 1202
150	User:
151	Language: Java
152	Result: Accepted
153	Time:188 ms
154	Memory:18444 kb
155	****************************************************************/

1	#include <iostream>
2	#include <algorithm>
3	#include <string.h>
4
5	using namespace std;
6
7
8	enum Majhong { Z, F, B, N, W, S, E, Yx, Tx, Wx, Nil };
9
10
11	Majhong determine(string mah) {
12	if (mah.size() == 1) {
13	if (mah.compare("Z") == 0) return Z;
14	if (mah.compare("F") == 0) return F;
15	if (mah.compare("B") == 0) return B;
16	if (mah.compare("N") == 0) return N;
17	if (mah.compare("W") == 0) return W;
18	if (mah.compare("S") == 0) return S;
19	if (mah.compare("E") == 0) return E;
20	}
21	else {
22	if (mah[0] == 'Y') return Yx;
23	if (mah[0] == 'T') return Tx;
24	if (mah[0] == 'W') return Wx;
25	}
26	return Nil;
27	}
28
29
30	bool compare(string a, string b) {
31	if (a.size() > b.size()) return true;
32	else if (a.size() > b.size()) return false;
33	else {
34	Majhong aM;
35	aM = determine(a);
36	Majhong bM;
37	bM = determine(b);
38	if (aM > bM) return true;
39	else if (aM < bM) return false;
40	else if (aM == bM && a.size() == 1) return true;
41	else {
42	if (a[1] <= b[1]) return true;
43	else if (a[1] > b[1]) return false;
44	}
45	}
46	return false;
47	}
48
49
50	int main() {
51	int times;
52	cin >> times;
53
54	while (times-- > 0) {
55	string mahjong[13];
56	for (int i = 0; i < 13; i++) {
57	cin >> mahjong[i];
58	}
59	sort(mahjong, mahjong + 13, compare);
60
61	for (int i = 0; i < 13; i++) {
62	cout << mahjong[i];
63	cout << " ";
64	}
65	cout << endl;
66	}
67	return 0;
68	}
69
70	/**************************************************************
71	Problem: 1247
72	User:
73	Language: C++
74	Result: Accepted
75	Time:8 ms
76	Memory:1720 kb
77	****************************************************************/

1	#include <iostream>
2	#include <math.h>
3
4
5	using namespace std;
6
7
8
9	long long len(long long num) {
10	long long n = 0;
11	while (num != 0) {
12	num /= 10;
13	n++;
14	}
15	return n;
16	}
17
18
19	long long zonetotal(long long len) {
20	if (len == 0) return 0;
21	if (len == 1) return 10;
22	return 9 * (long long)pow(10, (len - 1) / 2);
23	}
24
25
26	long long func(long long len) {
27	if (len == 0) return 0;
28	if (len == 1) return 10;
29	return func(len - 1) + zonetotal(len);
30	}
31
32
33	long long piecenumber(long long* piece, long long startp, long long endp) {
34	if (startp == 0) {
35	if (endp == startp) return piece[startp] - 1;
36	else return (piece[startp] - 1) * pow(10, (endp - startp)) + piecenumber(piece, startp + 1, endp);
37	}
38	if (endp == startp) return piece[startp];
39	return piece[startp] * pow(10, (endp - startp)) + piecenumber(piece, startp + 1, endp);
40	}
41
42
43	bool isplus(long long* left, long long* right, long long half) {
44	for (long long i = half - 1; i >= 0; i--) {
45	int a = left[i];
46	int b = right[i];
47	if (left[i] == right[i]) continue;
48	if (left[i] < right[i]) return true;
49	return false;
50	}
51	return true;
52	}
53
54
55	long long zonepart(long long num) {
56	long long length = len(num);
57	if (length == 1) return num + 1;
58	long long half = (length + 1) / 2;
59	long long left[23] = { 0 };
60	long long right[23] = { 0 };
61	for (long long i = 0; i < half; i++) {
62	right[i] = num % 10;
63	num /= 10;
64	}
65	if (length & 1) {
66	for (long long i = 0; i < half - 1; i++) {
67	left[half - i - 2] = num % 10;
68	num /= 10;
69	}
70	left[half - 1] = right[half - 1];
71	}
72	else {
73	for (long long i = 0; i < half; i++) {
74	left[half - i - 1] = num % 10;
75	num /= 10;
76	}
77	}
78
79	int p = piecenumber(left, 0, half - 1);
80	bool isss = isplus(left, right, half);
81	return piecenumber(left, 0, half - 1) + (isplus(left, right, half) ? 1 : 0);
82	}
83
84
85	int main() {
86	long long times;
87	cin >> times;
88	while (times-- > 0) {
89	long long num;
90	cin >> num;
91	if (num / 10 == 0) {
92	cout << num + 1 << endl;
93	continue;
94	}
95	int ttt = func(len(num) - 1);
96	long long total = zonepart(num) + func(len(num) - 1);
97	cout << total << endl;
98	}
99	return 0;
100	}
101
102	/**************************************************************
103	Problem: 1248
104	User:
105	Language: C++
106	Result: Accepted
107	Time:0 ms
108	Memory:1908 kb
109	****************************************************************/

1	#include <iostream>
2	#include <cmath>
3	#include <string>
4	#include <sstream>
5
6
7	using namespace std;
8
9
10	long long point[2] = { 1, 1 };
11	long long p[2] = { 0, 0 };
12	long long number;
13	stringstream ss;
14
15
16	long long num2point(long long num) {
17	if (num <= 4) {
18	switch (num) {
19	case 2: point[0] += 1;
20	case 1:
21	default: return 0;
22	case 3: point[0] += 1;
23	case 0:
24	case 4: point[1] += 1;
25	}
26	return 0;
27	}
28
29	long long piece = floor(logbl(num - 1) / 2);
30	long long blocksize = powl(4, piece);
31	long long blocknum = num / blocksize;
32	long long blocklen = sqrtl(blocksize);
33	long long least = num - blocksize * blocknum;
34	if (num % blocksize == 0) least = blocksize;
35
36	switch ((num - 1) / blocksize) {
37	case 1: {
38	point[0] += blocklen;
39	break;
40	}
41	case 2: point[0] += blocklen;
42	case 3: point[1] += blocklen;
43	}
44
45	return num2point(least);
46	}
47
48
49	void findpoint(long long num) {
50	point[0] = point[1] = 1;
51	num2point(num);
52	}
53
54
55	long long* point2num(long long* p) {
56	long long maxp = fmaxl(p[0], p[1]);
57	if (maxp <= 2) {
58	switch (p[0]) {
59	case 1: {
60	switch (p[1]) {
61	case 2: number += 3;
62	case 1: number += 1;
63	default: {
64	p[0] = p[1] = 0;
65	return p;
66	}
67	}
68	}
69	case 2: {
70	switch (p[1]) {
71	case 2: number += 1;
72	case 1: number += 2;
73	default: {
74	p[0] = p[1] = 0;
75	return p;
76	}
77	}
78	}
79	}
80	}
81	long long piece = floor(logbl(maxp-1));
82	long long blocksize = powl(4, piece);
83	long long blocklen = sqrtl(blocksize);
84	bool isaxisX = p[0] > blocklen;
85	bool isaxisY = p[1] > blocklen;
86	switch (isaxisX && isaxisY) {
87	case true: {
88	number += blocksize * 2;
89	p[0] -= blocklen;
90	p[1] -= blocklen;
91	return point2num(p);
92	}
93	case false: {
94	if (isaxisX) {
95	number += blocksize;
96	p[0] -= blocklen;
97	return point2num(p);
98	}
99	else {
100	number += blocksize * 3;
101	p[1] -= blocklen;
102	return point2num(p);
103	}
104	}
105	}
106	}
107
108
109	void findnum(long long* p) {
110	number = 0;
111	point2num(p);
112	}
113
114	long long* str2point(string str) {
115	p[0] = 0;
116	p[1] = 0;
117	auto comma = str.find(",");
118	if (comma == string::npos) return p;
119	auto len = str.length();
120	auto p0 = str.substr(1, comma - 1);
121	auto p1 = str.substr(comma + 1, len - comma - 2);
122	ss.clear();
123	ss << p0;
124	ss >> p[0];
125	ss.clear();
126	ss << p1;
127	ss >> p[1];
128	return p;
129	}
130
131	long long str2ll(string str) {
132	long long ll;
133	ss.clear();
134	ss << str;
135	ss >> ll;
136	return ll;
137	}
138
139	int main() {
140	long long times;
141	cin >> times;
142	while (times-- > 0) {
143	string str;
144	cin >> str;
145	long long* p = str2point(str);
146	if (p[0] == 0) {
147	long long num = str2ll(str);
148	findpoint(num);
149	cout << "(" << point[0] << "," << point[1] << ")" << endl;
150	continue;
151	}
152	findnum(p);
153	cout << number << endl;
154	}
155	}
156	/**************************************************************
157	Problem: 1249
158	User:
159	Language: C++
160	Result: Accepted
161	Time:1244 ms
162	Memory:4844 kb
163	****************************************************************/

1	#include <stdio.h>
2
3	using namespace std;
4
5	int read_int();
6	int* binarysearch(int* info);
7
8	int info[4] = { 0 };
9	int* prices;
10
11
12	int main() {
13	int days = read_int();
14	int kinds = read_int();
15	int* money = new int[days];
16	prices = new int[kinds];
17	for (int i = 0; i < days; i++) money[i] = read_int();
18	for (int i = 0; i < kinds; i++) prices[i] = read_int();
19
20	for (int i = 0; i < days; i++) {
21	info[0] = 0;
22	info[1] = kinds - 1;
23	info[2] = money[i];
24	binarysearch(info);
25	if (info[3] == -1) {
26	if (prices[info[0]] > info[2]) printf("%d\n", info[2]);
27	else if (prices[info[0]] < info[2] && info[2] < prices[info[1]]) printf("%d\n", info[2] - prices[info[0]]);
28	else printf("%d\n", info[2] - prices[info[1]]);
29	}
30	else printf("Meow\n");
31	}
32	return 0;
33	}
34
35
36	int read_int() {
37	char r;
38	bool start = false, neg = false;
39	int ret = 0;
40	while (true) {
41	r = getchar();
42	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && !start) {
43	continue;
44	}
45	if ((r - '0' < 0 \|\| r - '0'>9) && r != '-' && start) {
46	break;
47	}
48	if (start)ret *= 10;
49	start = true;
50	if (r == '-')neg = true;
51	else ret += r - '0';
52	}
53	if (!neg)
54	return ret;
55	else
56	return -ret;
57	}
58
59
60	int* binarysearch(int* info) {
61	if (info[1] - info[0] == 1) {
62	if (prices[info[0]] == info[2]) {
63	info[3] = info[0];
64	return info;
65	}
66	else if (prices[info[1]] == info[2]) {
67	info[3] = info[1];
68	return info;
69	}
70	else {
71	info[3] = -1;
72	return info;
73	}
74	}
75	auto mid = (info[0] + info[1]) / 2;
76	if (prices[mid] < info[2]) info[0] = mid;
77	else info[1] = mid;
78	return binarysearch(info);
79	}
80
81	/**************************************************************
82	Problem: 1251
83	User:
84	Language: C++
85	Result: Accepted
86	Time:216 ms
87	Memory:9032 kb
88	****************************************************************/

1	import java.util.Arrays;
2	import java.util.Scanner;
3
4	public class Main {
5	public static void main(String[] args) {
6	Scanner input = new Scanner(System.in);
7	int arrayLength = input.nextInt();
8	long target = input.nextLong();
9	long[] array = new long[arrayLength];
10	boolean[] isSameBefore = new boolean[arrayLength];
11	for(int i = 0; i<arrayLength; i++) {
12	array[i] = input.nextLong();
13	if(i != 0 && array[i] == array[i - 1]) {
14	isSameBefore[i] = true;
15	}
16	}
17	input.close();
18
19	long times = 0;
20	if(target==0) {
21	if(Arrays.binarySearch(array, 0, arrayLength, 0) >= 0) {
22	for(int i = 0; i < arrayLength; i++) {
23	if(!isSameBefore[i] && array[i] != 0) {
24	times++;
25	}
26	else if(array[i] == 0) {
27	if(i == arrayLength - 1) {
28	break;
29	}
30	if(array[i + 1] == 0) {
31	times++;
32	for(int j = i + 1; j < arrayLength; j++) {
33	if(!isSameBefore[j]) {
34	i = j - 1;
35	break;
36	}
37	else if(j == arrayLength - 1) {
38	i = j;
39	break;
40	}
41	}
42	}
43	}
44	}
45	}
46	}
47	else {
48	for(int i = 0; i < arrayLength - 1; i++) {
49	if(isSameBefore[i] \|\| array[i] == 0) continue;
50	if(target % array[i] == 0) {
51	long key = target/array[i];
52	if(key<array[i]) continue;
53	if(Arrays.binarySearch(array, i+1, arrayLength, key) >= 0) {
54	times++;
55	}
56	}
57	}
58	}
59	System.out.println(times);
60	}
61	}
62
63	/**************************************************************
64	Problem: 1253
65	User:
66	Language: Java
67	Result: Accepted
68	Time:1092 ms
69	Memory:42520 kb
70	****************************************************************/

1	import java.util.Scanner;
2
3	public class Main {
4	private static int[] array;
5	private static long cost;
6	public static void main(String[] args) {
7	Scanner input = new Scanner(System.in);
8	int len = input.nextInt();
9	array = new int[len];
10	for(int i = 0; i < len; i++) array[i] = input.nextInt();
11	input.close();
12	mergeSort(0, len-1);
13	System.out.printf("%d\n", cost);
14	}
15
16	private static void mergeSort(int low, int mid, int high) {
17	int[] temp = new int[high - low + 1];
18	int i = low, j = mid + 1, k = 0;
19	while(i <= mid && j <= high) {
20	if (array[i] > array[j]) {
21	cost += (long)array[j] * (mid - i + 1);
22	for(int t = i; t <= mid; t++) cost += array[t];
23	temp[k++] = array[j++];
24	}
25	else {
26	temp[k++] = array[i++];
27	}
28	}
29	while(i <= mid) temp[k++] = array[i++];
30	while(j <= high) temp[k++] = array[j++];
31	for(int t = 0; t < high - low + 1; t++) array[low + t] = temp[t];
32	}
33
34	private static void mergeSort(int low, int high) {
35	if (low >= high) return;
36	int mid = (low + high) >> 1;
37	mergeSort(low, mid);
38	mergeSort(mid + 1, high);
39	mergeSort(low, mid, high);
40	}
41	}
42
43	/**************************************************************
44	Problem: 1257
45	User:
46	Language: Java
47	Result: Accepted
48	Time:2136 ms
49	Memory:42024 kb
50	****************************************************************/

1	import java.io.*;
2	import java.util.StringTokenizer;
3
4	public class Main {
5	public static void main(String[] args) {
6	InputReader input = new InputReader(System.in);
7	PrintWriter out = new PrintWriter(System.out);
8	int testCase = input.nextInt();
9	while(testCase-->0) {
10	int terms = input.nextInt();
11	LinkedList polynomial0 = new LinkedList();
12	while(terms-->0) polynomial0.addElement(input.nextInt(), input.nextInt());
13	terms = input.nextInt();
14	LinkedList polynomial1 = new LinkedList();
15	while(terms-->0) polynomial1.addElement(input.nextInt(), input.nextInt());
16	terms = input.nextInt();
17	int[] queries = new int[terms];
18	boolean isContinue = true;
19	for (int i = 0; i < terms; i++) queries[i] = input.nextInt();
20	LinkedList p = new LinkedList();
21	Node temp0 = polynomial0.head.next;
22	Node temp1 = polynomial1.head.next;
23	while (temp0!=null && temp1!=null) {
24	if(temp0.exponent==-1) {
25	if(temp1.exponent==-1) break;
26	p.addElement(temp1.coefficient, temp1.exponent);
27	temp1 = temp1.next;
28	}
29	else if(temp1.exponent==-1) {
30	if(temp0.exponent==-1) break;
31	p.addElement(temp0.coefficient, temp0.exponent);
32	temp0 = temp0.next;
33	}
34	else if(temp0.exponent > temp1.exponent) {
35	p.addElement(temp1.coefficient, temp1.exponent);
36	temp1 = temp1.next;
37	}
38	else if(temp0.exponent < temp1.exponent) {
39	p.addElement(temp0.coefficient, temp0.exponent);
40	temp0 = temp0.next;
41	}
42	else {
43	p.addElement(temp0.coefficient+temp1.coefficient, temp0.exponent);
44	temp0 = temp0.next;
45	temp1 = temp1.next;
46	}
47	}
48	Node temp = p.head.next;
49	for (int i = 0; i < terms; i++) {
50	if (queries[i] > p.last.exponent) {
51	for (; i < terms; i++) out.printf("%d ", 0);
52	break;
53	}
54	for (; temp.exponent > -1; temp = temp.next) {
55	if (queries[i] == temp.exponent) {
56	out.printf("%d ", temp.coefficient);
57	break;
58	}
59	else if (queries[i] < temp.exponent) {
60	out.printf("%d ", 0);
61	break;
62	}
63	}
64	}
65	out.println();
66	}
67	out.close();
68	}
69
70	private static class Node {
71	int coefficient;
72	int exponent;
73	Node next;
74
75	Node(int coefficient, int exponent) {
76	this.coefficient = coefficient;
77	this.exponent = exponent;
78	}
79	}
80
81	private static class LinkedList {
82	Node head;
83	Node tail;
84	Node last;
85
86	LinkedList() {
87	head = new Node(0, 0);
88	tail = new Node(0, -1);
89	last = head;
90	}
91
92	void addElement(Node node) {
93	node.next = tail;
94	last.next = node;
95	last = last.next;
96	}
97
98	void addElement(int coefficient, int exponent) {
99	addElement(new Node(coefficient, exponent));
100	}
101	}
102
103	private static class InputReader {
104	BufferedReader reader;
105	StringTokenizer tokenizer;
106
107	InputReader(InputStream stream) {
108	reader = new BufferedReader(new InputStreamReader(stream), 32768);
109	tokenizer = null;
110	}
111
112	String next() {
113	while (tokenizer == null \|\| !tokenizer.hasMoreTokens()) {
114	try {
115	tokenizer = new StringTokenizer(reader.readLine());
116	} catch (IOException e) {
117	throw new RuntimeException(e);
118	}
119	}
120	return tokenizer.nextToken();
121	}
122
123	public int nextInt() {
124	return Integer.parseInt(next());
125	}
126	}
127	}
128
129	/**************************************************************
130	Problem: 1261
131	User:
132	Language: Java
133	Result: Accepted
134	Time:1948 ms
135	Memory:126244 kb
136	****************************************************************/

1	#include <stdio.h>
2
3	using namespace std;
4
5	struct Node {
6	int id;
7	int count;
8	Node* previous;
9	Node* next;
10	Node(int id, int count) {
11	this->id = id;
12	this->count = count;
13	previous = NULL;
14	next = NULL;
15	}
16	};
17
18	class linkedList {
19	public:
20	Node* head, * tail;
21	int length;
22
23	linkedList(int id, int count) {
24	length = 1;
25	head = new Node(id, count);
26	tail = head;
27	}
28
29	void addElement(Node* node) {
30	length++;
31	tail->next = node;
32	node->previous = tail;
33	tail = node;
34	}
35
36	void addElement(int id, int count) {
37	addElement(new Node(id, count));
38	}
39
40	void del(Node* node) {
41	if (node == head) head = head->previous;
42	node->previous->next = node->next;
43	node->next->previous = node->previous;
44	delete(node);
45	length--;
46	}
47
48	void loop() {
49	if (length == 1) return;
50	head->previous = tail;
51	tail->next = head;
52	}
53	};
54
55	int readInt();
56
57	int main() {
58	int testCase = readInt();
59	while (testCase--) {
60	int members = readInt();
61	int loop = readInt();
62	linkedList circle = linkedList(1, readInt());
63	for (int i = 2; i <= members; i++) circle.addElement(i, readInt());
64	circle.loop();
65	Node* start = circle.head;
66	while (circle.length != 1) {
67	loop %= circle.length;
68	Node* temp = start;
69	if (circle.length - loop >= circle.length >> 1) {
70	while (loop--) temp = temp->next;
71	start = temp;
72	loop = temp->previous->count;
73	circle.del(temp->previous);
74	}
75	else {
76	loop = circle.length - loop;
77	while (loop--) temp = temp->previous;
78	start = temp;
79	loop = temp->previous->count;
80	circle.del(temp->previous);
81	}
82	}
83	printf("%d\n", circle.head->id);
84	}
85	return 0;
86	}
87
88	int readInt() {
89	char r;
90	bool start = false, neg = false;
91	int ret = 0;
92	while (true) {
93	r = getchar();
94	if ((r - '0' < 0 \|\| r - '0' > 9) && r != '-' && !start) continue;
95	if ((r - '0' < 0 \|\| r - '0' > 9) && r != '-' && start) break;
96	if (start) ret *= 10;
97	start = true;
98	if (r == '-') neg = true;
99	else ret += r - '0';
100	}
101	if (!neg) return ret;
102	else return -ret;
103	}
104
105	/**************************************************************
106	Problem: 1264
107	User:
108	Language: C++
109	Result: Accepted
110	Time:1240 ms
111	Memory:1480 kb
112	****************************************************************/

1	#include <stdio.h>
2
3	int generateNext(int number, int maxLen);
4
5	int max;
6
7	int main() {
8	int testCase;
9	scanf("%d", &testCase);
10	while (testCase--) {
11	int digit, number;
12	scanf("%d %d", &digit, &number);
13	if (number == 0) {
14	printf("%d\n", number);
15	continue;
16	}
17	int maxLen = 1;
18	while (digit--) maxLen *= 10;
19	max = number;
20	int slow = generateNext(number, maxLen);
21	int fast = generateNext(slow, maxLen);
22	while (slow != fast) {
23	slow = generateNext(slow, maxLen);
24	fast = generateNext(generateNext(fast, maxLen), maxLen);
25	}
26	printf("%d\n", max);
27	}
28	return 0;
29	}
30
31	int generateNext(int number, int maxLen) {
32	long long temp = (long long)number * (long long)number;
33	while (temp / maxLen != 0) temp /= 10;
34	if (temp > max) max = (int)temp;
35	return (int)temp;
36	}
37	/**************************************************************
38	Problem: 1265
39	User:
40	Language: C
41	Result: Accepted
42	Time:1644 ms
43	Memory:1092 kb
44	****************************************************************/

1	import java.io.BufferedReader;
2	import java.io.IOException;
3	import java.io.InputStream;
4	import java.io.InputStreamReader;
5	import java.util.StringTokenizer;
6
7	public class Main {
8	private static int max;
9	public static void main(String[] args) {
10	InputReader input = new InputReader(System.in);
11	int testCase = input.nextInt();
12	while (testCase-- > 0) {
13	int digit = input.nextInt();
14	int number = input.nextInt();
15	if (number == 0) {
16	System.out.printf("%d\n", number);
17	continue;
18	}
19	int maxLen = 1;
20	while (digit-->0) maxLen *= 10;
21	max = number;
22	int slow = generateNext(number, maxLen);
23	int fast = generateNext(slow, maxLen);
24	while (slow != fast) {
25	slow = generateNext(slow, maxLen);
26	fast = generateNext(generateNext(fast, maxLen), maxLen);
27	}
28	System.out.printf("%d\n", max);
29	}
30	}
31
32	private static class InputReader {
33	BufferedReader reader;
34	StringTokenizer tokenizer;
35
36	InputReader(InputStream stream) {
37	reader = new BufferedReader(new InputStreamReader(stream), 32768);
38	tokenizer = null;
39	}
40
41	String next() {
42	while (tokenizer == null \|\| !tokenizer.hasMoreTokens()) {
43	try {
44	tokenizer = new StringTokenizer(reader.readLine());
45	} catch (IOException e) {
46	throw new RuntimeException(e);
47	}
48	}
49	return tokenizer.nextToken();
50	}
51
52	int nextInt() {
53	return Integer.parseInt(next());
54	}
55	}
56
57	private static int generateNext(int number, int maxLen) {
58	long temp = (long)number * (long)number;
59	while (temp / maxLen != 0) temp /= 10;
60	if (temp > max) max = (int)temp;
61	return (int)temp;
62	}
63	}
64
65	/**************************************************************
66	Problem: 1265
67	User:
68	Language: Java
69	Result: Accepted
70	Time:1820 ms
71	Memory:19344 kb
72	****************************************************************/

1	#define _CRT_SECURE_NO_WARNINGS
2	#include <stdio.h>
3	#include <stack>
4
5	using namespace std;
6
7	char getBracket();
8	char getPair(char c);
9
10	int main() {
11	int testCase;
12	scanf("%d", &testCase);
13	while (testCase--) {
14	int len;
15	scanf("%d", &len);
16	char c;
17	if (len == 1) {
18	c = getBracket();
19	printf("NO\n");
20	continue;
21	}
22	std::stack<char> brackets;
23	bool hasRight = false;
24	while (len--) {
25	c = getBracket();
26	switch (c) {
27	case ')':
28	case ']':
29	case '}': {
30	if (brackets.empty()) {
31	hasRight = true;
32	break;
33	}
34	if (getPair(c) == brackets.top()) brackets.pop();
35	else hasRight = true;
36	break;
37	}
38	case '(':
39	case '[':
40	case '{': brackets.push(c);
41	}
42	}
43	if(!hasRight && brackets.empty()) printf("YES\n");
44	else printf("NO\n");
45	}
46	return 0;
47	}
48
49	bool isBracket(char c) {
50	return c == '(' \|\| c == '[' \|\| c == '{' \|\| c == ')' \|\| c == ']' \|\| c == '}';
51	}
52
53	char getBracket() {
54	char c = getchar();
55	while (!isBracket(c)) c = getchar();
56	return c;
57	}
58
59	char getPair(char c) {
60	switch (c) {
61	case '(': return ')';
62	case ')': return '(';
63	case '[': return ']';
64	case ']': return '[';
65	case '{': return '}';
66	case '}': return '{';
67	default: return ' ';
68	}
69	}
70	/**************************************************************
71	Problem: 1214
72	User:
73	Language: C++
74	Result: Accepted
75	Time:0 ms
76	Memory:1252 kb
77	****************************************************************/

1	#define _CRT_SECURE_NO_WARNINGS
2	#include <stdio.h>
3	#include <deque>
4
5	using namespace std;
6
7	int main() {
8	int size;
9	scanf("%d", &size);
10	int XORsum = 0;
11	deque<int> window;
12	deque<int> INDEX;
13	int index = 0;
14	int t;
15	scanf("%d", &t);
16	for (; index < size; index++) {
17	while (!window.empty() && t > window.back()) {
18	window.pop_back();
19	INDEX.pop_back();
20	}
21	window.push_back(t);
22	INDEX.push_back(index);
23	scanf("%d", &t);
24	}
25	XORsum ^= window.front();
26	while (t != -1) {
27	while (!window.empty() && t > window.back()) {
28	window.pop_back();
29	INDEX.pop_back();
30	}
31	if (!INDEX.empty() && INDEX.front() <= index - size) {
32	INDEX.pop_front();
33	window.pop_front();
34	}
35	window.push_back(t);
36	INDEX.push_back(index);
37	XORsum ^= window.front();
38	scanf("%d", &t);
39	index++;
40	}
41	printf("%d\n", XORsum);
42	return 0;
43	}
44
45	/**************************************************************
46	Problem: 1215
47	User:
48	Language: C++
49	Result: Accepted
50	Time:324 ms
51	Memory:1252 kb
52	****************************************************************/

1	import java.util.Deque;
2	import java.util.LinkedList;
3	import java.util.Scanner;
4
5	public class Main {
6	public static void main(String[] args) {
7	Scanner input = new Scanner(System.in);
8	Deque<Integer> window = new LinkedList<>();
9	Deque<Integer> indexs = new LinkedList<>();
10	int size = input.nextInt();
11	int n = input.nextInt();
12	int index = 0;
13	int XORsum = 0;
14	for (; index < size; index++) {
15	while(!window.isEmpty() && n > window.getLast()) {
16	window.pollLast();
17	indexs.pollLast();
18	}
19	window.addLast(n);
20	indexs.addLast(index);
21	n = input.nextInt();
22	}
23	XORsum ^= window.getFirst();
24	while(n != -1) {
25	while(!window.isEmpty() && n > window.getLast()) {
26	window.pollLast();
27	indexs.pollLast();
28	}
29	if(!indexs.isEmpty() && indexs.getFirst() <= index - size) {
30	window.pollFirst();
31	indexs.pollFirst();
32	}
33	window.addLast(n);
34	indexs.addLast(index);
35	XORsum ^= window.getFirst();
36	n = input.nextInt();
37	index++;
38	}
39	System.out.printf("%d\n", XORsum);
40	}
41	}
42
43	/**************************************************************
44	Problem: 1215
45	User:
46	Language: Java
47	Result: Accepted
48	Time:1648 ms
49	Memory:47180 kb
50	****************************************************************/

1	import java.util.Scanner;
2	import java.util.regex.Matcher;
3	import java.util.regex.Pattern;
4
5	public class Main {
6	public static void main(String[] args) {
7	Scanner input = new Scanner(System.in);
8	int suspicious = input.nextInt();
9	int repeaters = 0;
10	while (suspicious-->0) {
11	String saying = input.next();
12	String response = input.next();
13	Pattern pattern = Pattern.compile(saying.substring(0, saying.length() / 3 + ((saying.length() % 3 == 0) ? 0 : 1)));
14	Matcher matcher = pattern.matcher(response);
15	if (matcher.find()) repeaters += 1;
16	}
17	input.close();
18	System.out.printf("%d\n", repeaters);
19	}
20	}
21
22	/**************************************************************
23	Problem: 1271
24	User:
25	Language: Java
26	Result: Accepted
27	Time:996 ms
28	Memory:43376 kb
29	****************************************************************/

1	import java.util.ArrayList;
2	import java.util.Comparator;
3	import java.util.Scanner;
4
5	public class Main {
6	public static void main(String[] args) {
7	ArrayList<Integer> sticks = new ArrayList<>();
8	Scanner input = new Scanner(System.in);
9	int testCase = input.nextInt();
10	while(testCase-->0) {
11	sticks.clear();
12	int n = input.nextInt();
13	while(n-->0) sticks.add(input.nextInt());
14	int sum = 0;
15	while(sticks.size() != 1) {
16	sticks.sort(new Comparator<Integer>() {
17	@Override
18	public int compare(Integer o1, Integer o2) {
19	return o2 - o1;
20	}
21	});
22	int tmp = sticks.get(sticks.size() - 1) + sticks.get(sticks.size() - 2);
23	sticks.remove(sticks.size() - 1);
24	sticks.remove(sticks.size() - 1);
25	sticks.add(tmp);
26	sum += tmp;
27	}
28	System.out.printf("%d\n", sum);
29	}
30	}
31	}
32
33	/**************************************************************
34	Problem: 1280
35	User:
36	Language: Java
37	Result: Accepted
38	Time:404 ms
39	Memory:29132 kb
40	****************************************************************/

1	import java.util.PriorityQueue;
2	import java.util.Queue;
3	import java.util.Scanner;
4
5	public class Main {
6	public static void main(String[] args) {
7	Scanner input = new Scanner(System.in);
8	long t = input.nextInt(), k = input.nextInt(), s = input.nextInt();
9	Queue<Long> pq = new PriorityQueue<>();
10	for(int i = 1; i <= t; i++) {
11	long tmp = A062028(i + s);
12	if(pq.size() < k) pq.offer(tmp);
13	else if(tmp > pq.peek()) {
14	pq.poll();
15	pq.offer(tmp);
16	}
17	if(i % 100 == 0) {
18	System.out.printf("%d ", pq.peek());
19	s = pq.peek();
20	}
21	}
22	}
23
24	private static long A062028(long n) {
25	long res = n;
26	while(n != 0) {
27	res += n % 10;
28	n /= 10;
29	}
30	return res;
31	}
32	}
33
34	/**************************************************************
35	Problem: 1285
36	User:
37	Language: Java
38	Result: Accepted
39	Time:816 ms
40	Memory:83224 kb
41	****************************************************************/

1	2
2	4 6
3	1 2
4	1 3
5	1 4
6	2 3
7	2 4
8	3 4
9	6 8
10	2 5
11	5 4
12	4 3
13	4 1
14	1 3
15	2 3
16	2 6
17	5 6

1	import java.util.*;
2
3	public class Main {
4	final static int IN = 0, OUT = 1;
5
6	public static void main(String[] args) {
7	Scanner input = new Scanner(System.in);
8	PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> (o2 - o1));
9	Stack<Integer> stack = new Stack<>();
10
11	int testCase = input.nextInt();
12	while(testCase-->0) {
13	int soldiers = input.nextInt();
14	int constrains = input.nextInt();
15	int[][] degree = new int[soldiers + 1][2];
16	LinkedList<Integer>[] adjacencyList = new LinkedList[degree.length];
17	for(int i = 1; i < adjacencyList.length; i++) adjacencyList[i] = new LinkedList<>();
18	while(constrains-->0) {
19	int u = input.nextInt();
20	int v = input.nextInt();
21	adjacencyList[v].push(u);
22	degree[u][OUT] += 1;
23	degree[v][IN] += 1;
24	}
25
26	while(!priorityQueue.isEmpty()) priorityQueue.poll();
27	for(int i = 1; i < degree.length; i++) if(degree[i][OUT] == 0) priorityQueue.offer(i);
28	while(!priorityQueue.isEmpty()) {
29	int peek = priorityQueue.peek();
30	stack.push(peek);
31	priorityQueue.poll();
32	if(degree[peek][IN] != 0) {
33	for(int i : adjacencyList[peek]) {
34	degree[i][OUT] -= 1;
35	if(degree[i][OUT] == 0) priorityQueue.offer(i);
36	}
37	}
38	}
39
40	while(!stack.isEmpty()) System.out.printf("%d ", stack.pop());
41	System.out.println();
42	}
43	}
44	}
45
46	/**************************************************************
47	Problem: 1288
48	User:
49	Language: Java
50	Result: Accepted
51	Time:2572 ms
52	Memory:85164 kb
53	****************************************************************/

1	2
2	4 6
3	1 2
4	1 3
5	1 4
6	2 3
7	2 4
8	3 4
9	6 8
10	2 5
11	5 4
12	4 3
13	4 1
14	1 3
15	2 3
16	2 6
17	5 6