Solutions are presented as using the least memory and the fastest execution time. It also takes the top
10 most recent solutions from each language. If you want to limit to a specific index, click the
"Solved" button and go to that problem.
Problems
You are given an array (a_1, a_2, \ldots, a_n), where (n \leq 8) and (a_1 + a_2 + \cdots + a_n \leq 100). Construct a simple polygon(^{\text{∗}}) with at most (333) vertices that has exactly ()\frac{(a_1 + a_2 + \cdots + a_n)!}{a_1! a_2! \cdots a_n!}() different triangulations(^{\text{†}}). It can be proven that such a polygon always exists. (^{\text{∗}})A simple polygon is a polygon that does not intersect itself and has no holes. In other words, no two non-consecutive edges can have common points, and consecutive edges must have exactly one common point — the vertex between them. Consecutive edges may be collinear. (^{\text{†}})A triangulation of a polygon with (m) vertices is a set of (m-3) diagonals that intersect only at vertices. A diagonal is a segment between two vertices which lies inside the polygon and has exactly two common points with the polygon sides — the vertices it connects. The first line of each test contains a single integer (n) ((2 \leq n \leq 8)) — the number of elements in the array. The second line contains (n) integers (a_1, a_2, \ldots, a_n) ((1 \leq a_i \leq 100)) — the elements of the array. It is guaranteed that (a_1 + a_2 + \cdots + a_n) does not exceed (100). In the first line, output a single integer (m) ((3 \leq m \leq 333)) — the number of vertices in the polygon. In the (i)-th of the following (m) lines, output two integers (x_i), (y_i) ((-10^6 \leq x_i, y_i \leq 10^6)) — the coordinates of the (i)-th vertex of the polygon. The polygon must be simple. The vertices may be given in either clockwise or counterclockwise order. In the first test, the required polygon has to have (\tfrac{4!}{1! 1! 2!} = 12) triangulations. The following are all the triangulations of the example polygon. In the second test, the required polygon has to have (\tfrac{5!}{4! 1!} = 5) triangulations. |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|
329905710 |
akulsareen |
F |
July 19, 2025, 9:45 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
47 |
61 |
102400 |
|
|
|
329886143 |
potato167 |
F |
July 19, 2025, 5:54 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
47 |
61 |
102400 |
|
|
|
329904212 |
akulsareen |
F |
July 19, 2025, 9:36 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
47 |
62 |
0 |
|
|
|
329874491 |
taeyeon_ss |
F |
July 19, 2025, 4:41 p.m. |
OK |
C++17 (GCC 7-32) |
TESTS |
47 |
77 |
102400 |
|
|
|
329889395 |
-14 |
F |
July 19, 2025, 6:20 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
61 |
102400 |
|
|
|
329883651 |
BurnedChicken |
F |
July 19, 2025, 5:36 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
61 |
102400 |
|
|
|
329888931 |
0wuming0 |
F |
July 19, 2025, 6:16 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
62 |
102400 |
|
|
|
329882839 |
rin204 |
F |
July 19, 2025, 5:30 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
62 |
102400 |
|
|
|
329880986 |
Pa.Nic |
F |
July 19, 2025, 5:19 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
77 |
0 |
|
|
|
329883766 |
Abdelrahman_Mounir |
F |
July 19, 2025, 5:36 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
77 |
102400 |
|
|
|
329872600 |
zhiganov_v |
F |
July 19, 2025, 4:37 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
78 |
102400 |
|
|
|
329873203 |
Benq |
F |
July 19, 2025, 4:39 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
93 |
102400 |
|
|
|
329871638 |
VladProg |
F |
July 19, 2025, 4:35 p.m. |
OK |
C++20 (GCC 13-64) |
TESTS |
47 |
93 |
102400 |
|
|
|
329925578 |
Aayush_coded |
F |
July 20, 2025, 5:08 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
46 |
102400 |
|
|
|
329890406 |
kaiboy |
F |
July 19, 2025, 6:29 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
61 |
102400 |
|
|
|
329925420 |
Aayush_coded |
F |
July 20, 2025, 5:06 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329884894 |
hos.lyric |
F |
July 19, 2025, 5:45 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329883226 |
aabid21 |
F |
July 19, 2025, 5:33 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329883043 |
antontrygubO_o |
F |
July 19, 2025, 5:32 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329881248 |
Halzion |
F |
July 19, 2025, 5:20 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329874993 |
risujiroh |
F |
July 19, 2025, 4:43 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329873761 |
ksun48 |
F |
July 19, 2025, 4:40 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329873307 |
Kevin114514 |
F |
July 19, 2025, 4:39 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
47 |
62 |
102400 |
|
|
|
329871992 |
conqueror_of_tourist |
F |
July 19, 2025, 4:36 p.m. |
OK |
PyPy 3-64 |
TESTS |
47 |
109 |
307200 |
|
|
|
329923902 |
shanks_jr10 |
F |
July 20, 2025, 4:43 a.m. |
OK |
Python 3 |
TESTS |
47 |
93 |
307200 |
|
|
remove filters
Back to search problems