PESADA05 - Binary Search the product of Large Intergers
Multiply two large nonnegative integers and search it in a lexicographically sorted list of a large number of large integers.
Input
The input begins with a positive integer n indicating the size of the list of large integers (1 <= n <= 1000000). It is followed by n lines having a nonnegative large integer on each line and they are listed in lexicographic order (1 <= number of digits in the large integer <= 2000). A new line has a positive integer t indicating the number of pairs of large integers. It is followed by t lines having two nonnegative large integers in each line separated by a space (1 <= number of digits in the large integer <= 1000).
Output
Output to have t lines where each line has two numbers separated by a space. First number in each line is the product of two large integers provided in the input and the other number is the 0-based index of the product in the list of n large integers provided in the earlier part of the input.
Example
Input: 10
0
1186379681736876234567001234
2345671234
30
45678923
56789143
789
78912123453245
80779853376
911234341234
5
1234 0
5 6
123456 654321
876142389164 5761523128
1186379681736876234567001234 1 Output: 0 0
30 3
80779853376 8
5047914638589562584992 -1
1186379681736876234567001234 1
Added by: | Prof. Channa Bankapur |
Date: | 2015-01-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C |