Hungarian mathematician Paul Erdos (1913–1996) demonstrated that from any set of p*q+1 positive integers we can select p+1 numbers that divide successively (x1|x2|...|xp|xp+1) or we can select q+1 numbers, so that any two of these numbers are not divisible with each other.
Task
Being given p*q+1 distinct positive integers, determine a subgroup of p+1 numbers which divide successively or a subgroup of q+1 numbers that are not divisible with each other.
Input Data
Input file erdos.in contains on the first line two positive integers p and q separated by a single space. The second line contains p*q+1 distinct positive integers each separated by a space. The numbers are given in ascending order.
Output Data
Output file erdos.out will contain on the first line the positive integer p or the positive integer q. If line one contains positive integer p, then line two contains p+1 positive integers of those that have the property that the first number divides the second, the second divides the third, and so on. If line one contains positive integer q, then line two contains q+1 positive integers with the property that any two numbers of the q+1 displayed are not divisible with each other. Numbers displayed on the same line will be separated by a single space and will be in ascending order.
Restrictions and Mentions
| erdos.in | erdos.out | Explanation |
|
3 4 |
4 9 12 15 33 35 |
Any two numbers of group {9 12 15 33 35} are not divisible with each other. |
| erdos.in | erdos.out | Explanation |
|
3 4 |
3 3 12 24 72 |
3|12|24|72 |
Time limit: 0.1 seconds/test
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com