Eau de Cologne

Yukicoder No. 93 페가수스 문제 링크 문제 나오키 군은 $N \times N$격자의 $N$개의 "비마"(飛馬)라 불리는 신기한 말을 가지고 있습니다. "비마"는 쇼기의 비차(飛車)와 계마(桂馬)의 움직임을 합친 말입니다. (각주: 비차는 상하좌우로 원하는 만큼 이동할 수 있는 말이며, 계마는 앞으로 두 칸, 왼쪽 혹은 오른쪽으로 한 칸 움직일 수 있는 말입니다.) 어느 날 말을 배치하던 중에, "서로를 잡을 수 없도록 $N$개의 비마를 놓을 수 있는 방법"이 있다는 것을 발견했습니다. 이 조건을 만족하는 배치의 경우의 수를 $10^9+7$로 나눈 나머지를 구하는 프로그램을 작성해주세요. 단, 각 말의 구분은 없고, 모든 말은 위쪽 방향을 가리키고 있습니다. 입력 $N \ (1 \le N \l..

Yukicoder No. 67, 68 흔한 막대 자르기 문제 문제 링크 (1) No. 67 문제 링크 (2) No. 68 문제 유우키씨는 $N$ 개의 막대를 가지고 있고, $i$번째 막대의 길이는 $L_i$입니다. 막대는 (길이를 나누는 방향으로) 자유롭게 자를 수 있고, 연결하는 것은 불가능합니다. 유우키씨는 길이가 같은 막대를 $K$ 개 만들고 싶습니다. 만들 수 있는 $K$ 개 막대의 길이로 가능한 최댓값을 구하는 프로그램을 작성해주세요. 입력 입력 형식은 본문을 참고해주세요. No. 67 $1 \le N \le 200000 = 2 \times 10^5$ $1 \le L_i \le 1000000000 = 10^9$ $1 \le K \le 1000000000 = 10^{10}$ No. 68 이 문제는..

Yukicoder No. 54 Happy Hallowe'en 문제 링크 문제 오늘 할로윈을 맞아 타로군은 이웃에 사탕을 받으러 가기로 했습니다. 이웃에는, 타로군의 집 이외에 $N$ 채의 집이 있습니다. $i$번째 집에 가면 사탕을 $V_i$ 개 받을 수 있습니다. 이웃 친구와 공평하게 사탕을 나눠 가지기 위해서 이미 사탕을 $T_i$ 개 이상 가지고 있으면, (해당 집에서는) 사탕을 하나도 받을 수 없습니다. 타로군이 처음에 사탕을 하나도 가지고 있지 않고, 주위 집을 원하는 순서로 방문할 수 있을 때, 타로군이 받을 수 있는 사탕의 최댓값을 구해주세요. 같은 집은 $1$번 밖에 방문할 수 없습니다. 입력 $1$번째 줄에, 이웃의 집의 수 $N \ (1 \le N \le 10000)$이 주어집니다. 다..

Yukicoder No. 31 악의 믹스 주스 문제 링크 문제 믹스 주스가 다 떨어졌습니다. 믹스 주스의 원재료표시는, 차례대로 과일 $1$, 과일 $2$, $\cdots$, 과일 $N$입니다. 각 과일의 100% 주스를 섞어서 믹스 주스를 $V$리터 만들려고 합니다. 100% 과일 $k$ 주스는 $1$리터들이 한 팩에 $C_k$엔입니다. $V$ 리터 믹스 주스를 원재료표시의 변경 없이 만들기 위한 최소 비용을 구하는 프로그램을 작성해주세요. 즉, 믹스 주스에 대해서 과일 $k$가 들어간 비율 $p_k$는 $p_1 \ge p_2 \ge \cdots \ge p_N$이 되어야 합니다. 또한, 사용하지 않는 과일이 있어서는 안 됩니다. $1$리터 팩을 사서, 그 일부만 사용하는 것도 가능합니다. 입력 $1$번..

Yukicoder No. 14 최소공배수 정렬 문제 링크 문제 최소공배수를 막 배운 Larry는, 최소공배수 정렬을 하기로 했습니다. 여기서, "최소공배수 정렬"은, $N$개의 정수가 주어지고(중복을 포함할 수 있습니다), 각각을 $a_i \ ( 1 \le i \le N)$이라고 합시다. $a_1$을 고정하고, $a_2 \sim a_N$에 대해 각각 $a_1$과의 최소공배수를 구해서, 그 최소공배수가 작은 순으로 수열을 정렬합니다. (최소공배수가 같은 것이 여럿 있으면, 원래 수가 작은 것을 우선으로 합니다) Larry는, 이런 방식으로 정렬한 수열에 새로 $a_1 \cdots a_N$이란 이름을 붙이고, 조작을 계속합니다. 다음에는 $a_2$를 고정해서 ($a_1$도 고정한다), $a_3 \sim a_..

Yukicoder No. 1 길 바로 가기 문제 링크 문제 $N$개의 마을이 있습니다. 각각에는 $1$부터 $N$까지의 번호가 붙어있습니다. 각각의 도시는 직접 길로 연결되어 있을 수도, 아닐 수도 있습니다. 각 길은 마을 $S_i$부터 마을 $T_i$까지 가는 데에 비용 $Y_i$엔이 들고, $M_i$ 단위시간이 듭니다. 당신은 마을 $1$에 있습니다. $N$번 마을에 가고 싶습니다. 도로를 몇 개 사용하든 상관없지만, 당신은 $C$엔을 가지고 있습니다. (즉, 사용한 비용 $Y_i$의 합이 $C$를 넘어서는 안 됩니다.) 그중 가장 빠른 경로를 사용할 때, 드는 총 시간을 출력해 주세요. 이 제약 안에서 도착할 수 있는 방법이 없는 경우 $-1$을 출력해주세요. 입력 $1$번째 줄에는, 마을의 수를 ..