Chef Goes Through Segments
All submissions for this problem are available.
Read problems statements in Mandarin Chinese here
Read problems statements in Russian here
Chef has a sequence of N segments: [L1, R1], [L2, R2], ..., [LN, RN]. He wants to transform the first segment to the last one (with index N). His plan is to do this big deal with a number of transformations: firstly he will transform
the first segment to the second one, then to the third one, then to the fourth one, and so on till N-th one.
Chef can use operation of a single type: shift one segment border by one unit. So, if he has segment [L, R], he can transform it into one of the following segments: [L + 1, R] (we will denote such operation with string L+), [L, R + 1] (will be denoted as R+), [L - 1, R] (L-), [L, R - 1] (R-). Chef doesn't like empty segments, therefore he cannot use any operation that makes a segment empty (L = R).
Chef really wants to transform his segment as fast as possible. Please, help him. Find the sequence with minimal number of operations that transforms his segment. If there are multiple such sequences pick the lexicographically minimal one.
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 line of each test case contains a single integer N denoting the number of segments Chef has.
The following N lines contain pairs of integers. The i-th line contains integers Li, Ri, denoting i-th Chef's segment.
For each test case print an answer - two lines. The first line should contain the minimal number of operations. The second line should contain the sequence of operations
without any whitespaces.
- 1 ≤ T, N ≤ 1000.
- -1000 ≤ Li < Ri ≤ 1000.
The total sum of N values for all test cases doesn't exceed 1000.
Input: 4 3 -1 0 0 1 3 5 1 0 1 3 -2 -1 -2 -1 -2 0 4 4 6 3 5 -1 1 1 2 Output: 9 R+L+R+L+R+L+R+L+R+ 0 1 R+ 13 L-R-L-L-L-L-R-R-R-R-L+R+L+
|Tags||cook41, easy, gerald, greedy|
|Time Limit:||1 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.