All submissions for this problem are available.
Read problems statements in Russian here
Chef has a special affection for sets of binary strings of equal length which have same numbers of 1's. Given three integers n, k and m, your task is to find the the lexicographically mth smallest string among strings which have length n and have k 1's. If no such string exists output -1.
To see what lexicographic order means . See http://en.wikipedia.org/wiki/Lexicographical_order
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
- The first and only line of each test case contains three space separated integers N , K and M
For each test case output the answer on a separate line .
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 350
- 1 ≤ K ≤ N
Input: 1 3 2 2 Output: 101
Example case 1. The set of strings in lexicographic order is "011", "101", and "110"
Subtask 1 (41 point):
- 1 ≤ N ≤ 20
Subtask 2 (59 points):
- 1 ≤ N ≤ 350
|Tags||arithmetic, big-integer, binary-numbers, combinations, easy, ltime05, permutations, vineetpaliwal|
|Time Limit:||2 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.