LCPC12I - No more Johnny
Sure you are bored from Johnny and his stories, so we decided that we will not mention Johnny in this problem. As you are one of the cleverest students in programming course, it is required to develop a magic calculator. Magic calculators work on integer numbers and have two operations only: '&' (and) and '|' (or). As you know & and | operation works with bits so 3 & 2 will be 2 as 11 & 10 = 10 which is 2. But in our calculator & and | operation will have a different meaning. Every positive integer n > 1 can be represented in exactly one way as a product of prime (A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself) powers:
Where p1 < p2 < ... < pk are primes and the αi are positive integers; 1 is represented by the empty product. In this problem you will work with prime factors of numbers that is & means you will take minimum power for each prime between the 2 numbers unless prime exist in one and doesn't exist in the other in such case you will take the power of prime as it is,| you will take maximum power for each prime between the 2 numbers unless prime exist in one and doesn't exist in the other in such case you will take the power of prime as it is. For example 6 | 9 will be 21 * 31 | 33 so result will be 21 * 33 that will be 18. Also 6 & 9 will be 21 * 31 & 33 so result will be 21 * 31 that will be 6. Given a set of numbers and operations between them, print the final result as primes with powers (show prime factors of the result).
Input
The first line of input contains an integer T, the number of test cases. T test cases follows, the first line of each test case contains N where 1 <= N <= 100 represent number of integers to do calculations. Followed by N numbers between each 2 number one of the operations & or | (The precedence of & and | are equal and both are left associative). All numbers x will be 0 <= x < 100.
Output
There should be T lines, containing the following format.
k. p1^a1 p2^a2 ..pi^ai…pn^an
Where k is the test case number (starting at 1), a single period, a single space and sequence of primes with their powers represent a final result where p1 12 | 6 & 15 means 22 * 31 | 21 * 31 & 31 * 51 that will be 22 * 31 & 31 * 51 that will be 22 * 31 * 51Sample
Input
2
3
12 | 6 & 15
3
12 & 6 | 15
Output
1. 2^2 3^1 5^1
2. 2^1 3^1 5^1
Sample Clarification:
hide comments
nitish rao:
2013-09-23 13:10:20
Whats the value for 0 | 0 ?? and How to print if answer is '0' or '1'? I was printing an empty line. Correct me if I am wrong. Last edit: 2013-09-23 13:10:41 |
|
Francky:
2012-10-11 21:27:28
I didn't test this problem, but I ever post a comment to say that this one belongs to tutorial. You don't have to delete those kind of comments. My opinion is clear regarding constraints and interest.
|
|
numerix:
2012-10-11 21:15:34
After several WAs I figured out that the contraints are wrong:
|
|
Ikhaduri:
2012-10-11 14:09:49
What should we print if answer for the query is 1 or 0? |
|
Xsquare:
2012-10-07 18:02:58
Its showing WA's again and again.. any tricky cases.. please tell?.. :( |
|
Problem Solver:
2012-10-07 17:05:36
Cool task ;) |
Added by: | Gareev |
Date: | 2012-10-06 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | LCPC 2012 |