{"problem":{"name":"D. Масштабирование изображений","description":{"content":"Дано чёрно-белое изображение, имеющее высоту H1 пикселей и ширину W1 пикселей. Требуется выполнить его масштабирование таким образом, чтобы результирующее изображение имело высоту H2 пикселей и ширину","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10126D"},"statements":[{"statement_type":"Markdown","content":"Дано чёрно-белое изображение, имеющее высоту H1 пикселей и ширину W1 пикселей. Требуется выполнить его масштабирование таким образом, чтобы результирующее изображение имело высоту H2 пикселей и ширину W2 пикселей. При этом возможны следующие варианты:\n\nНапишите программу, которая позволит масштабировать изображения по указанным правилам.\n\nПервая строка содержит целые числа H1 и W1 (1 ≤ H1, W1 ≤ 100) — соответственно высоту и ширину исходного изображения.\n\nСледующие H1 строк описывают исходное изображение. Каждая из них содержит W1 символов '0' или '1' — пиксели изображения.\n\nСледующая строка содержит целые числа H2 и W2 (1 ≤ H2, W2 ≤ 100) — размеры, которые должны быть получены после масштабирования.\n\nЕсли масштабирование возможно, выведите H2 строк, каждая из которых содержит W2 символов '0' или '1' — пиксели результирующего изображения.\n\nВ противном случае выведите текст ошибки.\n\n## Входные Данные\n\nПервая строка содержит целые числа H1 и W1 (1 ≤ H1, W1 ≤ 100) — соответственно высоту и ширину исходного изображения.Следующие H1 строк описывают исходное изображение. Каждая из них содержит W1 символов '0' или '1' — пиксели изображения.Следующая строка содержит целые числа H2 и W2 (1 ≤ H2, W2 ≤ 100) — размеры, которые должны быть получены после масштабирования.\n\n## Выходные Данные\n\nЕсли масштабирование возможно, выведите H2 строк, каждая из которых содержит W2 символов '0' или '1' — пиксели результирующего изображения.В противном случае выведите текст ошибки.\n\n## Примеры\n\nВходные данные2 30011014 6Выходные данные000011000011110011110011Входные данные4 60000110010111100111100112 3Выходные данныеBad image\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of functions.  \nLet $ a = (a_1, a_2, \\dots, a_n) \\in \\{0, 1, \\dots, n\\}^n $ be the direct dependency array, where $ a_i $ is the function that function $ i $ directly depends on, and $ a_i = 0 $ means no direct dependency.  \n\nDefine a directed graph $ G = (V, E) $ where:  \n- $ V = \\{1, 2, \\dots, n\\} $ is the set of functions.  \n- $ E = \\{(a_i, i) \\mid a_i \\ne 0\\} $ is the set of directed edges (from dependency to dependent).  \n\nGiven: $ G $ is a forest of trees (no cycles, each node has at most one parent).  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 0 \\le a_i \\le n $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. If $ a_i \\ne 0 $, then there is no path from $ a_i $ to $ i $ in the reverse direction (no cycles).  \n\n**Objective**  \nFor each function $ i $, define its price $ p_i $ as:  \n$$\np_i = 1 + \\text{number of functions that depend on } i \\text{ (directly or indirectly)}\n$$  \nThat is, $ p_i = 1 + |\\{ j \\mid \\text{there is a path from } i \\text{ to } j \\text{ in } G \\}| $.  \n\nFind:  \n$$\n\\arg\\max_{i \\in \\{1, \\dots, n\\}} p_i\n$$  \nOutput any pair $ (i, p_i) $ achieving the maximum price.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10126D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}