分类目录归档:编程

洛谷 P3369 【模板】普通平衡树

手写Splay成功。庆祝能写出来的第一个BBST!
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<iostream>
#include<cassert>
using namespace std;
class Splay {
private:
    struct Node {
        int v; //值
        Node* f, * l, * r; //父,左孩子,右孩子
        int cnts; //本子树下包含自身的所有**元素**数目
        int rep; //该值重复了多少次
        Node(int v, Node* f) :v(v), f(f), l(NULL), r(NULL), cnts(1), rep(1) {}
    };
    Node* _root;
#define root _root->r
    void update(Node* p) { //更新cnts值
        p->cnts = p->rep;
        if (p->l)p->cnts += p->l->cnts;
        if (p->r)p->cnts += p->r->cnts;
    }
    bool identify(Node* s, Node* f) { //确定本节点是左孩子还是右孩子,左孩子false,右孩子true
        return !f || s == f->r;
    }
    void connect(Node* s, Node* f, bool r) { //儿子地址,父亲地址,连接到左儿子还是右儿子
        if (f)(r ? f->r : f->l) = s; //父亲更新新儿子
        if (s)s->f = f; //儿子更新新父亲
    }
    void rotate(Node* s) { //儿子节点的旋转
        Node* f = s->f, * gf = s->f->f;
        if (!identify(s, f)) { //左孩子
            connect(s->r, f, false);
            connect(f, s, true);
            connect(s, gf, identify(f, gf));
        }
        else { //右孩子
            connect(s->l, f, true);
            connect(f, s, false);
            connect(s, gf, identify(f, gf));
        }
        update(f);
        update(s);
    }
    void splay(Node* s, Node* e) { //伸展操作,将节点s旋转到节点e所在的位置
        e = e->f;
        while (s->f != e) {
            Node* f = s->f;
            if (f->f == e)rotate(s); //s是e的直系儿子,只需做单旋
            else if (identify(f, f->f) == identify(s, f)) { //Zig-Zig或Zag-Zag,需要先旋父亲节点,再旋儿子节点
                rotate(f);
                rotate(s);
            }
            else { //Zig-Zag或Zag-Zig
                rotate(s);
                rotate(s);
            }
        }
    }

public:
    Splay() {
        _root = new Node(0, NULL);
    }
    ~Splay() {
        delete _root;
    }
    Node* find(int v) {
        Node* cur = root;
        if (!cur)return NULL;
        while (1) {
            if (cur->v == v) break;
            Node* next = v < cur->v ? cur->l : cur->r;
            if (!next)break;
            cur = next;
        }
        splay(cur, root);
        root = cur;
        if (cur->v == v)return cur;
        else return NULL;
    }
    void del(int v) {
        Node* cur = find(v);
        if (!cur)return;
        if (cur->rep > 1) { //节点个数出现多于1次
            cur->rep--;
            cur->cnts--;
            return;
        }
        if (!cur->l && !cur->r) { //删除最后一个仅剩的节点
            root = NULL;
        }
        else if (!cur->l) { //无左子树时直接把右子树拼到根
            root = cur->r;
            root->f = _root;
        }
        else { //有左子树时,把左子树的最大值旋到根的左子,将根的右子放到根的左子的右子,删根后补左子树
            Node* l = cur->l;
            while (l->r)l = l->r;
            splay(l, cur->l);
            Node* r = cur->r;
            connect(r, l, true);
            root = l;
            root->f = _root;
            update(l);
        }
        delete cur;
    }
    void insert(int v) {
        Node* cur = find(v);
        if (!root) { //特判空树
            root = new Node(v, _root);
            return;
        }
        if (cur && cur->v == v) { //元素存在,直接把次数+1
            cur->rep++;
            cur->cnts++;
            return;
        }
        Node* newNode = new Node(v, _root);
        if (root->v < v) { //将v接入右侧
            connect(root, newNode, false);
            connect(root->r, newNode, true);
            root->r = NULL;
        }
        else { //将v接入左侧
            connect(root, newNode, true);
            connect(root->l, newNode, false);
            root->l = NULL;
        }
        update(root);
        update(newNode);
        root = newNode;
        newNode->f = _root;
    }
    int rank(int v) {
        Node* cur = find(v);
        if (!cur)return -1;
        int lCnts = cur->l ? cur->l->cnts : 0;
        return lCnts + 1;
    }
    int atrank(int rank) {
        Node* cur = root;
        while (cur) {
            int lCnts = cur->l ? cur->l->cnts : 0;
            if (lCnts < rank && rank <= lCnts + cur->rep) {
                splay(cur, root);
                return cur->v;
            }
            if (rank <= lCnts)cur = cur->l;
            else {
                rank -= lCnts + cur->rep;
                cur = cur->r;
            }
        }
        return -1;
    }
    int upper(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v <= v)return atrank(lCnts + root->rep + 1);
        return root->v;
    }
    int lower(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v >= v)return atrank(lCnts);
        return root->v;
    }
