티스토리 뷰

공부

ONTAK 2016

구사과 2017.02.26 15:41

[2017.01.25 : 처음 작성]

[2017.03.03 : las / pod 문제 번역 실수가 있었습니다. 죄송합니다..]

[2017.03.13 : klo 문제 번역 실수가 있었습니다. 죄송합니다.. 이 글은 이제 마감합니다.]

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2016/

Problems

폴란드어 문제만 번역합니다. Day1 ~ Day4는 영어로 문제가 나오니까 그걸로 읽으시면 됩니다.

Day 5

Kłódka (klo)

0 이상 K 미만의 정수 배열 a[0] ... a[n-1] 이 있다. 0 이상 n-2 이하의 정수 x에 대해, 당신은 다음 두 연산을 할 수 있다.

 * inc(x) : a[x]와 a[x+1] 에, v <- (v + 1) mod k를 대입

 * dec(x) : a[x]와 a[x+1] 에, v <- (v + k - 1) mod k를 대입

(참고 : 원문에서는 두꺼운 손가락으로 자물쇠를 조작한다고 서술되어 있다.) 

정수 배열 a[0] ... a[n-1]을 b[0] ... b[n-1]으로 만들어야 한다. 당신은 inc와 dec를 합해서 "m/2"번 쓸 수 있다. "m/2"번 쓴 이후에도 a[i] != b[i]인 원소가 존재한다면 이러한 원소들은 수작업으로 바꿀 예정이다. 수작업으로 바꿔야 하는 원소의 개수를 최소화하여라.

Input

첫번째 줄에 배열의 크기 n, m, k가 주어진다. (1 <= n <= 1000, 1 <= m <= 100000, 1 <= k <= 100)

두번째 줄에 배열 a[0] ... a[n-1]이 주어진다.

세번째 줄에 배열 b[0] ... b[n-1]이 주어진다.

Output

최소값을 출력하라.

Limits and Subtasks

메모리 제한은 64MB이다.

1. m <= 500 (24점)

2. n <= 100 (24점)

3. nk <= 5000 (26점)

4. 추가 제약 조건 없음 (26점)

Example

입력

5 10 8

0 0 0 0 0

1 3 2 7 1

출력

1

설명

10번의 연산으로 1 3 2 7 7을 만들 수 있다. 마지막 수만 바꾸면 된다. 이것이 최적이다. 


Nowy Manhattan (man) 

두 점 (x1, y1)과 (x2, y2)이 주어졌을 때, 두 점간의 맨하탄 거리는 |x1-x2| + |y1-y2| 로 정의된다. 초기에 빈 점들의 집합 S가 있을 때, 다음 두 질의를 Q번 처리 해야 한다.

 * 1. 점 (x, y)를 집합 S에 삽입하라.

 * 2. 집합 S에 있는 점 중, 현재 점 (x, y)와 맨하탄 거리가 가장 짧은 점과의 거리를 출력하라.

Input

첫번째 줄에 질의의 수 Q가 주어진다. (1 <= Q <= 200000)

이후 Q개의 줄에 질의가 주어진다. 질의는 "a x y" (a = {1, 2}, 1 <= x, y <= 200000) 과 같은 형태의 세 정수가 주어지는데, 만약 a = 1이면 집합 S에 점 (x, y)를 삽입해야 하고, a = 2이면 집합 S에 있는 점 중 현재 점 (x, y)와 거리가 가장 짧은 점과의 거리를 출력해야 한다.

첫번째 질의는 항상 a = 1이다.

Output

a = 2인 질의가 주어질 때마다 순서대로 답을 새 줄로 구분하여 출력한다.

Limits and Subtasks

메모리 제한은 512MB이다.

1. Q <= 2000 (15점)

2. a = 2인 쿼리가 들어온 이후부터는 a = 1인 쿼리가 들어오지 않는다. (25점)

3. 추가 제약 조건 없음 (60점) 

Example

입력

6

1 4 2

2 3 3

2 1 5

1 10 8

2 4 3

2 1 1

출력

2

6

1

4

Słowa (slo) 

N개의 알파벳 소문자로 이루어진 문자열이 주어진다. 당신은 이제 임의의 길이의 알파벳 소문자로 이루어진 문자열인 "템플릿 문자열"을 만들 것이다. 템플릿 문자열은 문자열에서 1개 혹은 2개의 문자가 "Special" 하다고 지정되어 있다. 

좋은 템플릿 문자열은, N개의 문자열 중, 템플릿 문자열과 길이가 같으며, 템플릿 문자열과 정확히 일치하지는 않지만, Special한 글자를 제외한 모든 글자가 템플릿 문자열과 일치하는 문자열의 개수를 최대화하는 문자열을 뜻한다. 가장 좋은 템플릿 문자열과 일치하는 문자열의 개수는 몇개인가?

