Унгарският математик Пол Ердьош (1913–1996) е доказал, че от всяко множество от p*q+1 цели положителни числа могат да се изберат p+1 числа, всяко от които дели следващото (x1|x2|...|xp|xp+1) или q+1 числа, такива, че които и две от избраните числа да вземем, никое от тях няма да се дели на другото.
Задача
По дадени p*q+1 на брой различни цели положителни числа, да се намери подмножество от p+1 числа, които се делят последователно едно на друго или пък подмножество от q+1 числа, никое от които не е делител на друго.
Вход
Входния файл erdos.in съдържа на първия ред две цели положителни числа p и q, разделени с един интервал. Втория ред съдържа p*q+1 различни цели положителни числа, разделени с интервали. Числата са дадени в растящ ред.
Изход
Изходния файл erdos.out трябва да съдържа на първия ред числото p или числото q. Ако на първият ред е записано числото p, на втория ред трябва да има p+1 числа, избрани от дадените числа, така, че първото число е дели второто, второто дели третото и т.н. Ако на първия ред е записано числото q, тогава на вторият ред трябва да има q+1 числа от дадените, със свойството, че никое от тях не се дели на някое друго. Числата в реда трябва да бъдат в растящ ред и да са разделени с интервали.
Ограничения и пояснения
Примери
erdos.in |
erdos.out |
Обяснение |
3 4 |
4 |
Никое число от множеството {9 12 15 33 35} не се дели на друго число от това множество. |
erdos.in |
erdos.out |
Обяснение |
3 4 |
3 |
3|12|24|72 |
Ограничение
за време: 0.2
секунди на
тест
prof. Emanuela
Cerchez
"Grigore Moisil"
Iaşi IT High School
Contact:emanuela.cerchez@gmail.com
Превод
на български:
Стоян Капралов