OJ – 第6页 – 柳婼の blog

L3-002. 堆栈-PAT团体程序设计天梯赛GPLT（树状数组）

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。

输入格式：

输入第一行给出正整数N（<= 105）。随后N行，每行给出一个操作指令，为下列3种指令之一：

Push key
Pop
PeekMedian
其中Push表示入栈，key是不超过105的正整数；Pop表示出栈；PeekMedian表示查中值。

输出格式：

对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“Invalid”。

输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

分析：如果排序查找的话会超时，用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快～

#include <cstdio>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <stack>

#define lowbit(i) ((i) & (-i))

const int maxn = 100010;

using namespace std;

int c[maxn];

stack<int> s;

void update(int x, int v) {

for(int i = x; i < maxn; i += lowbit(i))

c[i] += v;

}

int getsum(int x) {

int sum = 0;

for(int i = x; i >= 1; i -= lowbit(i))

sum += c[i];

return sum;

}

void PeekMedian() {

int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;

while(left < right) {

mid = (left + right) / 2;

if(getsum(mid) >= k)

right = mid;

else

left = mid + 1;

}

printf("%d\n", left);

}

int main() {

int n, temp;

scanf("%d", &n);

char str[15];

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

scanf("%s", str);

if(str[1] == 'u') {

scanf("%d", &temp);

s.push(temp);

update(temp, 1);

} else if(str[1] == 'o') {

if(!s.empty()) {

update(s.top(), -1);

printf("%d\n", s.top());

s.pop();

} else {

printf("Invalid\n");

}

} else {

if(!s.empty())

PeekMedian();

else

printf("Invalid\n");

}

return 0;

}

1075. PAT Judge (25)-PAT甲级真题

The ranklist of PAT is generated from the status list, which shows the scores of the submittions. This time you are supposed to generate the ranklist for PAT.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 positive integers, N (<=104), the total number of users, K (<=5), the total number of problems, and M (<=105), the total number of submittions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submittion in the following format:

user_id problem_id partial_score_obtained

where partial_score_obtained is either -1 if the submittion cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.

Output Specification:

For each test case, you are supposed to output the ranklist in the following format:

rank user_id total_score s[1] … s[K]

where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-” must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.

The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

Sample Input:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0
Sample Output:
1 00002 63 20 25 – 18
2 00005 42 20 0 22 –
2 00007 42 – 25 – 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 –

分析：结构体数组中passnum统计完整通过的题目个数，isshown在用户有一题通过了编译器（不管得不得0分）的时候置为true。vector<int> score;记录每门课的最高分
因为没有通过编译器的分数为0，但是没有提交过的分数为“-”，所以把有一门课每次都是未通过编译器的那门课分数置为-2。初始化数组分数为-1，所以可以根据-1和-2判断当前分数是提交过了没通过编译器的，还是没提交过的题目
注意：因为最后一个测试样例是有一个人一开始得到了分数，后来提交了一次没有通过编译器的，所以要判断在分数每次更新最大值之后if(v[id].score[num] == -1)，说明最好成绩只是-1（也就是没通过编译器或者没有提交过），这个时候再置v[id].score[num] = -2，否则会误操作把已经提交过很好分数的人的成绩抹掉成了-2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int rank, id, total = 0;
    vector<int> score;
    int passnum = 0;
    bool isshown = false;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.passnum != b.passnum)
        return a.passnum > b.passnum;
    else
        return a.id < b.id;
}