Input

첫번째 줄에 문자열의 수 N이 주어진다. (1 <= N)

이후 N개의 줄에 각각의 문자열의 길이 Li와, 문자열 Si가 주어진다. 

입력으로 주어지는 문자열은 모두 서로 다르다. 모든 문자열의 길이의 합은 200000을 넘지 않는다.

Output

가장 좋은 템플릿 문자열과 일치하는 문자열의 개수를 출력한다.

Limits and Subtasks

메모리 제한은 128MB이다.

1. 모든 문자열의 길이의 합은 2000을 넘지 않는다. (25점)

2. 추가 제약 조건 없음 (75점) 

Example

입력

6 kamera 

4 kula 

4 kura 

4 tura 

6 kurant 

6 kaseta 

6 kareta 

6 kaleta

출력

4

(설명 : ka[a]e[a]a 를 생각해면 kamera kaseta kareta kaleta와 동일합니다)

Day 6

Największy wspólny dzielnik (gcd)

길이 n의 수열과, p개의 질의가 들어온다. 각각의 질의로 들어온 정수 d에 대해서, gcd(a_p, a_p+1, ...., a_q) = d 인 쌍 (p, q)의 개수를 출력하라. 질의를 온라인으로 처리하여야 한다.

Input

첫번째 줄에 정수의 수 n이 주어진다. (1 <= n <= 300000)

두번째 줄에 n개의 정수 a_i (1 <= a_i <= 10^18) 이 주어진다.

세번째 줄에 질의의 수 p가 주어진다. (1 <= p <= 300000)

이후 p개의 줄에 정수 c_i가 주어진다. c_i를, i-1번째 질의의 답인 ans_{i-1}과 xor 시킨 것이 d_i 이다. ans_0 = 0이라 하자.

Output

p개의 줄에 쌍의 개수 ans_{i}를 새 줄로 구분해서 출력한다.


Limits and Subtasks

메모리 제한은 512MB이다.

1. N, Q <= 120, d_i <= 40000 (11점)

2. N, Q <= 100000, d_i <= 100000 (1점)

3. s = 1, d_1 = 1 (25점)

5. 추가 제약 조건 없음 (53점) 

Example

입력

6

4 2 6 3 15 5

2

5

1

출력

2

4

Symulator Obrońcy Piłkarskiego 2016 (obr)

평면 상에 n개의 점이 주어진다. 이 중 어떠한 세 점도 한 직선 상에 존재하지 않는다. 당신은 임의의 직선을 골라서, 직선과의 거리가 D 이하인 점들을 모두 색칠할 수 있다. k개 이상의 점을 색칠할 수 있는 직선이 존재하는 최소 D를 출력하라.

Input

첫번째 줄에 점의 수 n과 k가 주어진다. (3 <= k <= n <= 2500)

이후 n개의 줄에 점의 위치인 정수 x_i, y_i (|x_i|, |y_i| <= 10^6) 이 주어진다. 

Output

최소 D를 출력하라. 절대 or 상대 오차 범위가 10^-9 안에 들어와야 한다.

Limits and Subtasks

메모리 제한은 256MB이다.

1. N <= 12 (10점)

2. N <= 80 (22점)

3. N <= 250 (22점)

4. N <= 1000, K <= 30 (26점)

5. 추가 제약 조건 없음 (30점) 

Example

입력

4 3

0 0

1 0

1 1

0 1

출력

0.353553390593

입력

4 4

0 0

1 0

1 1

0 1

출력

0.500000000000


Przesyłka (prz)

Weighted Directed Graph가 주어진다. (멀티 간선과 자가 루프는 없다). 이 중 K개의 정점에 술집이 있다. 

Q개의 쿼리로 시작점과 끝점이 주어지면, 시작점에서 끝점으로 가는 경로 중, 술집을 S번 이상 방문하는 경로를 출력해야 한다. 갔던 술집을 다시 갈 수는 있지만, 바로 다음 번에 가는 것은 안된다. (즉 처음에 3번 술집에 들렀다면 다음에 들리는 것은 3번 술집이면 안되고, 그 다음에 들리는 것은 3번 술집이어도 됨.) 이러한 경로 중, 최단 경로의 길이를 출력하라.

Input

첫번째 줄에 N, M, K, S, Q가 주어진다. (1 <= N, M, Q <= 100000, 1 <= K, S <= 100)

두번째 줄에 K개의 서로 다른 1 이상 N 이하의 정수가 주어진다. 술집이 있는 정점의 번호이다. 정점은 1번부터 N번까지 번호가 매겨져 있다.

이후 M개의 줄에 간선의 정보가 S_i, E_i, C_i 로 주어진다. S_i에서 E_i로 가는 가중치 C_i의 간선을 뜻한다. (1 <= S_i, E_i <= N, 1 <= C_i <= 100000)

