Partition the numbers
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given two integers x and N. Consider all integers between 1 and N inclusive, except x. We want to partition these integers into two disjoint sets (each integer has to appear in exactly one set) such that the sums of numbers in these sets are equal.
Find one valid partition or determine that it doesn't exist.
- The first line of the input contains a single 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 two space-separated integers x and N.
For each test case:
- If there's no way to partition the numbers into two sets with equal sums, print a single line containing the string "impossible" (without quotes).
- Otherwise, print a single line containing a string with length N.
- The x-th character of this string should be '2'.
- For each valid i ≠ x, the i-th character of this string should be '0' if number i should be in the first set or '1' if it should be in the second set.
- 1 ≤ T ≤ 10,000
- 2 ≤ N ≤ 1,000,000
- 1 ≤ x ≤ N
- 1 ≤ sum of N in all test cases ≤ 1,000,000
Subtask #1 (20 points): sum of N in all test cases ≤ 50
Subtask #2 (80 points): original constraints
Input: 3 2 4 5 5 1 2 Output: 0201 01102 impossible
|Tags||easy, jan18, kingofnumbers, kingofnumbers|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.