liuchuo – 第197页 – 柳婼の blog

L2-016. 愿天下有情人都是失散多年的兄妹-PAT团体程序设计天梯赛GPLT（广度优先bfs）

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 <= N <= 104），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出“Never Mind”；如果是异性并且关系出了五服，输出“Yes”；如果异性关系未出五服，输出“No”。

输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

分析：我用的方法是广度优先，然后把每个人和他们的祖先们压入一个set里面，判断set前后有没有大小改变，如果没改变说明重复了，所以有相同祖先，所以就输出No，用level数组标记他们当前的层数在push一层的时候令他们的层数为上一层+1，一直到五层判断结束。如果结束了还没有输出过No，那么就输出yes。（其实后来想到可以用数组标记的方法，不用集合来这么复杂的。。）
有三个注意点：1.一开始有三个测试点不过，然后。。发现。。每次在输入的时候把它们父母的性别也要标记一下，因为！测试数据里面可能会判断某个人的父亲（但是不在给出的本人id的列表中），或者母亲和某个人是否能结婚。。。。也就是说测试数据里面如果出现了09999，它是某个人的父母，那么也可能会被判断。。所以。。所以。。要在输入的时候加上父母的性别的标记。。。PAT教我做人。。
【有可爱的小伙伴和我说不太明白第一个注意点的意思，我的意思是，测试用例里面，除了测试样例那样常规的9种询问的是否可以通婚的用例，还有可能会问02222和03333是否可以通婚，02222和04444是否可以通婚。但是我们不知道02222和03333和04444的父母是谁，所以就默认他们之间是没有血缘关系的，接下来考虑的就是他们的性别问题了，因为02222是男的（因为他是父亲嘛）而03333是女的，那就要输出可以通婚；同理，04444是男的，就要输出never mind~】
2.因为我开的是全局数组，用全局数组的时候就千万要记得，用完之后记得把它。。置回0啊啊啊。。。因为下一组测试数据用这个数组的时候可能会不小心用到了上一组测试数据保存的结果。。。就会出错了。。
3.用exist数组标记是否存在这个结点，否则避免不小心把0压入。。。到队列里面（就是求对于一个父母，他们可能不存在在本人id里面，那么把他们的孩子结点放入queue里面就会出现0.。不断标记0的话把0当他们的共同祖先可能会误输出No）

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    int f, m, sex;
};
node v[100010];
int level[100010];
bool exist[100010];
int main() {
    int n, m, id, father, mother, a, b;
    scanf("%d", &n);
    char c;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d %d", &id, &c, &father, &mother);
        v[id].f = father, v[id].m = mother;
        if(c == 'M') v[id].sex = 0;
        else v[id].sex = 1;
        exist[id] = true;
        v[father].sex = 0;
        v[mother].sex = 1;
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        fill(level, level + 100010, 0);
        scanf("%d%d", &a, &b);
        if(v[a].sex == v[b].sex) {
            printf("Never Mind\n");
            continue;
        }
        queue<int> q;
        q.push(a);
        q.push(b);
        level[a] = 1;
        level[b] = 1;
        set<int> s;
        int flag = 0;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            int size = s.size();
            s.insert(top);
            if(size == s.size()) {
                printf("No\n");
                flag = 1;
                break;
            }
            if(exist[top] == false) continue;
            if(level[top] <= 4) {
                int fa = v[top].f;
                int mo = v[top].m;
                if(fa != -1) {
                    q.push(fa);
                    level[fa] = level[top] + 1;
                }
                if(mo != -1) {
                    q.push(mo);
                    level[mo] = level[top] + 1;
                }
            }
        }
        if(flag == 0) printf("Yes\n");
    }
    return 0;
}

#include <cstdio>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;

struct node {

int f, m, sex;

};

node v[100010];

int level[100010];

bool exist[100010];

int main() {

int n, m, id, father, mother, a, b;

scanf("%d", &n);

char c;

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

scanf("%d %c %d %d", &id, &c, &father, &mother);

v[id].f = father, v[id].m = mother;

if(c == 'M') v[id].sex = 0;

else v[id].sex = 1;

exist[id] = true;

v[father].sex = 0;

v[mother].sex = 1;

}

