PAT – 第15页

1044. Shopping in Mars (25)-PAT甲级真题（二分查找）

Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:

1. Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
3. Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.

If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=105), the total number of diamonds on the chain, and M (<=108), the amount that the customer has to pay. Then the next line contains N positive numbers D1 … DN (Di<=103 for all i=1, …, N) which are the values of the diamonds. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print “i-j” in a line for each pair of i <= j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.

If there is no solution, output “i-j” for pairs of i <= j such that Di + … + Dj > M with (Di + … + Dj – M) minimized. Again all the solutions must be printed in increasing order of i.

It is guaranteed that the total value of diamonds is sufficient to pay the given amount.

Sample Input 1:
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
Sample Output 1:
1-5
4-6
7-8
11-11
Sample Input 2:
5 13
2 4 5 7 9
Sample Output 2:
2-4
4-5
题目大意，求一串的数字中连续的一段，使得这个连续的段内数字的和恰好等于所期望的值m。如果不能找到恰好等于，就找让自己付出最少的价格（总和必须大于等于所给值）的那段区间。求所有可能的结果。
分析：一开始用的简单模拟，有两个超时了。后来想到因为sum数组是递增的，所以改用二分法查找～Func函数的作用是二分查找，修改tempsum和j的值～一开始接收输入的时候可以直接保存它的sum函数，即sum[i]表示1～i的所有数字的总和～

#include <iostream>
#include <vector>
using namespace std;
vector<int> sum, resultArr;
int n, m;
void Func(int i, int &j, int &tempsum) {
    int left = i, right = n;
    while(left < right) {
        int mid = (left + right) / 2;
        if(sum[mid] - sum[i-1] >= m)
            right = mid;
        else
            left = mid + 1;
    }
    j = right;
    tempsum = sum[j] - sum[i-1];
}
int main() {
    scanf("%d%d", &n, &m);
    sum.resize(n+1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &sum[i]);
        sum[i] += sum[i-1];
    }
    int minans = sum[n];
    for(int i = 1; i <= n; i++) {
        int j, tempsum;
        Func(i, j, tempsum);
        if(tempsum > minans) continue;
        if(tempsum >= m) {
            if(tempsum < minans) {
                resultArr.clear();
                minans = tempsum;
            }
            resultArr.push_back(i);
            resultArr.push_back(j);
        }
    }
    for(int i = 0; i < resultArr.size(); i += 2)
        printf("%d-%d\n", resultArr[i], resultArr[i+1]);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> sum, resultArr;

int n, m;

void Func(int i, int &j, int &tempsum) {

int left = i, right = n;

while(left < right) {

int mid = (left + right) / 2;

if(sum[mid] - sum[i-1] >= m)

right = mid;

else

left = mid + 1;

}

j = right;

tempsum = sum[j] - sum[i-1];

}

int main() {

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

sum.resize(n+1);

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

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

sum[i] += sum[i-1];

}

int minans = sum[n];

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

int j, tempsum;

Func(i, j, tempsum);

if(tempsum > minans) continue;

if(tempsum >= m) {

if(tempsum < minans) {

resultArr.clear();

minans = tempsum;

}

resultArr.push_back(i);

resultArr.push_back(j);

}

for(int i = 0; i < resultArr.size(); i += 2)

printf("%d-%d\n", resultArr[i], resultArr[i+1]);

return 0;

}

1056. Mice and Rice (25)-PAT甲级真题（queue的用法）

Mice and Rice is the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order to become a FatMouse.

First the playing order is randomly decided for NP programmers. Then every NG programmers are grouped in a match. The fattest mouse in a group wins and enters the next turn. All the losers in this turn are ranked the same. Every NG winners are then grouped in the next match until a final winner is determined.