int main() {
    int n, k, m, id, num, score;
    scanf("%d %d %d", &n, &k, &m);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++)
        v[i].score.resize(k + 1, -1);
    vector<int> full(k + 1);
    for(int i = 1; i <= k; i++)
        scanf("%d", &full[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &id, &num, &score);
        v[id].id = id;
        v[id].score[num] = max(v[id].score[num], score);
        if(score != -1)
            v[id].isshown = true;
        else if(v[id].score[num] == -1)
            v[id].score[num] = -2;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            if(v[i].score[j] != -1 && v[i].score[j] != -2)
                v[i].total += v[i].score[j];
            if(v[i].score[j] == full[j])
                v[i].passnum++;
        }
    }
    sort(v.begin() + 1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        v[i].rank = i;
        if(i != 1 && v[i].total == v[i - 1].total)
            v[i].rank = v[i - 1].rank;
    }
    for(int i = 1; i <= n; i++) {
        if(v[i].isshown == true) {
            printf("%d %05d %d", v[i].rank, v[i].id, v[i].total);
            for(int j = 1; j <= k; j++) {
                if(v[i].score[j] != -1 && v[i].score[j] != -2)
                    printf(" %d", v[i].score[j]);
                else if(v[i].score[j] == -1)
                    printf(" -");
                else
                    printf(" 0");
            }
            printf("\n");
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int rank, id, total = 0;

vector<int> score;

int passnum = 0;

bool isshown = false;

};

bool cmp1(node a, node b) {

if(a.total != b.total)

return a.total > b.total;

else if(a.passnum != b.passnum)

return a.passnum > b.passnum;

else

return a.id < b.id;

}

int main() {

int n, k, m, id, num, score;

scanf("%d %d %d", &n, &k, &m);

vector<node> v(n + 1);

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

v[i].score.resize(k + 1, -1);

vector<int> full(k + 1);

for(int i = 1; i <= k; i++)

scanf("%d", &full[i]);

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

scanf("%d %d %d", &id, &num, &score);

v[id].id = id;

v[id].score[num] = max(v[id].score[num], score);

if(score != -1)

v[id].isshown = true;

else if(v[id].score[num] == -1)

v[id].score[num] = -2;

}

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

for(int j = 1; j <= k; j++) {

if(v[i].score[j] != -1 && v[i].score[j] != -2)

v[i].total += v[i].score[j];

if(v[i].score[j] == full[j])

v[i].passnum++;

}

sort(v.begin() + 1, v.end(), cmp1);

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

v[i].rank = i;

if(i != 1 && v[i].total == v[i - 1].total)

v[i].rank = v[i - 1].rank;

}

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

if(v[i].isshown == true) {

printf("%d %05d %d", v[i].rank, v[i].id, v[i].total);

for(int j = 1; j <= k; j++) {

if(v[i].score[j] != -1 && v[i].score[j] != -2)

printf(" %d", v[i].score[j]);

else if(v[i].score[j] == -1)

printf(" -");

else

printf(" 0");

}

printf("\n");

}

return 0;

}

1071. Speech Patterns (25)-PAT甲级真题（map应用）

People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

Input Specification:

Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return ‘\n’. The input contains at least one alphanumerical character, i.e., one character from the set [0-9 A-Z a-z].

Output Specification:

For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

Sample Input:
Can1: “Can a can can a can? It can!”
Sample Output:
can 5

题目大意：统计单词个数～大小写字母+数字的组合才是合法的单词，给出一个字符串，求出现的合法的单词的个数最多的那个单词，以及它出现的次数。如果有并列的，那么输出字典序里面的第一个～～
分析：用map很简单的~不过呢~有几个注意点～：
1. 大小写不区分，所以统计之前要先s[i] = tolower(s[i]);
2. [0-9 A-Z a-z]可以简写为cctype头文件里面的一个函数isalnum～～
3. 必须用getline读入一长串的带空格的字符串～～
4. 一定要当t不为空的时候m[t]++，因为t为空也会被统计的！！！～～
5. 最重要的是～如果i已经到了最后一位，不管当前位是不是字母数字，都得将当前这个t放到map里面（只要t长度不为0）～

#include <iostream>
#include <map>
#include <cctype>
using namespace std;
int main() {
    string s, t;
    getline(cin, s);
    map<string, int> m;
    for(int i = 0; i < s.length(); i++) {
        if(isalnum(s[i])) {
            s[i] = tolower(s[i]);
            t += s[i];
        }
        if(!isalnum(s[i]) || i == s.length() - 1){
            if(t.length() != 0) m[t]++;
            t = "";
        }
    }
    int maxn = 0;
    for(auto it = m.begin(); it != m.end(); it++) {
        if(it->second > maxn) {
            t = it->first;
            maxn = it->second;
        }
    }
    cout << t << " " << maxn;
    return 0;
}

#include <iostream>

#include <map>

#include <cctype>

using namespace std;

