Power Sum solution codechef
You are given a sequenceof integers such that every element is a non-negative power of .
A sequence is called
good if its sum is a non-negative power of . You would like to turn into a
To achieve this, you can perform the following operation on:
- Pick a non-empty subsequence of , pick a positive integer such that , and multiply every element of this subsequence by .
Find the minimum number of operations required to turninto a good sequence. Also, find one sequence of operations which does this. If there are multiple possible answers, you may find any of them.
- The first line of input contains a single integer , denoting the number of test cases. The description of test cases follows.
- The first line of each test case contains a single integer .
- The second line of each test case contains space-separated integers .
For each test case, print the answer in the following format:
- First, print one line containing an integer , denoting the minimum number of moves required.
- Then, print
lines describing operations.
- Each operation is described by lines.
- On the first line, print two space-separated integers and , denoting the size of the subsequence and the multiplier for this operation.
- On the second line, print distinct space-separated integers denoting the indices of the elements chosen to be multiplied in this operation. These integers can be printed in any order.
Subtask #1 (100 points): Original constraints
Sample Input 1
2 4 4 8 4 32 3 2 2 4
Sample Output 1
1 3 2 1 2 3 0
Test case: Multiplying the and elements by turns the array into , whose sum is .