마트료시카(matryoshka)는 100여 년 전 러시아에서 시작된 인형의 한 종류이다. 가장 큰 특징은 크기가 모두 다른 여러 개의 인형으로 이루어진 세트이며, 작은 인형들이 큰 인형 안에 깔끔하게 들어간다는 점이다.

이 문제에서는 비슷한 중첩 패턴을 따르는 마트리곤(matrygon)을 다룬다. 마트리곤은 정 볼록 다각형 (regular convex polygon)들의 집합으로, 양의 넓이를 가지는 정 볼록 다각형 p_1, p_2, \dots, p_k가 다음 조건을 만족한다: 모든 i에 대해 p_{i+1}의 꼭짓점들은 p_i의 꼭짓점들 중 진부분집합(proper subset)과 정확히 겹친다. (즉, p_{i+1}는 p_i보다 꼭짓점의 개수가 엄격히 더 적다.)

예를 들어 아래 그림은 두 개의 마트리곤을 보여준다. 첫 번째 마트리곤은 정 볼록 다각형 3개로 이루어져 있다: 정24각형(변이 24개), 정육각형(변이 6개), 그리고 정삼각형(변이 3개)이다. 두 번째 마트리곤은 정 볼록 다각형 2개로 이루어져 있다: 정22각형(변이 22개)과 정11각형(변이 11개)이다. 이 두 마트리곤 모두 포함된 모든 다각형의 변의 총합은 33이다.

A matrygon containing a regular icositetragon (24 sides), a regular hexagon (6 sides), and an equilateral triangle (3 sides)

변의 총 개수 \mathbf{N}이 주어질 때, 마트리곤에 포함될 수 있는 다각형의 개수를 최대화하면서 그 마트리곤에 포함된 모든 다각형의 변의 총합이 정확히 \mathbf{N}이 되도록 할 수 있는 다각형의 최대 개수를 구하라.

#10405 upload 1 done 1 how_to_reg -

Matrygons timer 20s memory 1024MB

#10405

Matrygons 20s 1024MB