int main() {

string s, t;

getline(cin, s);

map<string, int> m;

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

if(isalnum(s[i])) {

s[i] = tolower(s[i]);

t += s[i];

}

if(!isalnum(s[i]) || i == s.length() - 1){

if(t.length() != 0) m[t]++;

t = "";

}

int maxn = 0;

for(auto it = m.begin(); it != m.end(); it++) {

if(it->second > maxn) {

t = it->first;

maxn = it->second;

}

cout << t << " " << maxn;

return 0;

}

1055. The World’s Richest (25)-PAT甲级真题

Forbes magazine publishes every year its list of billionaires based on the annual ranking of the world’s wealthiest people. Now you are supposed to simulate this job, but concentrate only on the people in a certain range of ages. That is, given the net worths of N people, you must find the M richest people in a given range of their ages.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: N (<=105) – the total number of people, and K (<=103) – the number of queries. Then N lines follow, each contains the name (string of no more than 8 characters without space), age (integer in (0, 200]), and the net worth (integer in [-106, 106]) of a person. Finally there are K lines of queries, each contains three positive integers: M (<= 100) – the maximum number of outputs, and [Amin, Amax] which are the range of ages. All the numbers in a line are separated by a space.

Output Specification:

For each query, first print in a line Case #X: where X is the query number starting from 1. Then output the M richest people with their ages in the range [Amin, Amax]. Each person’s information occupies a line, in the format

Name Age Net_Worth
The outputs must be in non-increasing order of the net worths. In case there are equal worths, it must be in non-decreasing order of the ages. If both worths and ages are the same, then the output must be in non-decreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output “None”.
Sample Input:
12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50
Sample Output:
Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

题目大意：给出n个人的姓名、年龄和拥有的钱，然后进行k次查询，每次查询输出在年龄区间内的财富值的从大到小的前m个人的信息。如果财富值相同就就先输出年龄小的，如果年龄相同就把名字按照字典序排序输出～
分析：不能先排序然后根据每一个条件再新建一个数组、对新数组排序的方法，这样测试点2会超时～因为n和m的悬殊太大了，n有10的5次方，m却只有100个。所以先把所有的人按照财富值排序，再建立一个数组book标记每个年龄段拥有的人的数量，遍历数组并统计相应年龄的人数，当当前年龄的人的数量不超过100的时候压入新的数组，多出来的不要压入新数组中（也就是说只取每个年龄的前100名，因为一个年龄段最小的就是一个年龄，即使这样也不会超过100个需要输出），再从这个新的数组里面取符合相应年龄的人的信息～～

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
struct node {
    char name[10];
    int age, money;
};
int cmp1(node a, node b) {
    if(a.money != b.money)
        return a.money > b.money;
    else if(a.age != b.age)
        return a.age < b.age;
    else
        return (strcmp(a.name, b.name) < 0);
}
int main() {
    int n, k, num, amin, amax;
    scanf("%d %d", &n, &k);
    vector<node> vt(n), v;
    vector<int> book(205, 0);
    for(int i = 0; i < n; i++)
        scanf("%s %d %d", vt[i].name, &vt[i].age, &vt[i].money);
    sort(vt.begin(), vt.end(), cmp1);
    for(int i = 0; i < n; i++) {
        if(book[vt[i].age] < 100) {
            v.push_back(vt[i]);
            book[vt[i].age]++;
        }
    }
    for(int i = 0; i < k; i++) {
        scanf("%d %d %d", &num, &amin, &amax);
        vector<node> t;
        for(int j = 0; j < v.size(); j++) {
            if(v[j].age >= amin && v[j].age <= amax)
                t.push_back(v[j]);
        }
        if(i != 0) printf("\n");
        printf("Case #%d:", i + 1);
        int flag = 0;
        for(int j = 0; j < num && j < t.size(); j++) {
            printf("\n%s %d %d", t[j].name, t[j].age, t[j].money);
            flag = 1;
        }
        if(flag == 0) printf("\nNone");
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstring>

using namespace std;

struct node {

char name[10];

int age, money;

};

int cmp1(node a, node b) {

if(a.money != b.money)

return a.money > b.money;

else if(a.age != b.age)

return a.age < b.age;

else

return (strcmp(a.name, b.name) < 0);

}

int main() {

int n, k, num, amin, amax;

scanf("%d %d", &n, &k);

vector<node> vt(n), v;

vector<int> book(205, 0);

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

scanf("%s %d %d", vt[i].name, &vt[i].age, &vt[i].money);

sort(vt.begin(), vt.end(), cmp1);

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

if(book[vt[i].age] < 100) {

v.push_back(vt[i]);

book[vt[i].age]++;

}

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

scanf("%d %d %d", &num, &amin, &amax);

vector<node> t;

for(int j = 0; j < v.size(); j++) {

if(v[j].age >= amin && v[j].age <= amax)

t.push_back(v[j]);

}

if(i != 0) printf("\n");

printf("Case #%d:", i + 1);

int flag = 0;

for(int j = 0; j < num && j < t.size(); j++) {

printf("\n%s %d %d", t[j].name, t[j].age, t[j].money);

flag = 1;

}

if(flag == 0) printf("\nNone");

}

return 0;

}

1037. Magic Coupon (25)-PAT甲级真题（贪心算法）

The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!

For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:

Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.

Output Specification:

For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:
4
1 2 4 -1
4
7 6 -2 -3
Sample Output:
43
题目大意：给出两个数字序列，从这两个序列中分别选取相同数量的元素进行一对一相乘，问能得到的乘积之和最大为多少～
分析：把这两个序列都从小到大排序，将前面都是负数的数相乘求和，然后将后面都是正数的数相乘求和～

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int m, n, ans = 0, p = 0, q = 0;
    scanf("%d", &m);
    vector<int> v1(m);
    for(int i = 0; i < m; i++)
        scanf("%d", &v1[i]);
    scanf("%d", &n);
    vector<int> v2(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v2[i]);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    while(p < m && q < n && v1[p] < 0 && v2[q] < 0) {
        ans += v1[p] * v2[q];
        p++; q++;
    }
    p = m - 1, q = n - 1;
    while(p >= 0 && q >= 0 && v1[p] > 0 && v2[q] > 0) {
        ans += v1[p] * v2[q];
        p--; q--;
    }
    printf("%d", ans);
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int m, n, ans = 0, p = 0, q = 0;

scanf("%d", &m);

vector<int> v1(m);

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

scanf("%d", &v1[i]);

scanf("%d", &n);

vector<int> v2(n);

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

scanf("%d", &v2[i]);

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

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

while(p < m && q < n && v1[p] < 0 && v2[q] < 0) {

ans += v1[p] * v2[q];

p++; q++;

}

p = m - 1, q = n - 1;

while(p >= 0 && q >= 0 && v1[p] > 0 && v2[q] > 0) {

ans += v1[p] * v2[q];

p--; q--;

}

printf("%d", ans);

return 0;

}

1029. Median (25)-PAT甲级真题（two points）

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output

For each test case you should output the median of the two given sequences in a line.

Sample Input
4 11 12 13 14
5 9 10 15 16 17
Sample Output
13

题目大意：给出两个已排序序列，求这两个序列合并后的中间数

分析：既然两个数组都是递增的顺序，可以借助归并的思想~与归并排序不同的是，在第一个while里如果找到了中位数，就直接跳出来～
如果其中一个数组已经走到头也没有找到中位数，可以用数学公式直接推导出中位数在另一个数组中的位置～

PS：感谢@琦子块提供的更优解～

#include <iostream>
const int maxn = 200005;
int n, m, a1[maxn], a2[maxn], cnt = 0, i, j, ans;
int main() {
    scanf("%d", &n);
    for(i = 1; i <= n; i++) scanf("%d", &a1[i]);
    scanf("%d", &m);
    for(i = 1; i <= m; i++) scanf("%d", &a2[i]);
    int target = (n + m + 1) / 2;
    i = 1, j = 1;
    while(i <= n && j <= m) {
        ans = a1[i] <= a2[j] ? a1[i++] : a2[j++];
        if(++cnt == target) break;
    }
    if(i <= n && cnt < target)  
        ans = a1[i + target - cnt - 1];
    else if(j <= m && cnt < target) 
        ans = a2[j + target - cnt - 1];
    printf("%d", ans);
    return 0;
}

#include <iostream>

const int maxn = 200005;

int n, m, a1[maxn], a2[maxn], cnt = 0, i, j, ans;

int main() {

scanf("%d", &n);

for(i = 1; i <= n; i++) scanf("%d", &a1[i]);

scanf("%d", &m);

for(i = 1; i <= m; i++) scanf("%d", &a2[i]);

int target = (n + m + 1) / 2;

i = 1, j = 1;

while(i <= n && j <= m) {

ans = a1[i] <= a2[j] ? a1[i++] : a2[j++];

if(++cnt == target) break;

}

if(i <= n && cnt < target)

ans = a1[i + target - cnt - 1];

else if(j <= m && cnt < target)

ans = a2[j + target - cnt - 1];

printf("%d", ans);

return 0;

}