Two k-Convex Polygons
All submissions for this problem are available.
Given n sticks' lengths, determine whether there is a solution to choose 2k out of them and use these 2k sticks to form two k-convex polygons (non-degenerated), namely, two convex polygons each has exactly k sticks as its sides, and every adjacent sticks are not parallel.
The first line contains two space-separated integers n and k, denoting the number of sticks and the size of convex polygon we needed.
The second line contains n positive integers, denoting the lengths of sticks.
Print "Yes" (without quotes) in the first line if exists a solution. Otherwise print "No" (without quotes) instead.
If such solution exists, you should output a plan in the second line. Print 2k indexes (indexes start from 1) of the sticks you chosen. First k sticks compose the first k-convex polygon. And the later k sticks form the second. If there are more than one solution, output any.
- 2k ≤ n ≤ 1000
- 3 ≤ k ≤ 10
- 1 ≤ length of each stick ≤ 109
Input 1: 6 3 1 1 1 2 2 2 Output 1: Yes 1 2 3 4 5 6 Input 2: 6 3 1 2 3 100 200 300 Output 2: No
Example case 1: 1 1 1 and 2 2 2 form two triangles.
Example case 2: Please be careful that convex polygons must be non-degenerated.
|Tags||june13, math, medium-hard, shangjingbo|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.