A - N-choice question
https://atcoder.jp/contests/abc300/tasks/abc300_a
문제
첫째 줄에 배열의 길이 $N$과 두 수 $A$와 $B$가 주어진다.
둘째 줄에 배열이 주어진다.
설명
배열 중에서 $A+B$와 일치하는 것의 인덱스를 출력한다.
소스 코드
1
2
3
4
5
6
|
import sys
input = sys.stdin.readline
n, a, b = map(int, input().split())
arr = [int(x) for x in input().split()]
print(arr.index(a+b)+1)
|
C - Cross
https://atcoder.jp/contests/abc300/tasks/abc300_c
문제
첫째 줄에 배열의 높이 $H$와 너비 $W$가 주어진다.
둘째 줄부터 $1+H$ 번째 줄까지 배열이 주어진다.
‘#‘이 크로스하는 경우를 세 주면 되는데, 사이즈별로 개수를 세 주어야 한다.
1
2
3
4
5
|
#...#
.#.#.
..#..
.#.#.
#...#
|
위 경우는 사이즈가 2인 것이다.
사이즈가 $1$인 개수부터 사이즈가 $N$인 개수까지 출력하면 된다.
여기서 $N$은 $min(H,W)$이다.
해설
중심점을 먼저 찾으면 되는데, 모든 중심점은 두 가지 조건을 만족한다.
- 모든 크로스의 중심점은 아래 에시의 형태이다.
- 모든 중심점의 좌표값은 다음 범위 내에 있다.
$1 \leq R \leq H-2$
$1 \leq C \leq W-2$
이걸로 중심점을 한 개씩 잡고, 1씩 크기를 늘려가면서 체크해주면 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import sys
input = sys.stdin.readline
def check(x, y):
i = 1
while True:
for dx, dy in zip([i, i, -i, -i], [i, -i, i, -i]):
nx, ny = x + dx, y + dy
if not nx in range(w) or not ny in range(h):
return i-2
if arr[ny][nx] != '#':
return i-2
i += 1
h, w = map(int, input().split())
arr = [input().rstrip() for _ in range(h)]
result = [0 for _ in range(min(h, w))]
for y in range(1, h-1):
for x in range(1, w-1):
if arr[y][x] == arr[y-1][x-1] == arr[y-1][x+1] == arr[y+1][x-1] == arr[y+1][x+1] == '#':
result[check(x, y)] += 1
print(*result)
|
D - AABCC
https://atcoder.jp/contests/abc300/tasks/abc300_d
문제
첫째 줄에 $N$이 주어진다. $(3 \leq N \leq 10^{12})$
$N$보다 크지 않은 양의 정수 중에서, $a^2\times b\times c^2$ 로 표현될 수 있는 수의 개수를 출력한다.
$(a<b<c)$ 이며, $a, b,c$는 소수이다.
해설
재미있는 문제였다.
$\sqrt{N}$까지 소수를 구하고, $a<b<c$가 되도록 세 가지 소수를 선택해 조건을 만족하는지 개수를 세 주면 된다.
커팅 없이 돌리면 시간 초과가 나고, 두 가지 커팅을 해 주어야 한다.
-
$b < c$ 이므로 $a^2 \times b^3$이 $N$ 보다 크다면 $a^2\times b\times c^2 \leq N$을 만족할 수 없으므로, 그 뒤는 확인하지 않아도 된다.
-
$a^2\times b\times c^2$ 가 $N$보다 크다면, 마찬가지로 그 뒤는 확인하지 않아도 된다.
소스 코드
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
|
import sys
from math import *
input = sys.stdin.readline
def eratosthenes(n):
primes = [True] * (n + 1)
p = 2
while p * p <= n:
if primes[p]:
for i in range(p * p, n + 1, p):
primes[i] = False
p += 1
primes_list = []
for p in range(2, n):
if primes[p]:
primes_list.append(p)
return primes_list
n = int(input())
primes = eratosthenes(floor(sqrt(n)))
l = len(primes)
count = 0
for i in range(l):
for j in range(i+1, l):
a, b = primes[i], primes[j]
if a*a*b*b*b > n:
break
for k in range(j+1, l):
a, b, c = primes[i], primes[j], primes[k]
if a*a*b*c*c <= n:
count += 1
else:
break
print(count)
|