For the sake of simplicity, assume that the weight of each mouse is fixed once the programmer submits his/her code. Given the weights of all the mice and the initial playing order, you are supposed to output the ranks for the programmers.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers: NP and NG (<= 1000), the number of programmers and the maximum number of mice in a group, respectively. If there are less than NG mice at the end of the player’s list, then all the mice left will be put into the last group. The second line contains NP distinct non-negative numbers Wi (i=0,…NP-1) where each Wi is the weight of the i-th mouse respectively. The third line gives the initial playing order which is a permutation of 0,…NP-1 (assume that the programmers are numbered from 0 to NP-1). All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the final ranks in a line. The i-th number is the rank of the i-th programmer, and all the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:
11 3
25 18 0 46 37 3 19 22 57 56 10
6 0 8 7 10 5 9 1 4 2 3
Sample Output:
5 5 5 2 5 5 5 3 1 3 5

题目大意：np为老鼠的数量，ng为每组最多g个老鼠。先给出np个老鼠的重量，再给出老鼠的初始顺序（第i名的老鼠是第j号，j从0开始）。每ng个老鼠分为一组，对于每组老鼠，选出最重的那个，晋级下一轮比赛，然后依次再以np个老鼠一组分类，然后选出重量最大的。。。直到只剩下一只老鼠，排名为1.输出为老鼠的排名，这个排名是按照原输入老鼠的顺序输出的～
分析：设立结构体node表示老鼠，里面包括weight重量，index是按照排名后的顺序的老鼠的下标，index0是排名前老鼠的下标。rank是最终要输出的老鼠的排名。
先将所有的老鼠按照排名后的顺序依次放入队列中，对于队列中的每一个老鼠，按照分组后选择最大重量的比赛规则，将每次分组获得第一的老鼠放入队列尾部。此处有一点，如果当前剩下的老鼠可以分为group组，那么这一组里面没有晋级的老鼠排名就是group+1.此处解释一下：
因为对于共有group组的老鼠，每组晋级一个，也就是说最终这一轮能晋级的是group个老鼠，那么没有晋级的所有人就是group+1名，就像有4个人晋级下一轮，那么所有没晋级的这一轮就都是并列第5名。
group的计算方法是：如果当前轮次的人数正好可以被每组ng人的ng整除，那么就有人数/ng个组。如果不能被整除，就有剩下来的一些老鼠分为一组，就是人数/ng + 1组。（这是求得group的方法）
cnt用来控制当前的组内第几个人，如果cnt能够被ng整除了说明已经是下一组了，就cnt = 0；否则cnt不断++，同时将最重的老鼠体重赋值给maxn，最重的老鼠的node赋值给maxnode。
最后将结果结构体w排序，按照先前保存的index0的顺序排序，因为题目要求是必须按照题目所给的输入顺序输出的，排序后即可按序输出～

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int weight, index, rank, index0;
};
bool cmp1(node a, node b) {
    return a.index0 < b.index0;
}
int main() {
    int n, g, num;
    scanf("%d%d", &n, &g);
    vector<int> v(n);
    vector<node> w(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        w[i].weight = v[num];
        w[i].index = i;
        w[i].index0 = num;
    }
    queue<node> q;
    for(int i = 0; i < n; i++)
        q.push(w[i]);
    while(!q.empty()) {
        int size = q.size();
        if(size == 1) {
            node temp = q.front();
            w[temp.index].rank = 1;
            break;
        }
        int group = size / g;
        if(size % g != 0)
            group += 1;
        node maxnode;
        int maxn = -1, cnt = 0;
        for(int i = 0; i < size; i++) {
            node temp = q.front();
            w[temp.index].rank = group + 1;
            q.pop();
            cnt++;
            if(temp.weight > maxn) {
                maxn = temp.weight;
                maxnode = temp;
            }
            if(cnt == g || i == size - 1) {
                cnt = 0;
                maxn = -1;
                q.push(maxnode);
            }
        }
    }
    sort(w.begin(), w.end(), cmp1);
    for(int i = 0; i < n; i++) {
        if(i != 0) printf(" ");
        printf("%d", w[i].rank);
    }
    return 0;
}

#include <iostream>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

struct node {

int weight, index, rank, index0;

};

bool cmp1(node a, node b) {

return a.index0 < b.index0;

}

int main() {

int n, g, num;

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

vector<int> v(n);

vector<node> w(n);

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

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

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

scanf("%d", &num);

w[i].weight = v[num];

w[i].index = i;

w[i].index0 = num;

}

queue<node> q;

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

