{"problem":{"name":"D. Тыквенная магия","description":{"content":"Маг Чариотис занимается выращиванием тыкв. Размер тыквы определяется целым числом (объёмом в кубических метрах). У мага есть три заклинания: первое увеличивает размер любой тыквы *на* $p$, второе уве","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10218D"},"statements":[{"statement_type":"Markdown","content":"Маг Чариотис занимается выращиванием тыкв. Размер тыквы определяется целым числом (объёмом в кубических метрах).\n\nУ мага есть три заклинания: первое увеличивает размер любой тыквы *на* $p$, второе увеличивает размер любой тыквы *в* $k$ раз, а третье превращает тыкву размера ровно $m$ в карету (на тыквы других размеров оно не оказывает никакого влияния).\n\nИзначально у мага есть $n$ тыкв и он планирует сделать как можно больше карет. Чтобы не колдовать попусту, ему хочется узнать, из каких тыкв возможно получить кареты, пользуясь только заклинаниями.\n\nВ первой строке записаны четыре целых числа: $n$, $p$, $k$, $m$ ($1 <= n <= 10^5$, $1 <= p <= 10^7$, $2 <= k <= 10^7$, $1 <= m <= 10^7$).\n\nВо второй строке записаны $n$ целых чисел $a_i$ – начальные размеры тыкв, имеющихся у мага ($1 <= a_i <= 10^7$).\n\nВыведите $n$ чисел, каждое из которых равно либо $0$, либо $1$. При этом, если из $i$-й тыквы можно получить карету, $i$-e число должно быть равно $1$, а если нельзя – то равняться $0$.\n\n## Входные Данные\n\nВ первой строке записаны четыре целых числа: $n$, $p$, $k$, $m$ ($1 <= n <= 10^5$, $1 <= p <= 10^7$, $2 <= k <= 10^7$, $1 <= m <= 10^7$).Во второй строке записаны $n$ целых чисел $a_i$ – начальные размеры тыкв, имеющихся у мага ($1 <= a_i <= 10^7$).\n\n## Выходные Данные\n\nВыведите $n$ чисел, каждое из которых равно либо $0$, либо $1$. При этом, если из $i$-й тыквы можно получить карету, $i$-e число должно быть равно $1$, а если нельзя – то равняться $0$.\n\n## Примеры\n\nВходные данные1 3 2 7\n2\nВыходные данные1 Входные данные9 2 4 8\n1 2 3 4 5 6 7 8 9\nВыходные данные1 1 0 1 0 1 0 1 0 \n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the required total duration of the song.  \nLet $ A \\in \\mathbb{Z} $ be the duration of the chorus.  \nLet $ B \\in \\mathbb{Z} $ be the duration of each verse.  \nLet $ N \\in \\mathbb{Z}_{\\geq 0} $ be the number of interludes.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the sequence of interlude durations, where $ s_i \\in \\mathbb{Z} $ and $ 1 \\leq s_i \\leq 500 $.  \n\nLet $ x \\in \\mathbb{Z}_{\\geq 0} $ be the number of verses to be composed.  \nLet $ y \\in \\mathbb{Z}_{\\geq 0} $ be the number of times the chorus is repeated.  \nLet $ z \\subseteq \\{1, 2, \\dots, N\\} $ be a subset of interludes used (possibly empty).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^{18} $  \n2. $ 1 \\leq A, B \\leq 500 $  \n3. $ 0 \\leq N \\leq 500 $  \n4. $ 1 \\leq s_i \\leq 500 $ for all $ i \\in \\{1, \\dots, N\\} $  \n5. The song structure must alternate between chorus and verse, starting and ending with chorus:  \n   $$\n   \\text{Structure: } \\underbrace{A,\\, \\text{interlude?},\\, B,\\, \\text{interlude?},\\, A,\\, \\dots,\\, A}_{\\text{starts and ends with } A}\n   $$  \n   Hence, if there are $ x $ verses, there must be exactly $ x + 1 $ choruses.  \n6. The total duration is:  \n   $$\n   T = (x + 1) \\cdot A + x \\cdot B + \\sum_{i \\in z} s_i\n   $$  \n7. The subset $ z $ of interludes used must satisfy $ |z| \\leq N $, and each $ s_i $ may be used at most once.  \n\n**Objective**  \nFind the minimum $ x \\in \\mathbb{Z}_{\\geq 0} $ such that there exists a subset $ z \\subseteq \\{1, \\dots, N\\} $ with:  \n$$\n(x + 1) \\cdot A + x \\cdot B + \\sum_{i \\in z} s_i = T\n$$  \nIf no such $ x $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10218D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}