scanf("%d", &m);

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

fill(level, level + 100010, 0);

scanf("%d%d", &a, &b);

if(v[a].sex == v[b].sex) {

printf("Never Mind\n");

continue;

}

queue<int> q;

q.push(a);

q.push(b);

level[a] = 1;

level[b] = 1;

set<int> s;

int flag = 0;

while(!q.empty()) {

int top = q.front();

q.pop();

int size = s.size();

s.insert(top);

if(size == s.size()) {

printf("No\n");

flag = 1;

break;

}

if(exist[top] == false) continue;

if(level[top] <= 4) {

int fa = v[top].f;

int mo = v[top].m;

if(fa != -1) {

q.push(fa);

level[fa] = level[top] + 1;

}

if(mo != -1) {

q.push(mo);

level[mo] = level[top] + 1;

}

if(flag == 0) printf("Yes\n");

}

return 0;

}

【数据结构】堆的建立（边输入数据边建立）（给定数字顺序插入）

堆的建立有两种方式，一个向上调整，一个向下调整，这两个得到的结果可能不同
- 向上调整一般用于边输入数据边建立，是给定数字顺序插入
- 向下调整一般是将所有结点先加入到一棵完全二叉树中，然后对二叉树的所有非叶子结点进行向下调整（从非叶子结点n/2开始，一直到1）

向上调整（大顶堆为例）：

void upAdjust(int i) {
  if(i == 1) return ;
  while(i != 1) {
    if(heap[i] > heap[i / 2]) {
    	swap(heap[i], heap[i / 2]);
    	i = i / 2;
    } else {
      break;
    }
  }
}

for(int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        upAdjust(i);
}