q.push(w[i]);

while(!q.empty()) {

int size = q.size();

if(size == 1) {

node temp = q.front();

w[temp.index].rank = 1;

break;

}

int group = size / g;

if(size % g != 0)

group += 1;

node maxnode;

int maxn = -1, cnt = 0;

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

node temp = q.front();

w[temp.index].rank = group + 1;

q.pop();

cnt++;

if(temp.weight > maxn) {

maxn = temp.weight;

maxnode = temp;

}

if(cnt == g || i == size - 1) {

cnt = 0;

maxn = -1;

q.push(maxnode);

}

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

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

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

printf("%d", w[i].rank);

}

return 0;

}

1120. Friend Numbers (20)-PAT甲级真题

Two integers are called “friend numbers” if they share the same sum of their digits, and the sum is their “friend ID”. For example, 123 and 51 are friend numbers since 1+2+3 = 5+1 = 6, and 6 is their friend ID. Given some numbers, you are supposed to count the number of different friend ID’s among them. Note: a number is considered a friend of itself.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N. Then N positive integers are given in the next line, separated by spaces. All the numbers are less than 10^4.

Output Specification:

For each case, print in the first line the number of different frind ID’s among the given integers. Then in the second line, output the friend ID’s in increasing order. The numbers must be separated by exactly one space and there must be no extra space at the end of the line.

Sample Input:
8
123 899 51 998 27 33 36 12
Sample Output:
4
3 6 9 26

分析：在接收输入数据的时候就把该数字的每一位相加，并把结果插入一个set集合中。因为set是有序的、不重复的，所以set的size值就是输出的个数，set中的每一个数字即所有答案的数字序列

#include <iostream>
#include <set>
using namespace std;
int getFriendNum(int num) {
    int sum = 0;
    while(num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
int main() {
    set<int> s;
    int n, num;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        s.insert(getFriendNum(num));
    }
    printf("%d\n", s.size());
    for(auto it = s.begin(); it != s.end(); it++) {
        if(it != s.begin()) printf(" ");
        printf("%d", *it);
    }
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int getFriendNum(int num) {

int sum = 0;

while(num != 0) {

sum += num % 10;

num /= 10;

}

return sum;

}

int main() {

set<int> s;

int n, num;

scanf("%d", &n);

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

scanf("%d", &num);

s.insert(getFriendNum(num));

}

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

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

if(it != s.begin()) printf(" ");

printf("%d", *it);

}

return 0;

}

1122. Hamiltonian Cycle (25)-PAT甲级真题

The “Hamilton cycle problem” is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a “Hamiltonian cycle”.

In this problem, you are supposed to tell if a given cycle is a Hamiltonian cycle.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2< N <= 200), the number of vertices, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format “Vertex1 Vertex2”, where the vertices are numbered from 1 to N. The next line gives a positive integer K which is the number of queries, followed by K lines of queries, each in the format:

n V₁ V₂ … V_n

where n is the number of vertices in the list, and V_i‘s are the vertices on a path.

Output Specification:

For each query, print in a line “YES” if the path does form a Hamiltonian cycle, or “NO” if not.

Sample Input:

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

Sample Output:

YES
NO
NO
NO
YES
NO

题目大意：给出一个图，判断给定的路径是不是哈密尔顿路径

分析：1.设置falg1 判断节点是否多走、少走、或走成环
2.设置flag2 判断这条路能不能走通
3.当falg1、flag2都为1时是哈密尔顿路径，否则不是

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main() {
    int n, m, cnt, k, a[210][210] = {0};
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int t1, t2;
        scanf("%d%d", &t1, &t2);
        a[t1][t2] = a[t2][t1] = 1;
    }
    cin >> cnt;
    while(cnt--) {
        cin >> k;
        vector<int> v(k);
        set<int> s;
        int flag1 = 1, flag2 = 1;
        for(int i = 0; i < k; i++) {
            scanf("%d", &v[i]);
            s.insert(v[i]);
        }
        if(s.size() != n || k - 1 != n || v[0] != v[k-1]) flag1 = 0;
        for(int i = 0; i < k - 1; i++)
            if(a[v[i]][v[i+1]] == 0) flag2 = 0;
        printf("%s",flag1 && flag2 ? "YES\n" : "NO\n");
    }
    return 0;
}

