Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۹:عملی:سوال ۱۷

زیرمجموعه‌ی مجموعه‌ساز

مجموعه‌ی A={a1,a2,...,an} شامل n عدد طبیعی که در یک متغیر Integer جا می‌گیرند داده شده است. (n500) می‌خواهیم یک زیرمجموعه‌ی S={s1,s2,...,sk} از A را پیدا کنیم که:

  • S کم‌ترین تعداد عدد ممکن را داشته باشد.(k کمینه باشد.)
  • هر عدد مجموعه‌ی A را بتوان به صورت ترکیب خطی مثبت اعداد S نوشت. یعنی:

aAb1,b2,...,bkN{0},a=b1s1+b2s2+...+bksk

ورودی

در خط اول پرونده ورودی، n تعداد اعداد مجموعه‌ی A و در n سطر بعدی، در هر خط، یکی از اعداد مجموعه‌ی A نوشته شده است.

خروجی

در پرونده‌ی خروجی نیز مجموعه‌ی S را شبیه مجموعه‌ی A بنویسید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
10
463
470
306
367
487
452
96
20
275
15
3
15
20
96
17
781
596
220
484
639
451
229
620
922
598
210
707
983
642
159
284
82
9
82
159
210
220
229
284
484
596
642

ابزار صفحه