[Codeforces] AIM Tech Round 5 (rated, Div. 1 + Div. 2)

드디어 제가 풀었던 코포들 중에 마지막 코포 정리입니다!

후후... 이 5번째 코포 풀이를 완성하면 왠지 떡상을 할 것 같은 좋은 느낌(?)이 듭니다. 후후후

A. Find Square

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Consider a table of size $n\times m$, initially fully white. Rows are numbered $1$ through $n$ from top to bottom, columns $1$ through $m$ from left to right. Some square inside the table with odd side length was painted black. Find the center of this square.

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 115$) — the number of rows and the number of columns in the table.

The $i$-th of the next $n$ lines contains a string of $m$ characters $s_{i1}{s}_{i2}\dots s_{im}$ ($s_{ij}$ is 'W' for white cells and 'B' for black cells), describing the $i$-th row of the table.

Output

Output two integers $r$ and $c$ ($1\le r\le n$, $1\le c\le m$) separated by a space — the row and column numbers of the center of the black square.

Examples

input

Copy

5 6
WWBBBW
WWBBBW
WWBBBW
WWWWWW
WWWWWW

output

Copy

2 4

input

Copy

3 3
WWW
BWW
WWW

output

Copy

2 1

문제 해석

요약을 많이 해드리겠습니다.

직사각형 B의 중심점의 위치를 출력하면 됩니다.

(단, 직사각형 B의 길이는 언제나 홀 수이기 때문에, 중앙점이 무조건 존재합니다.) 

어떻게 풀까?

B는 직사각형이기 때문에, 왼쪽 위부터 한칸씩 보면, 연속되는 B의 가로와 세로의 위치를 구함으로써 가로와 세로의 길이를 구할 수 있습니다.

그리고, 중앙 위치는 맨 왼쪽 위의 B좌표 + 가로길이 / 2, 세로 길이 /2 지점이 되겠죠!

코드 

#pragma once
#include<cstdio>
 
int n, m;
char map[117][117];
 
struct cod {
    int r, c;
};
 
cod findMID(int r, int c) {
    int nc = c;
    
    while (map[r][nc] == 'B') {
        nc++;
    }
 
    int nr = r;
    while (map[nr][c] == 'B') {
        nr++;
    }
    return { (nr + r) / 2, (c + nc) / 2 };
}
 
int main() {
    scanf("%d %d\n", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        scanf("%s\n", map[i]+1);
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == 'B') {
                cod res = findMID(i, j);
                printf("%d %d\n", res.r, res.c);
                return 0;
            }
        }
    }
    return 0;
 
}

B. Unnatural Conditions

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let $s\left(x\right)$ be sum of digits in decimal representation of positive integer $x$. Given two integers $n$ and $m$, find some positive integers $a$ and $b$such that

• $s\left(a\right)\ge n$,
• $s\left(b\right)\ge n$,
• $s(a+b)\le m$.

Input

The only line of input contain two integers $n$ and $m$ ($1\le n,m\le 1129$).

Output

Print two lines, one for decimal representation of $a$ and one for decimal representation of $b$. Both numbers must not contain leading zeros and must have length no more than $2230$.

Examples

input

Copy

6 5

output

Copy

6 
7

input

Copy

8 16

output

Copy

35 
53

Note

In the first sample, we have $n=6$ and $m=5$. One valid solution is $a=6$, $b=7$. Indeed, we have $s\left(a\right)=6\ge n$ and $s\left(b\right)=7\ge n$, and also $s(a+b)=s\left(13\right)=4\le m$.

문제 해석

s(a) 라는 함수가 있습니다. 이 함수는 a의 모든 자리수를 더한 수 입니다.

두 수 n과 m이 주어질 때,

s(a) >= n,

s(b) >= n,

s(a+b) <= m 인 a,b 쌍을 출력하세요!

어떻게 풀까?

이 문제 풀이는 두 쌍의 길이가 2230까지 될 수 있고, n, m은 이에 반해 1129이기 때문에 매우 쉽게 구할 수 있습니다.

자! 일단, 제 아무리 길던 수던간에 s(a+b)를 1로 만들 수 있습니다!

4444 와 5556을 더해보죠!

두 수를 더하면 10000가 됩니다.

네! s(10000) = 1 + 0 + 0 + 0+ 0 = 1 입니다.

또한, n이 1129입니다!

그렇다는 말은,

1을 1129개 쓰면 s(1 ..... 1) = 1129가 된다는 것이죠.

그럼 1129는 1129자리 수가 아니겠습니까!?

에서 위 수를 빼면, 88888888888888..... 888889 라는 수가 나올 것입니다.

이 수를 s()함수에 넣으면 111111111...... 111111 보다 당연히 큰 수가 나올 것입니다.

즉, 어떤 경우에서든, 위 수를 출력하면 됩니다!

모든 조건에서 맞는 답을 구할 수 있는 것이죠!

코드

#pragma once
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
 
int main() {
    string str[2];
 
    int n, m;
    scanf("%d %d\n", &n, &m);
 
    for (int i = 0; i < 1129; i++) {
        str[0].push_back('1');
    }
    
    
    for(int i = 0; i < 1128; i++) {
        str[1].push_back('8');
    }
    str[1].push_back('9');
    cout << str[0] << '\n';
    cout << str[1] << '\n';
    return 0;
}

시간 복잡도

입력에 전혀 상관없기 때문에 O(1)입니다.

C. Rectangles

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given $n$ rectangles on a plane with coordinates of their bottom left and upper right points. Some $(n-1)$ of the given $n$ rectangles have some common point. A point belongs to a rectangle if this point is strictly inside the rectangle or belongs to its boundary.