void upAdjust(int i) {

if(i == 1) return ;

while(i != 1) {

if(heap[i] > heap[i / 2]) {

swap(heap[i], heap[i / 2]);

i = i / 2;

} else {

break;

}

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

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

upAdjust(i);

}

向下调整（以大顶堆为例）：先将所有输入得到的数组存储到heap[i]中（构成了一颗完全二叉树，下标从1开始）

void createHeap() {
  for(int i = n / 2; i >= 1; i--)
    downAdjust(i, n);
}

void createHeap() {

for(int i = n / 2; i >= 1; i--)

downAdjust(i, n);

}

const int maxn = 100;
int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）
void downAdjust(int low, int high) {
  int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子
  while(j <= high) {
    if(j + 1 <= high && heap[j + 1] > heap[j])
      j = j + 1; //那就让j存储数值最大的那个结点所对应的下标
    if(heap[j] > heap[i]) {
      swap(heap[i], heap[j]);
      i = j; j = i * 2;
    } else {
      break;
    }
  }
}

const int maxn = 100;

int heap[maxn], n = 10;

//对heap数组在[low, high]范围进行向下调整，其中low为欲调整的结点的数组下标，high一般为堆的最后一个元素的数组下标（其实可以省去high，就是用全局变量n表示）

void downAdjust(int low, int high) {

int i = 1ow, j = i * 2;//i为将要调整的结点，j为它的左孩子

while(j <= high) {

if(j + 1 <= high && heap[j + 1] > heap[j])

j = j + 1; //那就让j存储数值最大的那个结点所对应的下标

if(heap[j] > heap[i]) {

swap(heap[i], heap[j]);

i = j; j = i * 2;

} else {

break;

}

L3-004. 肿瘤诊断-PAT团体程序设计天梯赛GPLT（广度优先搜索）

在诊断肿瘤疾病时，计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域，请你计算肿瘤的体积。

输入格式：

输入第一行给出4个正整数：M、N、L、T，其中M和N是每张切片的尺寸（即每张切片是一个M×N的像素矩阵。最大分辨率是1286×128）；L（<=60）是切片的张数；T是一个整数阈值（若疑似肿瘤的连通体体积小于T，则该小块忽略不计）。

最后给出L张切片。每张用一个由0和1组成的M×N的矩阵表示，其中1表示疑似肿瘤的像素，0表示正常像素。由于切片厚度可以认为是一个常数，于是我们只要数连通体中1的个数就可以得到体积了。麻烦的是，可能存在多个肿瘤，这时我们只统计那些体积不小于T的。两个像素被认为是“连通的”，如果它们有一个共同的切面，如下图所示，所有6个红色的像素都与蓝色的像素连通。

输出格式：

在一行中输出肿瘤的总体积。

输入样例：

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

输出样例：

分析：三维的广度优先搜索～XYZ三个数组判断方向，对每一个点广度优先累计肿瘤块的大小，如果大于等于t就把结果累加。用visit数组标记当前的点有没有被访问过，被访问过的结点是不会再访问的。。judge判断是否超过了边界，或者是否当前结点为0不是肿瘤～

#include <cstdio>
#include <queue>
using namespace std;
struct node {
    int x, y, z;
};
int m, n, l, t;
int X[6] = {1, 0, 0, -1, 0, 0};
int Y[6] = {0, 1, 0, 0, -1, 0};
int Z[6] = {0, 0, 1, 0, 0, -1};
int arr[1300][130][80];
bool visit[1300][130][80];
bool judge(int x, int y, int z) {
    if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;
    if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;
    return true;
}
int bfs(int x, int y, int z) {
    int cnt = 0;
    node temp;
    temp.x = x, temp.y = y, temp.z = z;
    queue<node> q;
    q.push(temp);
    visit[x][y][z] = true;
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < 6; i++) {
            int tx = top.x + X[i];
            int ty = top.y + Y[i];
            int tz = top.z + Z[i];
            if(judge(tx, ty, tz)) {
                visit[tx][ty][tz] = true;
                temp.x = tx, temp.y = ty, temp.z = tz;
                q.push(temp);
            }
        }
    }
    if(cnt >= t)
        return cnt;
    else
        return 0;
    
}
int main() {
    scanf("%d %d %d %d", &m, &n, &l, &t);
    for(int i = 0; i < l; i++)
        for(int j = 0; j < m; j++)
            for(int k = 0; k < n; k++)
                scanf("%d", &arr[j][k][i]);
    int ans = 0;
    for(int i = 0; i < l; i++) {
        for(int j = 0; j < m; j++) {
            for(int k = 0; k < n; k++) {
                if(arr[j][k][i] == 1 && visit[j][k][i] == false)
                    ans += bfs(j, k, i);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

#include <cstdio>

#include <queue>

using namespace std;

struct node {

int x, y, z;

};

int m, n, l, t;

int X[6] = {1, 0, 0, -1, 0, 0};

int Y[6] = {0, 1, 0, 0, -1, 0};

int Z[6] = {0, 0, 1, 0, 0, -1};

int arr[1300][130][80];

bool visit[1300][130][80];

bool judge(int x, int y, int z) {

if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;

if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;

return true;

}

int bfs(int x, int y, int z) {

int cnt = 0;

node temp;

temp.x = x, temp.y = y, temp.z = z;

queue<node> q;

q.push(temp);

visit[x][y][z] = true;

while(!q.empty()) {

node top = q.front();

q.pop();

cnt++;

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

int tx = top.x + X[i];

int ty = top.y + Y[i];

int tz = top.z + Z[i];

if(judge(tx, ty, tz)) {

visit[tx][ty][tz] = true;

temp.x = tx, temp.y = ty, temp.z = tz;

q.push(temp);

}

if(cnt >= t)

return cnt;

else

return 0;

}

int main() {

scanf("%d %d %d %d", &m, &n, &l, &t);

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

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

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

scanf("%d", &arr[j][k][i]);

int ans = 0;

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

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

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

if(arr[j][k][i] == 1 && visit[j][k][i] == false)

ans += bfs(j, k, i);

}

printf("%d", ans);

return 0;

}

1091. Acute Stroke (30)-PAT甲级真题（广度优先搜索）

One important factor to identify acute stroke (急性脑卒中) is the volume of the stroke core. Given the results of image analysis in which the core regions are identified in each MRI slice, your job is to calculate the volume of the stroke core.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive integers: M, N, L and T, where M and N are the sizes of each slice (i.e. pixels of a slice are in an M by N matrix, and the maximum resolution is 1286 by 128); L (<=60) is the number of slices of a brain; and T is the integer threshold (i.e. if the volume of a connected core is less than T, then that core must not be counted).

Then L slices are given. Each slice is represented by an M by N matrix of 0’s and 1’s, where 1 represents a pixel of stroke, and 0 means normal. Since the thickness of a slice is a constant, we only have to count the number of 1’s to obtain the volume. However, there might be several separated core regions in a brain, and only those with their volumes no less than T are counted. Two pixels are “connected” and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.
Figure 1
Output Specification:

For each case, output in a line the total volume of the stroke core.

Sample Input:
3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0
Sample Output:
26

题目大意：给定一个三维数组，0表示正常1表示有肿瘤，肿瘤块的大小大于等于t才算作是肿瘤，让计算所有满足肿瘤块的大小
分析：三维的广度优先搜索～XYZ三个数组判断方向，对每一个点广度优先累计肿瘤块的大小，如果大于等于t就把结果累加。用visit数组标记当前的点有没有被访问过，被访问过的结点是不会再访问的。。judge判断是否超过了边界，或者是否当前结点为0不是肿瘤～

#include <cstdio>
#include <queue>
using namespace std;
struct node {
    int x, y, z;
};
int m, n, l, t;
int X[6] = {1, 0, 0, -1, 0, 0};
int Y[6] = {0, 1, 0, 0, -1, 0};
int Z[6] = {0, 0, 1, 0, 0, -1};
int arr[1300][130][80];
bool visit[1300][130][80];
bool judge(int x, int y, int z) {
    if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;
    if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;
    return true;
}
int bfs(int x, int y, int z) {
    int cnt = 0;
    node temp;
    temp.x = x, temp.y = y, temp.z = z;
    queue<node> q;
    q.push(temp);
    visit[x][y][z] = true;
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < 6; i++) {
            int tx = top.x + X[i];
            int ty = top.y + Y[i];
            int tz = top.z + Z[i];
            if(judge(tx, ty, tz)) {
                visit[tx][ty][tz] = true;
                temp.x = tx, temp.y = ty, temp.z = tz;
                q.push(temp);
            }
        }
    }
    if(cnt >= t)
        return cnt;
    else
        return 0;
    
}
int main() {
    scanf("%d %d %d %d", &m, &n, &l, &t);
    for(int i = 0; i < l; i++)
        for(int j = 0; j < m; j++)
            for(int k = 0; k < n; k++)
                scanf("%d", &arr[j][k][i]);
    int ans = 0;
    for(int i = 0; i < l; i++) {
        for(int j = 0; j < m; j++) {
            for(int k = 0; k < n; k++) {
                if(arr[j][k][i] == 1 && visit[j][k][i] == false)
                    ans += bfs(j, k, i);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

#include <cstdio>

#include <queue>

using namespace std;

struct node {

int x, y, z;

};

int m, n, l, t;

int X[6] = {1, 0, 0, -1, 0, 0};

int Y[6] = {0, 1, 0, 0, -1, 0};

int Z[6] = {0, 0, 1, 0, 0, -1};

int arr[1300][130][80];

bool visit[1300][130][80];

bool judge(int x, int y, int z) {

if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;

if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;

return true;

}

int bfs(int x, int y, int z) {

int cnt = 0;

node temp;

temp.x = x, temp.y = y, temp.z = z;

queue<node> q;

q.push(temp);

visit[x][y][z] = true;

while(!q.empty()) {

node top = q.front();

q.pop();

cnt++;

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

int tx = top.x + X[i];

int ty = top.y + Y[i];

int tz = top.z + Z[i];

if(judge(tx, ty, tz)) {

visit[tx][ty][tz] = true;

temp.x = tx, temp.y = ty, temp.z = tz;

q.push(temp);

}

if(cnt >= t)

return cnt;

else

return 0;

}

int main() {

scanf("%d %d %d %d", &m, &n, &l, &t);

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

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

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

scanf("%d", &arr[j][k][i]);

int ans = 0;

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

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

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

if(arr[j][k][i] == 1 && visit[j][k][i] == false)

ans += bfs(j, k, i);

}

printf("%d", ans);

return 0;

}

1049. Counting Ones (30)-PAT甲级真题（数学问题）

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (<=230).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:
12
Sample Output:
5
题目大意：给出一个数字n，求1~n的所有数字里面出现1的个数
分析：这是一道数学问题。从第一位（个位）到最高位，设now为当前位的数字，left为now左边的所有数字构成的数字，right是now右边的所有数字构成的数字。只需要一次次累加对于当前位now来说可能出现1的个数，然后把它们累加即可。a表示当前的个位为1，十位为10，百位为100类推。
对于now，有三种情况：
1.now == 0 : 那么 ans += left * a; //因为now==0说明now位只有在left从0~left-1的时候会产生1，所以会产生left次，但是又因为右边会重复从0~999…出现a次
2.now == 1 : ans += left * a + right + 1;//now = 1的时候就要比上一步多加一个当now为1的时候右边出现0~right个数导致的now为1的次数
3.now >= 2 : ans += (left + 1) * a;//now大于等于2就左边0~left的时候会在now位置产生1，所以会产生left次，但是又因为右边会重复从0~999…出现a次

#include <iostream>
using namespace std;
int main() {
    int n, left = 0, right = 0, a = 1, now = 1, ans = 0;
    scanf("%d", &n);
    while(n / a) {
        left = n / (a * 10), now = n / a % 10, right = n % a;
        if(now == 0) ans += left * a;
        else if(now == 1) ans += left * a + right + 1;
        else ans += (left + 1) * a;
        a = a * 10;
    }
    printf("%d", ans);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, left = 0, right = 0, a = 1, now = 1, ans = 0;

scanf("%d", &n);

while(n / a) {

left = n / (a * 10), now = n / a % 10, right = n % a;

if(now == 0) ans += left * a;

else if(now == 1) ans += left * a + right + 1;

else ans += (left + 1) * a;

a = a * 10;

}

printf("%d", ans);

return 0;

}

1038. Recover the Smallest Number (30)-PAT甲级真题（贪心算法）

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (<=10000) followed by N number segments. Each segment contains a non-negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Do not output leading zeros.

Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287
题目大意：给一些字符串，求它们拼接起来构成最小数字的方式
分析：贪心算法。让我们一起来见证cmp函数的强大之处！！～～不是按照字典序排列就可以的，必须保证两个字符串构成的数字是最小的才行，所以cmp函数写成return a + b < b + a;的形式，保证它排列按照能够组成的最小数字的形式排列。
因为字符串可能前面有0，这些要移除掉（用s.erase(s.begin())就可以了～嗯～string如此神奇～～）。输出拼接后的字符串即可。
注意：如果移出了0之后发现s.length() == 0了，说明这个数是0，那么要特别地输出这个0，否则会什么都不输出～

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp0(string a, string b) {
    return a + b < b + a;
}
string str[10010];
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        cin >> str[i];
    sort(str, str + n, cmp0);
    string s;
    for(int i = 0; i < n; i++)
        s += str[i];
    while(s.length() != 0 && s[0] == '0')
        s.erase(s.begin());
    if(s.length() == 0) cout << 0;
    cout << s;
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

bool cmp0(string a, string b) {

return a + b < b + a;

}

string str[10010];

int main() {

int n;

scanf("%d", &n);

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

cin >> str[i];

sort(str, str + n, cmp0);

string s;

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

s += str[i];

while(s.length() != 0 && s[0] == '0')

s.erase(s.begin());

if(s.length() == 0) cout << 0;

cout << s;

return 0;

}