Codeforces Round #803 (Div. 2)
05:22:44 |
Codeforces Round #804 (Div. 2)
7 өдрийн дараа |
C. Таны гаргаж чадах утгууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Пари Аря-аас нэгэн үнэтэй шоколад худалдан авахыг хүсжээ. Түүнд $n$ ширхэг зоос байгаа бөгөөд $i$-дахь зоос нь $c_{i}$ үнэтэй байв. Түүний худалдан авахыг хүсэж буй шоколадны үнэ нь $k$ ба иймд тэрээр өөрт байгаа зооснуудаас нийлбэр утга нь $k$ байх зооснуудын дэд олонлог сонгон авах бөгөөд үүнийгээ Аря-д өгөх юм.
Ийм байх зооснуудын хайж байхдаа түүний толгойд дараах бодол орж иржээ: эдгээр зооснуудыг Аря-д өгсний дараа Аря эдгээр зооснуудыг ашиглан ямар утгууд гарган авч болохыг тэрээр боджээ. Пари хувь хүний хувьд бага зэрэг атаархуу нэгэн учраас Аря-г тэдгээр зооснуудыг ашиглан олон утга гаргаж чадахгүй байхыг хүсэж байв. Иймд тэрээр Аря нийлбэр утга нь $k$ байх зооснуудын дэд олонлогийг ашиглан гаргаж чадах бүх $x$-ын утгуудыг мэдэхийг хүсжээ.
Илүү дэлгэрэнгүй хэлбэл, Пари өөрт байх зооснуудын нийлбэр утга нь $k$ байх зооснуудын дэд олонлогуудын хувьд тухайн дэд олонлогийн ямар нэгэн дэд олонлогийн нийлбэр утга $x$-ын бүх боломжит утгыг мэдэхийг хүсэж байв. Өөрөөр хэлбэл бид ямар нэгэн байдлаар шоколадыг худалдан авахад Аря тэдгээр зооснуудыг ашиглан $x$ гэсэн нийлбэр утгыг гаргаж чадаж байх юм.
Оролт
Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n, k ≤ 500$) өгөгдөх ба эдгээр нь харгалзан зооснуудын тоо болох шоколадны үнийг илэрхийлэх юм.
Дараагийн мөрөнд бүхэл тоонууд $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{i} ≤ 500$) өгөгдөх ба эдгээр нь Пари-д байгаа зооснуудын үнийг илэрхийлнэ.
Түүнчлэн эдгээр зооснуудыг ашиглан $k$ гэсэн утгыг гаргаж чадах юм. Өөрөөр хэлбэл ямар ч тохиолдолд шоколадыг худалдан авах зам байна гэсэн үг юм.
Гаралт
Гаралтын эхний мөрөнд ганц бүхэл тоо $q$-г хэвлэх ба энэ нь бүх боломжит $x$-ын утгуудын тоог илэрхийлнэ. Дараа нь $q$ ширхэг бүхэл тоонуудыг өсөх дарааллаар хэвлэх ба эдгээр нь Пари-ын шоколад худалдан авах гэж төлсөн зооснуудыг ашиглан Аря-ын гаргаж чадах утгуудыг илэрхийлэх юм.
Орчуулсан: Баатархүү
Жишээ тэстүүд
Оролт
6 18 5 6 1 10 12 2
Гаралт
16 0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18
Оролт
3 50 25 25 50
Гаралт
3 0 25 50