#undef root
};
int main() {
    Splay splay;
    int n;
    cin >> n;
    while (n--) {
        int op1, op2;
        cin >> op1 >> op2;
        if (op1 == 1) {
            splay.insert(op2);
        }
        else if (op1 == 2) {
            splay.del(op2);
        }
        else if (op1 == 3) {
            cout << splay.rank(op2) << endl;
        }
        else if (op1 == 4) {
            cout << splay.atrank(op2) << endl;
        }
        else if (op1 == 5) {
            cout << splay.lower(op2) << endl;
        }
        else if (op1 == 6) {
            cout << splay.upper(op2) << endl;
        }
    }
}

参考资料:
https://www.luogu.com.cn/blog/user19027/solution-p3369
非常感谢rentenglong同学

洛谷 P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

开心啦! THUOJ不过不知道是什么鬼畜精度问题,不管了^v^
板子好用^v^

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<iostream>
#include<iomanip>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
struct point {
    double x, y;
    long long id;
    point() :x(0), y(0) {}
    bool operator ==(const point& p) const {
        return x == p.x && y == p.y;
    }
}PP; //PP: Polar Point
vector<point> points;
double area2(point p, point q, point s) {
    /*
    |p.x p.y 1|
    |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)
    |s.x s.y 1|
    */

    return p.x * q.y - s.x * q.y
        + q.x * s.y - q.x * p.y
        + s.x * p.y - p.x * s.y;
}
bool toLeftTest(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) > 0;
}
bool toLeftTest2(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) >= 0;
}
bool cmp(const point& p1, const point& p2) { // Sort according to polar angle
    return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2);
}
point LTL(vector<point>& points) { //Lowest then leftmost
    point ltl = points[0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)
            ltl = points[i];
    }
    return ltl;
}
vector<point> grahamScan() {
    PP = LTL(points);
    sort(points.begin(), points.end(), cmp);
    vector<point> S, T;
    S.push_back(points[0]); S.push_back(points[1]);
    for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);
    while (!T.empty()) {
        if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {
            S.push_back(T[T.size() - 1]);
            T.pop_back();
        }
        else S.pop_back();
    }
    return S;
}
double dist(point x, point y) {
    return sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y));
}
int main() {
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        point tmp;
        cin >> tmp.x >> tmp.y;
        tmp.id = i;
        points.push_back(tmp);
    }
    vector<point> result;
    if (points.size() > 2)result = grahamScan();
    else result = points;
    double res = 0;
    for (int i = 0; i < result.size(); i++) {
        res += dist(result[i % result.size()], result[(i + 1) % result.size()]);
    }
    cout.setf(ios::fixed);
    cout << setprecision(2) << res;
}

CG2017 PA1-1 Convex Hull (凸包)

开始接触计算几何啦!!!

CG2017 PA1-1 Convex Hull (凸包)


Description (描述)

After learning Chapter 1, you must have mastered the convex hull very well. Yes, convex hull is at the kernel of computational geometry and serves as a fundamental geometric structure. That’s why you are asked to implement such an algorithm as your first programming assignments.

Specifically, given a set of points in the plane, please construct the convex hull and output an encoded description of all the extreme points.

经过了第一章的学习,想必你对于凸包的认识已经非常深刻。是的,凸包是计算几何的核心问题,也是一种基础性的几何结构。因此你的第一项编程任务,就是来实现这样的一个算法。

具体地,对于平面上的任意一组点,请构造出对应的凸包,并在经过编码转换之后输出所有极点的信息。

Input (输入)

The first line is an integer n > 0, i.e., the total number of input points.

The k-th of the following n lines gives the k-th point:

pk = (xk, yk), k = 1, 2, …, n

Both xk and yk here are integers and they are delimited by a space.

第一行是一个正整数首行为一个正整数n > 0,即输入点的总数。

随后n行中的第k行给出第k个点:

pk = (xk, yk), k = 1, 2, …, n

这里,xk与yk均为整数,且二者之间以空格分隔。

Output (输出)

Let { s1, s2, …, sh } be the indices of all the extreme points, h ≤ n. Output the following integer as your solution:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

若 { s1, s2, …, sh } 为所有极点的编号, h ≤ n,则作为你的解答,请输出以下整数:

( s1 * s2 * s3 * … * sh * h ) mod (n + 1)

Sample Input (输入样例)

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

Sample Output (输出样例)

1
7   // ( 9 x 2 x 6 x 7 x 1 x 5 ) % (10 + 1)