#include <iostream>

#include <set>

#include <vector>

using namespace std;

int main() {

int n, m, cnt, k, a[210][210] = {0};

cin >> n >> m;

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

int t1, t2;

scanf("%d%d", &t1, &t2);

a[t1][t2] = a[t2][t1] = 1;

}

cin >> cnt;

while(cnt--) {

cin >> k;

vector<int> v(k);

set<int> s;

int flag1 = 1, flag2 = 1;

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

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

s.insert(v[i]);

}

if(s.size() != n || k - 1 != n || v[0] != v[k-1]) flag1 = 0;

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

if(a[v[i]][v[i+1]] == 0) flag2 = 0;

printf("%s",flag1 && flag2 ? "YES\n" : "NO\n");

}

return 0;

}

1123. Is It a Complete AVL Tree (30)-PAT甲级真题

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print “YES” if the tree is complete, or “NO” if not.

Sample Input 1:

5
88 70 61 63 65

Sample Output 1:

70 63 88 61 65
YES

Sample Input 2:

8
88 70 61 96 120 90 65 68

Sample Output 2:

88 65 96 61 70 90 120 68
NO

分析：这道题实际上考察AVL树和层序遍历两个知识点～～
判断是不是完全二叉树，就看在出现了一个孩子为空的结点之后是否还会出现孩子结点不为空的结点，如果出现了就不是完全二叉树。
AVL树一共有四种情况，这里我把发现树不平衡的那个结点叫做A结点，A发现树不平衡的情况有四种：
新来的结点插入到A的左子树的左子树
新来的结点插入到A的左子树的右子树
新来的结点插入到A的右子树的左子树
新来的结点插入到A的右子树的右子树
发现不平衡时就需要处理，第1种情况只要简单的右旋，第4种情况只需左旋一下，第2种情况需要先对A的左子树左旋一下，然后对A右旋，同理第3种情况需要对A的右子树右旋一下，然后对A左旋就可以啦～～～

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int val;
    struct node *left, *right;
};
node* leftRotate(node *tree) {
    node *temp = tree->right;
    tree->right = temp->left;
    temp->left = tree;
    return temp;
}
node* rightRotate(node *tree) {
    node *temp = tree->left;
    tree->left = temp->right;
    temp->right = tree;
    return temp;
}
node* leftRightRotate(node *tree) {
    tree->left = leftRotate(tree->left);
    return rightRotate(tree);
}
node* rightLeftRotate(node *tree) {
    tree->right = rightRotate(tree->right);
    return leftRotate(tree);
}
int getHeight(node *tree) {
    if (tree == NULL) return 0;
    int l = getHeight(tree->left);
    int r = getHeight(tree->right);
    return max(l, r) + 1;
}
node* insert(node *tree, int val) {
    if (tree == NULL) {
        tree = new node();
        tree->val = val;
    }else if (tree->val > val) {
        tree->left = insert(tree->left, val);
        int l = getHeight(tree->left), r = getHeight(tree->right);
        if (l - r >= 2) {
            if (val < tree->left->val)
                tree = rightRotate(tree);
            else
                tree = leftRightRotate(tree);
        }
    } else {
        tree->right = insert(tree->right, val);
        int l = getHeight(tree->left), r = getHeight(tree->right);
        if (r - l >= 2) {
            if (val > tree->right->val)
                tree = leftRotate(tree);
            else
                tree = rightLeftRotate(tree);
        }
    }
    return tree;
}
int isComplete = 1, after = 0;
vector<int> levelOrder(node *tree) {
    vector<int> v;
    queue<node *> queue;
    queue.push(tree);
    while (!queue.empty()) {
        node *temp = queue.front();
        queue.pop();
        v.push_back(temp->val);
        if (temp->left != NULL) {
            if (after) isComplete = 0;
            queue.push(temp->left);
        } else {
            after = 1;
        }
        if (temp->right != NULL) {
            if (after) isComplete = 0;
            queue.push(temp->right);
        } else {
            after = 1;
        }
    }
    return v;
}
int main() {
    int n, temp;
    scanf("%d", &n);
    node *tree = NULL;
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        tree = insert(tree, temp);
    }
    vector<int> v = levelOrder(tree);
    for (int i = 0; i < v.size(); i++) {
        if (i != 0) printf(" ");
        printf("%d", v[i]);
    }
    printf("\n%s", isComplete ? "YES" : "NO");
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