Find any point with integer coordinates that belongs to at least $(n-1)$ given rectangles.

Input

The first line contains a single integer $n$ ($2\le n\le 132674$) — the number of given rectangles.

Each the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($-{10}^9\le x_1<x_2\le {10}^9$, $-{10}^9\le y_1<y_2\le {10}^9$) — the coordinates of the bottom left and upper right corners of a rectangle.

Output

Print two integers $x$ and $y$ — the coordinates of any point that belongs to at least $(n-1)$ given rectangles.

Examples

input

Copy

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

output

Copy

1 1

input

Copy

3
0 0 1 1
0 1 1 2
1 0 2 1

output

Copy

1 1

input

Copy

4
0 0 5 5
0 0 4 4
1 1 4 4
1 1 4 4

output

Copy

1 1

input

Copy

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

output

Copy

3 4

Note

The picture below shows the rectangles in the first and second samples. The possible answers are highlighted.

The picture below shows the rectangles in the third and fourth samples.

문제 해석

n개의 사각형이 주어집니다!

각 사각형은 왼쪽 아래 꼭지점의 (x, y)와 오른쪽 위 꼭지점 (x2, y2)로 주어집니다!

그리고 n개의 사각형 중에서  n-1개의 사각형이 공유하는 점이 있습니다! 

이 때, n-1개의 사각형에 겹치는 점 하나 아무거나하나를 출력하세요!!

어떻게 풀까?

이번 문제도 이전에 코드포스에서 나왔던 구간 겹치기 문제와 유사합니다!

우선, 문제에 따르면, n-1개에 겹쳐지는 점은 무조건 존재합니다!

그러면, 점을 어떻게 구할 수 있을까요!?

이전 코드포스에서 풀었떤 최대 공통 구간의 길이를 구하는 것과 비슷합니다.

모든 사각형이 공유하는 점 이라는 것은, 시작점의 x좌표와 y좌표는 우선, 다른 사각형의 시작점의 x좌표와 y좌표보다 커야합니다!

가장 큰 시작점의 좌표가 xma, yma 라고 하겠습니다.

만약, 이 보다 작은 x, y 값을 선택하면, 

xma와 yma는 해당 좌표를 포함하지 못하기 때문에 답이 될 수 없습니다!

또한, 이와 반대로 오른쪽 끝의 x좌표와 y좌표는 다른 사각형의 끝점 x좌표와 y좌표보다 작아야할 것입니다!

따라서, 시작점의 x좌표, 시작점의 y좌표, 끝 점의 x좌표, 끝 점의 y좌표를 정렬한 후에,

시작 점에서는 가장 큰 x좌표와 y좌표, 끝 점에서는 가장 작은 x좌표와 y좌표를 고르면 됩니다!

그리고, 또 하나의 조건이 있죠! 사각형의 특성상, 끝 점의 x좌표는 시작점의 x좌표보다 같거나 커야합니다!

마찬가지로 끝 점의 y좌표도 시작점의 y좌표보다 커야하죠!

위 조건을 만족하지 않는다면, 겹치지 않는 사각형 이라는 것이겠죠.

하지만, 이 문제에서의 조건은 n-1개의 사각형이 겹쳐야 한다는 것입니다!

하지만, 이 문제도 걱정할 것이 없습니다!

일단 1~n번째 사각형을 모두 순회하면서, 사각형을 하나씩 제거하는 경우를 보겠습니다.

i번째 사각형의 시작점의 x좌표를 xis, y좌표를 yis라고 하겠습니다.

끝점의 x좌표는 xie, y좌표는 yie라고 하죠!

만약, 정렬한 시작점 x의 좌표가 xis와 같다면 어떻게 해야할까요!?

해당 사각형의 점은 없어야 하기 때문에, 그 다음으로 큰 값을 가져오면 됩니다.

이는 나머지 세 점에 대해서도 모두 마찬가지이죠!

그리고 이렇게 고른 점 4개를 이용해서 위에서 봤던 사각형을 만들 수 있는가에 대한 판별식을 써서 만약 사각형이 될 수 있는 점 네 개라면,

둘 중에 아무거나 출력해주면 정답이 됩니다!!

코드

#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
 
using namespace std;
 
typedef tuple<int, int, int,int> ti4;
typedef vector<int> vi;
ti4 rect[200000];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    vi vl, vr, vd, vu;
 
    int l, r, d, u;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> d >> r >> u;
        vl.push_back(l);
        vd.push_back(d);
        vr.push_back(r);
        vu.push_back(u);
        rect[i] = { l,d,r,u };
    }
    sort(vl.begin(), vl.end());
    sort(vr.begin(), vr.end());
    sort(vd.begin(), vd.end());
    sort(vu.begin(), vu.end());
 
    for (int i = 0; i < n; i++) {
        tie(l, d, r, u) = rect[i];
        int xmin, xmax, ymin, ymax;
 
        xmin = l == *vl.rbegin() ? *next(vl.rbegin()) : *vl.rbegin();
        xmax = r == *vr.begin() ? *next(vr.begin()) : *vr.begin();
        ymin = d == *vd.rbegin() ? *next(vd.rbegin()) : *vd.rbegin();
        ymax = u == *vu.begin() ? *next(vu.begin()) : *vu.begin();
 
        if (xmin <= xmax && ymin <= ymax) {
            cout << xmin << ' ' << ymin << '\n';
            return 0;
        }
    }
    return 0;
}

시간 복잡도

시간 복잡도는 n개의 데이터를 정렬하기 위한 O(N log N)입니다!

여담

드디어.. 다 올렸습니다.... 기쁘다.. 좀쉬어야게써요