이후 Q개의 줄에 각 쿼리의 시작점과 끝점이 주어진다. 

Output

각각의 쿼리마다 최단 경로의 길이를 새 줄로 구분하여 출력하라. 경로가 없으면 -1을 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. Q <= 1 (10점)

2. N, M <= 100 (20점)

3. N, M <= 1000 (20점)

4. 추가 제약 조건 없음 (50점) 

Example

입력

4 6 2 4 6 

1 2 

1 2 50 

2 1 100 

2 3 90 

3 2 10 

3 4 20 

4 1 40 

1 2 

2 3 

3 4 

2 1 

3 2 

4 3

출력

200 

390 

370

250 

260 

330


Day 7

Las (las)

Undirected Forest가 주어진다. 몇개의 간선을 추가해서 이를 트리로 만들고 싶다. 간선을 추가하는 여러가지 방법 중, 각각의 정점 쌍의 거리의 합 (=sigma(i < j) dist(i, j)) 을 최소화하고 싶다. 

Input

첫번째 줄에 정점의 수 n, 간선의 수 m이 주어진다. (0 <= m < n <= 200000)

이후 m개의 줄에 간선의 시작점과 끝점 s e가 주어진다. (1 <= s, e <= n)

Output

가능한 거리 합의 최솟값을 구하여라.

Limits and Subtasks

메모리 제한은 128MB이다.

1. N <= 15 (15점)

2. M <= 3000 (25점)

3. 추가 제약 조건 없음 (60점) 

Example

입력

4 2

1 2

3 4

출력

10

Moda na sukces (mod)

1 이상 N 이하의 자연수를 정의역과 치역으로 하는 일대일 대응 함수를 순열이라 한다. 

크기 N의 순열 A와 B가 주어진다. 모든 i = [1, N] 인 자연수에 대해 A^k(i) = B^k(i) 인 최소 k > 0을 찾아라. 수가 너무 커질 수 있으니, 10^9 + 7로 나눈 나머지를 출력하라.

Input

첫번째 줄에 n이 주어진다. (1 <= n <= 1000000)

두번째 줄에 A(i)가 1 ~ n 순서대로 주어진다. 

세번째 줄에 B(i)가 1 ~ n 순서대로 주어진다. 

Output

모든 i = [1, N] 인 자연수에 대해 A^k(i) = B^k(i) 인 최소 k > 0을 찾아라. 수가 너무 커질 수 있으니, 10^9 + 7로 나눈 나머지를 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. n <= 20 (10점)

2. n <= 100 (15점)

3. n <= 600 (15점)

4. n <= 5000 (20점)

5. n <= 100000 (20점)

6. 추가 제약 조건 없음 (20점) 

Example

입력

2 3 4 1

3 2 4 1

출력

12

Podciąg (pod)

A와 B가 게임을 하고 있다. B는 처음에 자신의 문자열의 원소 중 몇개를 지워서, 부분 수열을 만든다. (부분 수열은 연속하지 않아도 되며, 부분 수열은 하나 이상의 원소를 지워야 한다.) 이렇게 만든 부분 수열이 A의 부분 수열이라면 A가 이기고, 아니라면 B가 이긴다.

A와 B는 길이 n / k의 문자열을 가지고 있다. A는 항상 이긴다는 조건 하에 자신의 문자열의 맨 뒤 원소 몇개를 제거할 예정이다. (즉 prefix를 가지고 게임을 할 예정이다.) A가 이김을 보장해주는 가장 짧은 prefix의 길이를 출력하라. 전체 문자열을 가져도 A가 진다면 -1을 출력하라.

Input

첫번째 줄에 n, k가 주어진다. (1 <= k <= n <= 500000)

두번째 줄에 A가 가지는 길이 n의 문자열이 주어진다.

세번째 줄에 B가 가지는 길이 k의 문자열이 주어진다.

Output

A가 이김을 보장해주는 가장 짧은 prefix의 길이를 출력하라. 전체 문자열을 가져도 A가 진다면 -1을 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. n, k <= 3000 (20점)

2. n <= 30000, k <= 3000 (30점)

3. 추가 제약 조건 없음 (50점) 

Example

입력

7 4

bababab

abba

출력

5


Solutions

더보기

신고

'공부' 카테고리의 다른 글

Atcoder Regular Contest / Atcoder Grand Contest  (0) 2017.04.01
Opencup 2017 - GP of Poland  (4) 2017.03.27
ONTAK 2016  (0) 2017.02.26
Facebook Hacker Cup 2017 Round 3  (1) 2017.01.30
지하철 1호선 (트리와 쿼리 8) 풀이  (0) 2017.01.26
Centroid Decomposition  (0) 2017.01.26
댓글
댓글쓰기 폼
공지사항
Total
94,775
Today
200
Yesterday
200