Limitation (限制)

  • 3 ≤ n ≤ 10^5
  • Each coordinate of the points is an integer from (-10^5, 10^5). There are no duplicated points. Each point is selected uniformly randomly in (-10^5, 10^5) x (-10^5, 10^5).
  • All points on extreme edges are regarded as extreme points and hence should be included in your solution.
  • Time Limit: 2 sec
  • Space Limit: 512 MB
  • 3 ≤ n ≤ 10^5
  • 所有点的坐标均为范围(-10^5, 10^5)内的整数,且没有重合点。每个点在(-10^5, 10^5) x (-10^5, 10^5)范围内均匀随机选取
  • 极边上的所有点均被视作极点,故在输出时亦不得遗漏
  • 时间限制:2 sec
  • 空间限制:512 MB

Hint (提示)

Use the CH algorithms presented in the lectures.

课程中讲解过的凸包算法

 

分数:92.5
使用Graham Scan算法。凸包板子题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
struct point {
    long long x, y, id;
    point() :x(0), y(0) {}
    point(long long x, long long y) :x(x), y(y) {}
    bool operator ==(const point& p) const {
        return x == p.x && y == p.y;
    }
}PP; //PP: Polar Point
vector<point> points;
long long area2(point p, point q, point s) {
    /*
    |p.x p.y 1|
    |q.x q.y 1| == 2*DirectedTriangleArea(p,q,s)
    |s.x s.y 1|
    */

    return p.x * q.y - s.x * q.y
        + q.x * s.y - q.x * p.y
        + s.x * p.y - p.x * s.y;
}
bool toLeftTest(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) > 0;
}
bool toLeftTest2(point p, point q, point s) {
    //When return value large than 0, S is on the left side of ray PQ
    return area2(p, q, s) >= 0;
}
bool cmp(const point& p1, const point& p2) { // Sort according to polar angle
    return PP == p1 || !(PP == p2) && toLeftTest(PP, p1, p2);
}
point LTL(vector<point>& points) { //Lowest then leftmost
    point ltl = points[0];
    for (int i = 1; i < points.size(); i++) {
        if (points[i].y < ltl.y || points[i].y == ltl.y && points[i].x < ltl.x)
            ltl = points[i];
    }
    return ltl;
}
vector<point> grahamScan() {
    PP = LTL(points);
    sort(points.begin(), points.end(), cmp);
    vector<point> S, T;
    S.push_back(points[0]); S.push_back(points[1]);
    for (int i = points.size() - 1; i > 1; i--)T.push_back(points[i]);
    while (!T.empty()) {
        if (toLeftTest2(S[S.size() - 2], S[S.size() - 1], T[T.size() - 1])) {
            S.push_back(T[T.size() - 1]);
            T.pop_back();
        }
        else S.pop_back();
    }
    return S;
}
int main() {
    ios::sync_with_stdio(false);
    long long n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        point tmp;
        cin >> tmp.x >> tmp.y;
        tmp.id = i;
        points.push_back(tmp);
    }
    vector<point> result;
    if (points.size() > 2)result = grahamScan();
    else result = points;
    long long res = 1;
    for (int i = 0; i < result.size(); i++) {
        //cout << result[i].id << endl;//debug
        res = ((res % (n + 1)) * (result[i].id % (n + 1))) % (n + 1);
    }
    res = ((res % (n + 1)) * (result.size() % (n + 1))) % (n + 1);
    cout << res;
}

DOSBox-8086Assembly

最近我们学校在上8086汇编课程,需要写汇编程序。而Masm套件自带的debug调试程序是命令行的,不很好用。于是我在网上搜索了一下好用的8086汇编调试器,搜到了Turbo Debugger,经过试用。发现非常好用,带有GUI界面,非常人性化。于是就想把它和DOSBox集成到一起,制作一个输入源代码文件,即可自动开始调试的程序。经过努力,我做出了这个套件。我把它称作:DOSBox-8086Assembly。

继续阅读

洛谷 P2580 于是他错误的点名开始了

Trie树练手题,然而空间不够用最后一个点MLE,90

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
int trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    return node;
}
int main() {
    int n,m;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        int node=trieInsert(s);
        cnts[node]=1;
    }
    cin >> m;
    while (m--) {
        cin >> s;
        int node = trieInsert(s);
        if (cnts[node] == 1){
            cout << "OK" << endl;
            cnts[node]=2;
        }
        else if (cnts[node] == 0)cout << "WRONG" << endl;
        else if (cnts[node] == 2)cout << "REPEAT" << endl;
    }
}

洛谷 P1481 魔族密码

