FRACTAN - Fractan
f1, f2, ..., fk
of fractions and starting integer N
, you repeatedly multiply the integer you have at any stage (initially N
) by the earliest fi
in the list for which the answer is integral.
Whenever there is no such fi
, the game stops.
Formally, we define a sequence by S0=N
, and Sj+1=fiSj
, if for 1<=i<=k
, the number fiSj
is an integer but the numbers f1Sj, ..., fi-1Sj
are not.
For example, if we have the list of eight fractions f1=170/39
, f2=19/13
, f3=13/17
, f4=69/95
, f5=19/23
, f6=1/19
, f7=13/7
, f8=1/3
, and start with N=21
, we produce the (finite) sequence (21,39,170,130,190,138,114,6,2)
.
In general, the sequence may be infinite.
Given a fraction list and a starting integer calculate a part of the defined sequence.
Actually, we are interested only in the powers of 2
that appear in the sequence.
Input Specification
The input contains several test cases.
Every test case starts with three integers m, N, k
.
You may assume that 1<=m<=40
, 1<=N<=1000
, and 1<=k<=100
.
Then follow k
fractions f1, ..., fk
.
For each fraction, first its numerator is given, followed by its denominator.
You may assume that both are positive integers less than 1000
and their greatest common divisor is 1
.
The last test case is followed by a zero.
Output Specification
For each test case output on a line m
numbers e1, ..., em
, separated by one space character, such that 2e1, ..., 2ek
are the first m
numbers in the defined sequence that are powers of 2
.
You may assume that there are at least m
powers of 2
among the first 7654321 elements of the sequence.
Sample Input
1 21 8 170 39 19 13 13 17 69 95 19 23 1 19 13 7 1 3 20 2 14 17 91 78 85 19 51 23 38 29 33 77 29 95 23 77 19 1 17 11 13 13 11 15 2 1 7 55 1 0
Sample Output
1 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
hide comments
David:
2022-06-10 16:42:16
No Java solutions either. :-(
|
|
.::Manish Kumar::.:
2010-06-26 13:55:03
as u can see till now there is no python submission accepted , plz increase time limit for python programmers. |
Added by: | Wanderley Guimarăes |
Date: | 2007-09-19 |
Time limit: | 0.303s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | University of Ulm Local Contest 2004 |