Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Binary strings are strings that can only have 0 or 1 as the characters. The hash value of a string is calculated using the formula bellow:
Where is the length of the string, is the ’th character of the string and and are two positive integers.
For example, let and , then “0010” will generate as the hash value.
Given the values of , , and , your task is to print the lexicographically smallest binary string of length that will generate as the hash value.
The input will start with an integer — the number of test cases.
The next lines will contain 4 space separated integers , , and each.
It is guaranteed that sum of in all the test cases does not exceed .
For each test case in a line print the lexicographically smallest binary string of length that generates as the hash value or print -1 if it doesn’t exist.
Input | Output |
---|---|
3 2 1 1 0 4 7 3 6 4 37 2 35 | 00 0010 -1 |
String is lexicographically smaller than string if it is shorter than and is its prefix, or if none of them is a prefix of the other and at the first position where they differ, the character in is smaller than the character in .
78% Solution Ratio
Wojciech.324122Earliest,
flukehn.841988Fastest, 0.0s
ArcturusLightest, 393 kB
Xi.498579Shortest, 779B
Login to submit
As it is a binary string, the hash value of a string will be the sum of some distinct power of base ...