今学习Trie树:https://blog.csdn.net/weixin_43792276/article/details/98977397

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
void trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    cnts[node]++;
}
void trieAccumulate(int node) {
    for (int i = 0; i < 26; i++) {
        if (trie[node][i]) {
            cnts[trie[node][i]] += cnts[node];
            trieAccumulate(trie[node][i]);
        }
    }
}
int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        trieInsert(s);
    }
    trieAccumulate(0);
    int result = 0;
    for (int i = 0; i <= tot; i++)result = max(result, cnts[i]);
    cout << result;
}

BJD CTF Programming notakto_1

不知名CTF比赛的不知名题目,类井字棋,要写程序判断。
写了两个程序:如下:
C++有漏洞,够用就行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
using namespace std;
int process[10] = { 4 };
bool visited[10];
inline int cal(int x, int y) {
    return x * 3 + y;
}
bool& vis(int x, int y) {
    return visited[cal(x, y)];
}
bool check(int x, int y) {
    bool flag = false;
    flag |= vis(0, y) & vis(1, y) & vis(2, y);
    flag |= vis(x, 0) & vis(x, 1) & vis(x, 2);
    if (x == y)flag |= vis(0, 0) & vis(1, 1) & vis(2, 2);
    if (x + y == 2)flag |= vis(0, 2) & vis(1, 1) & vis(2, 0);
    return flag;
}
void print(int n) {
    for (int i = 0; i <= n; i++) {
        cout << process[i];
    }
    cout << endl;
}
void dfs(int step) {
    bool flag = true;
    for (int i = 0; i < 9; i++) {
        if (visited[i])continue;
        visited[i] = true;
        process[step] = i;
        if (check(i / 3, i % 3) == 0) {
            dfs(step + 1);
            flag = false;
        }
        visited[i] = false;
    }
    if (flag&&step%2==1)print(step);
}
int main() {
    visited[4] = true;
    dfs(1);
}

python连带着往外发socket麻烦得很:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from pwn import *
sock = remote("222.186.56.247",8122)
wordList = []
currentWord = ""

def findNewWord():
    global currentWord,wordList
    for elem in wordList:
        if elem[0:len(currentWord)]==currentWord:
            return elem
    raise Exception("Error:Word Not found!")

def loadDic():
    global wordList
    with open("situation.txt","r") as f:
        wordList = f.readlines()
   
def getIntfromSock(sock):
    sock.recvuntil("My move: ")
    x = sock.recv(1)
    if x==b' ': x = sock.recv(1)
    return int(x)

def payGame(i):
    global currentWord,wordList,sock
    print("the ith:",i)
    currentWord=""
    while len(currentWord) < 5:
        backupWord = findNewWord()
        print("Send:",backupWord[len(currentWord)])
        sock.sendline(str(backupWord[len(currentWord)]))
        currentWord += backupWord[len(currentWord)]
        if len(currentWord)==5:
            print("break")
            break
        currentWord += str(getIntfromSock(sock))
        print("currentWord",currentWord)
    sock.recvuntil("win!")

loadDic()
for i in range(150):
    payGame(i)
sock.interactive()

代码链接:notakto

lower_bound/upper_bound简易实现

lower_bound:

1
2
3
4
5
6
7
8
9
int lower_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<v)l=mid+1;
        else r = mid;
    }
    return l;
}

upper_bound:

1
2
3
4
5
6
7
8
9
int upper_bound(int v) { //arr[1..n],arr[0..n-1]
    int l = 0, r = n-1,mid;
    while (l < r) {
        mid = (l + r) / 2;
        if (arr[mid]<=v)l=mid+1;
        else r = mid;
    }
    return l;
}

洛谷 P4777 【模板】扩展中国剩余定理(EXCRT)

照着教程想了一下午,终于A了。。。
参考文章:
https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337

扩展欧几里得算法与中国剩余定理


https://www.cnblogs.com/yangsongyi/p/9867057.html
(快速乘规避溢出)
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll b[100005], a[100005]; //b是余数,a是模数
ll quickmultiply(ll a, ll b,ll mod) {
    if (b == 0)return 0;
    ll result = quickmultiply(a, b / 2, mod) % mod;
    result = 2*result%mod;
    if (b & 1)result = (result+a)%mod;
    return result;
}
ll ngcd(ll a, ll b) {
    return b == 0 ? a : ngcd(b, a % b);
}
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll excrt() {
    ll lcm = a[1], ans = b[1];
    for (int i = 2; i <= n; i++) {
        ll k1, k2, K, mod = lcm;
        ll gcd = exgcd(lcm, a[i], k1, k2);
        ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i];
        if ((minus % ngcd(lcm, a[i]) != 0))return -1;
        K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd);
        lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm;
    }
    return (ans % lcm + lcm) % lcm;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    cout<<excrt();
}