{"problem":{"name":"D. Американские горки","description":{"content":"Аттракцион «Американские горки» представляет собой рельсовый трек, размещенный на опорах. Известна высота каждой опоры. Для рекламы аттракциона необходимо выделить один из его фрагментов (несколько по","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFD"},"statements":[{"statement_type":"Markdown","content":"Аттракцион «Американские горки» представляет собой рельсовый трек, размещенный на опорах. Известна высота каждой опоры. Для рекламы аттракциона необходимо выделить один из его фрагментов (несколько подряд идущих опор с рельсовым треком) световой подсветкой. При этом необходимо выделить такой фрагмент трека, на котором была бы «горка», т.е. на выделенном участке трека была бы точка, которая находилась бы строго выше начала и строго выше конца выделенного фрагмента трека.\n\nВладелец аттракциона для экономии хочет найти подходящий участок минимальной длины, удовлетворяющий условию наличию «горки» на этом участке.\n\nПервая строка входных данных содержит число $N$ — количество опор аттракциона. Следующие $N$ строк содержат информацию о высотах опор при движении от начала к концу аттракциона. Все числа натуральные и не превосходящие $10^5$.\n\nПрограмма должна вывести два числа — номер первой и последней подходящей опоры. Опоры нумеруются числами от $1$ до $N$. Если фрагмента, удовлетворяющего условиям, не существует, программа должна вывести одно число 0. Если подходящих ответов несколько, нужно вывести любой из них.\n\nРешение, правильно работающее только для случав, когда все исходные числа не превосходят 100, будет оцениваться в 40 баллов. В 100 баллов будет оцениваться решение, правильно работающее, когда все числа не превосходят $10^5$.\n\nПояснение к первому примеру. Дано 7 опор с высотами 18, 10, 15, 20, 20, 20, 1, 3. Самый короткий участок, содержащий «горку» — это 15, 20, 20, 10. Он начинается опорой номер 3 и заканчивается опорой номер 6.\n\nПояснение ко второму примеру. Высоты опор убывают, поэтому участка с «горкой» нет.\n\n## Входные Данные\n\nПервая строка входных данных содержит число $N$ — количество опор аттракциона. Следующие $N$ строк содержат информацию о высотах опор при движении от начала к концу аттракциона. Все числа натуральные и не превосходящие $10^5$.\n\n## Выходные Данные\n\nПрограмма должна вывести два числа — номер первой и последней подходящей опоры. Опоры нумеруются числами от $1$ до $N$. Если фрагмента, удовлетворяющего условиям, не существует, программа должна вывести одно число 0. Если подходящих ответов несколько, нужно вывести любой из них.\n\n## Примеры\n\nВходные данные7\n18\n10\n15\n20\n20\n10\n3\nВыходные данные3\n6\nВходные данные3\n9\n8\n5\nВыходные данные0\n\n## Примечание\n\nПояснение к первому примеру. Дано 7 опор с высотами 18, 10, 15, 20, 20, 20, 1, 3. Самый короткий участок, содержащий «горку» — это 15, 20, 20, 10. Он начинается опорой номер 3 и заканчивается опорой номер 6.Пояснение ко второму примеру. Высоты опор убывают, поэтому участка с «горкой» нет.\n\n## Система Оценки\n\nРешение, правильно работающее только для случав, когда все исходные числа не превосходят 100, будет оцениваться в 40 баллов. В 100 баллов будет оцениваться решение, правильно работающее, когда все числа не превосходят $10^5$.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"给定一个大小为 #cf_span[M * N] 的矩阵 #cf_span[A]，其中 #cf_span[0 ≤ Aij < K]。行编号从 1 到 #cf_span[M]，列编号从 1 到 #cf_span[N]。\\n\\n你可以执行两种操作：\\n\\n第一行包含三个整数 #cf_span[M]、#cf_span[N] 和 #cf_span[K]（#cf_span[1 ≤ M, N ≤ 1000]，#cf_span[1 ≤ K ≤ 109]）。\\n\\n接下来的 #cf_span[M] 行描述矩阵。每行包含 #cf_span[N] 个数 #cf_span[Aij]（#cf_span[0 ≤ Aij < K]）。\\n\\n第一行输出最小操作次数。\\n\\n在下一行，输出 #cf_span[M] 个数，表示对每一行（从第一行开始）应用的操作次数。\\n\\n在再下一行，输出 #cf_span[N] 个数，表示对每一列（从第一列开始）应用的操作次数。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含三个整数 #cf_span[M]、#cf_span[N] 和 #cf_span[K]（#cf_span[1 ≤ M, N ≤ 1000]，#cf_span[1 ≤ K ≤ 109]）。接下来的 #cf_span[M] 行描述矩阵。每行包含 #cf_span[N] 个数 #cf_span[Aij]（#cf_span[0 ≤ Aij < K]）。\"},{\"iden\":\"output\",\"content\":\"第一行输出最小操作次数。在下一行，输出 #cf_span[M] 个数，表示对每一行（从第一行开始）应用的操作次数。在再下一行，输出 #cf_span[N] 个数，表示对每一列（从第一列开始）应用的操作次数。\"},{\"iden\":\"examples\",\"content\":\"输入\\n3 3 2\\n0 0 0\\n1 1 1\\n1 1 1\\n输出\\n2\\n0 1 1\\n0 0 0 \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ M, N, K \\in \\mathbb{Z}^+ $ with $ 1 \\leq M, N \\leq 1000 $, $ 1 \\leq K \\leq 10^9 $.  \nLet $ A \\in \\{0, 1, \\dots, K-1\\}^{M \\times N} $ be the given matrix.\n\nLet $ r_i \\in \\mathbb{Z}_{\\geq 0} $ denote the number of row operations applied to row $ i \\in \\{1, \\dots, M\\} $.  \nLet $ c_j \\in \\mathbb{Z}_{\\geq 0} $ denote the number of column operations applied to column $ j \\in \\{1, \\dots, N\\} $.\n\nEach row operation on row $ i $ increments all elements $ A_{i,j} $ modulo $ K $.  \nEach column operation on column $ j $ increments all elements $ A_{i,j} $ modulo $ K $.\n\n**Constraints**  \nFor all $ i \\in \\{1, \\dots, M\\} $, $ j \\in \\{1, \\dots, N\\} $:  \n$$\n(A_{i,j} + r_i + c_j) \\bmod K = 0\n$$\n\n**Objective**  \nMinimize the total number of operations:  \n$$\n\\min \\sum_{i=1}^M r_i + \\sum_{j=1}^N c_j\n$$  \nsubject to the above constraints.  \n\nOutput the minimal total, followed by vectors $ (r_1, \\dots, r_M) $ and $ (c_1, \\dots, c_N) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFD","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}