struct node {

int val;

struct node *left, *right;

};

node* leftRotate(node *tree) {

node *temp = tree->right;

tree->right = temp->left;

temp->left = tree;

return temp;

}

node* rightRotate(node *tree) {

node *temp = tree->left;

tree->left = temp->right;

temp->right = tree;

return temp;

}

node* leftRightRotate(node *tree) {

tree->left = leftRotate(tree->left);

return rightRotate(tree);

}

node* rightLeftRotate(node *tree) {

tree->right = rightRotate(tree->right);

return leftRotate(tree);

}

int getHeight(node *tree) {

if (tree == NULL) return 0;

int l = getHeight(tree->left);

int r = getHeight(tree->right);

return max(l, r) + 1;

}

node* insert(node *tree, int val) {

if (tree == NULL) {

tree = new node();

tree->val = val;

}else if (tree->val > val) {

tree->left = insert(tree->left, val);

int l = getHeight(tree->left), r = getHeight(tree->right);

if (l - r >= 2) {

if (val < tree->left->val)

tree = rightRotate(tree);

else

tree = leftRightRotate(tree);

}

} else {

tree->right = insert(tree->right, val);

int l = getHeight(tree->left), r = getHeight(tree->right);

if (r - l >= 2) {

if (val > tree->right->val)

tree = leftRotate(tree);

else

tree = rightLeftRotate(tree);

}

return tree;

}

int isComplete = 1, after = 0;

vector<int> levelOrder(node *tree) {

vector<int> v;

queue<node *> queue;

queue.push(tree);

while (!queue.empty()) {

node *temp = queue.front();

queue.pop();

v.push_back(temp->val);

if (temp->left != NULL) {

if (after) isComplete = 0;

queue.push(temp->left);

} else {

after = 1;

}

if (temp->right != NULL) {

if (after) isComplete = 0;

queue.push(temp->right);

} else {

after = 1;

}

return v;

}

int main() {

int n, temp;

scanf("%d", &n);

node *tree = NULL;

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

scanf("%d", &temp);

tree = insert(tree, temp);

}

vector<int> v = levelOrder(tree);

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

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

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

}

printf("\n%s", isComplete ? "YES" : "NO");

return 0;

}

1063. 计算谱半径(20)-PAT乙级真题

在数学中，矩阵的“谱半径”是指其特征值的模集合的上确界。换言之，对于给定的n个复数空间的特征值{a1+b1i, …, an+bni}，它们的模为实部与虚部的平方和的开方，而“谱半径”就是最大模。

现在给定一些复数空间的特征值，请你计算并输出这些特征值的谱半径。

输入格式：

输入第一行给出正整数N（<= 10000）是输入的特征值的个数。随后N行，每行给出1个特征值的实部和虚部，其间以空格分隔。注意：题目保证实部和虚部均为绝对值不超过1000的整数。

输出格式：

在一行中输出谱半径，四舍五入保留小数点后2位。

输入样例：
5
0 1
2 0
-1 0
3 3
0 -3
输出样例：
4.24

分析：用max保存谱半径，对于n个特征值的实部a和虚部b，模ans = (a的平方+b的平方)的开方，所以ans = sqrt(a * a + b * b)；将ans的最大值保存在max中，最后用%.2f输出max的值～

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    float max = 0;
    for(int i = 0; i < n; i++) {
        float a, b, ans;
        scanf("%f%f", &a, &b);
        ans = sqrt(a * a + b * b);
        max = ans > max ? ans : max;
    }
    printf("%.2f", max);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

scanf("%d", &n);

float max = 0;

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

float a, b, ans;

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

ans = sqrt(a * a + b * b);

max = ans > max ? ans : max;

}

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

return 0;

}