Codeforces Round #803 (Div. 2)
04:14:26 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
C. Поликарпын шоо
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Поликарпад $d_{1}, d_{2}, ..., d_{n}$ гэсэн $n$ ширхэг шоо байдаг. $i$ дэхь шоо $1$-ээс $d_{i}$ хүртэлх тоонуудын аль нэгийг буулгах боломжтой. Поликарп бүх шоог хаясаны дараа буусан тоонуудын нийлбэр $A$-тай тэнцүү байсан. Агрипина аль шоо ямар тоо буулгасаныг хараагүй, харин зөвхөн нийлбэр $A$ болон шоонуудын хамгийн их тоонууд болох $d_{1}, d_{2}, ..., d_{n}$ эдгээрийг л мэднэ. Тэрээр энэ мэдээллүүдийг ашиглан $i$ дэхь шоо $r$ гэсэн тоог буулгасан байх боломжгүй гэдгийг олно. Жишээ нь: хэрвээ Поликарпад $2$ ширхэг 6-н талт шоо байсан бөгөөд шоонуудын буусан нийлбэр $A = 11$-тэй тэнцүү байсан бол Агрипина аль ч шоо $5$-аас доош хэмжээний тоог буулгах боломжгүй гэдгийг хэлж чадна (хэрэв аль нэг нь $5$-аас доош тоотой үлдсэн бол шоо хамгийн багадаа 7 гэсэн боломжгүй тоог буулгах ёстой болно).
Хэрвээ буусан бүх тоонуудын нийлбэр $A$ бол шоо болгон хэдэн ширхэг тоог буулгаж чадахгүйг олно уу.
Оролт
Эхний мөрөнд шоонуудын тоо ба нийт буусан тоонуудын нийлбэр болох 2 ширхэг бүхэл тоонууд $n, A$ $(1 ≤ n ≤ 2 \cdot 10^{5}, n ≤ A ≤ s)$ өгөгдөнө.
Хоёр дахь мөрөнд $i$ дэхь шооны буулгаж чадах хамгийн их тоонууд $d_{i}$-нүүд болох $n$ ширхэг бүхэл тоо $d_{1}, d_{2}, ..., d_{n}$ $(1 ≤ d_{i} ≤ 10^{6})$ өгөгдөнө.
Гаралт
$n$ ширхэг бүхэл тоо болох $b_{1}, b_{2}, ..., b_{n}$ дарааллыг хэвлэнэ үү. Энд $b_{i}$ нь $i$ дэхь шооны буулгаж чадахгүй тоонуудын тоо юм.
Орчуулсан: Энхлут
Жишээ тэстүүд
Оролт
2 8 4 4
Гаралт
3 3
Оролт
1 3 5
Гаралт
4
Оролт
2 3 2 3
Гаралт
0 1
Тэмдэглэл
Эхний жишээнд $A = 8$ бөгөөд энэ тохиолдолд $2$ шоо хоёул $4$ гэсэн тоог л буулгасан байх боломжтой. Тиймээс $2$ шоо $1$, $2$, эсвэл $3$ гэсэн тоонуудыг буулгасан байх боломжгүй.
Хоёр дахь жишээнд $A$ нь $3$-тай тэнцүү учир нэг шоо 3 гэсэн тоог буулгасан байх ганцхан боломжтой. Тиймээс шоо $1$, $2$, $3$ эсвэл $5$ гэсэн тоонуудыг буулгасан байх боломжгүй.
Гурав дахь жишээнд $A$ нь $3$-тай тэнцүү учир аль нэг шоо нь $1$-ийг харин үлдсэн шоо нь $2$-ыг буулгасан байх боломжтой. Тиймээс эхний шоо бүх тоог буулгасан байх боломжтой, харин $2$ дахь шоо $3$ гэсэн тоог буулгаж чадахгүй.