Начало
СоревнованияПодразделы
Другие разделы
Дата и время
16/11/2024 15:19:59
Задачи очного тура личного первенства Южного Урала 2005
1. Налогообложение
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (1) |
| 11/11/2023 | Марафон 80 задач, 4 этап (B) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Известно, что все люди платят налоги со своих доходов. Государство решило предоставить гибкую систему
уплаты налогов и предложило для использования на выбор несколько налоговых ставок.
Налоговая ставка складывается из фиксированной части (суммы, которую налогоплательщик обязан уплатить
по истечении налогового периода) и процентной части (суммы, составляющей некоторый процент от доходов налогоплательщика).
Налоговые органы заинтересовались конкретной налоговой ставкой. Им хочется знать, есть ли такой уровень доходов,
при котором данная налоговая ставка будет самой выгодной, то есть существует ли диапазон доходов от `A` до `B`
(`0\ ≤\ A\ <\ B`), в котором налогоплательщик будет платить по этой налоговой ставке меньше, чем по другим.
Напишите программу, выполняющую этот расчет.
В первой строке входного файла содержится одно целое число – количество тестов `T`.
Далее для каждого теста идет ровно три строки. Первая строка каждого теста содержит два целых числа `N` `M` (`1\ <\ N\ ≤\ 50`,
`0\ ≤\ M\ ≤\ N-1`), `N` – общее количество налоговых ставок, `M` – индекс интересующей налоговиков ставки.
На второй строке указаны `N` целых чисел, разделенных пробелами – фиксированные части налоговых ставок (от 0 до 10000).
На третьей строке указаны `N` целых чисел – процентные части (от 0 до 100).
В выходной файл для каждого теста на отдельной строке вывести искомый диапазон в виде двух чисел `А` `В` через пробел с
точностью 8 знаков после запятой.
Если значение `B` равно бесконечности, вместо числа вывести слово INF.
Если такого диапазона нет, то вывести на строке сообщение "NOT EXISTS".
Пример ввода
3 3 0 10 5 3 0 10 20 5 3 6000 435 3325 2345 0 0 45 33 13 100 4 0 1 0 0 0 9 6 7 8
Пример вывода
50.00000000 INF 5968.75000000 28115.38461538 NOT EXISTS
2. Закодированное изображение
Модулярная арифметикаМатрицы
Олимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (2) |
| 04/11/2023 | Марафон 80 задач, 3 этап (E) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Со шпионской телекамеры поступает закодированное черно-белое изображение.
Каждый кадр поступает в виде квадратной матрицы `A` размером `N\ times\ N`, состоящей только из 0 и 1.
Для расшифровки кадра нужно возвести матрицу в cтепень `K` и заменить в результирующей матрице четные значения единицами,
а нечетные нулями.
Во входном файле в первой строке содержится два целых числа `N` и `K` (`1\ <\ N\ ≤\ 50`, `0\ ≤\ K\ <\ 10^9`).
Далее следует `N` строк, содержащих по `N` символов 0 и 1 – значение матрицы `A`.
В выходной файл вывести декодированное изображение как матрицу размером `N\ times\ N` из 0 и 1.
Пример ввода
2 3 01 11
Пример вывода
01 10
3. Дробь
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (3) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу, которая находит представление дроби `m/n` в форме `(p^3+q^3)/(r^3+s^3)`.
В первой строке входного файла содержатся целых числа `m` и `n`, разделенные пробелом (`1\ ≤\ m\ ≤\ 1000`, `1\ ≤\ n\ ≤\ 1000`).
В выходной файл вывести четыре целых числа `p` `q` `r` `s`, разделяя их пробелом. Если существует несколько решений,
вывести одно из них.
Пример ввода
1 8
Пример вывода
1 1 2 2
4. Эльфы
Вычислительная геометрияГенерация всех подмножеств, сочетаний, перестановок
Олимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (4) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
У каждого эльфа есть свое любимое растение, которое он высаживает на подконтрольной ему территории леса.
Например, эльф с именем Шиповник везде сажает шиповник, а эльф Малина – малину. Территория каждого эльфа представляет
собой выпуклый многоугольник, у которого соседние ребра не коллинеарны.
Подконтрольные территории эльфов могут пересекаться.
Напишите программу для подсчета площади леса с наиболее разнообразной флорой.
На первой строке входного файла дано количество эльфов `N` (`0\ <\ N\ ≤\ 10`). Далее каждая следующая строка
описывает территорию `i`-го эльфа. Каждое описание участка начинается с количества вершин многоугольника `M`
(`3\ ≤\ M\ ≤\ 10`), далее следует `M` пар целых чисел `X` `Y` (`-10000\ <\ X,\ Y\ <\ 10000`), представляющих собой координаты
вершин многоугольника в порядке обхода вершин по часовой стрелке.
В выходной файл вывести общую площадь участков леса, засаженных наибольшим количеством различных эльфийских растений
с точностью 3 знака после запятой.
Пример ввода
2 4 0 0 0 10 10 10 10 0 4 0 0 5 5 10 0 5 -5
Пример вывода
25.000
5. Фибоначчиева система счисления
Специальные системы счисленияОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (5) |
| 03/03/2015 | Занятие 15 (E) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:
`F_0=0`, `F_1=1`, `F_n=F_{n-1}+F_{n-2}` для `n>1`.
Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей,
что любое целое положительное число имеет единственное представление вида
`N=F_{k_1}+F_{k_2}+…+F_{k_r}`, где `F_{k_i}` – число Фибоначчи, а `k_1\ ">>"\ k_2\ ">>"\ …\ ">>"\ k_r\ ">>"\ 0`.
Здесь `i\ ">>"\ j` означает, что `i\ ≥\ j+2`. Целое неотрицательное число можно записать в виде последовательности нулей
и единиц:
`N=(b_m\ b_{m-1}…b_2)_F\ hArr\ N\ =\ sum_{i=2}^m\ b_i*F_i`, где `b_i\ =\ 1`,
если `F_i` входит в преставление, иначе 0.
Например, `1000000` = `832040\ +\ 121393\ +\ 46368\ +\ 144\ +\ 55` = `F_30\ +\ F_26\ +\ F_24\ +\ F_12\ +\ F_10` или `(1000000)_10\ =\ (10001010000000000010100000000)_F`.
Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются
две 1 подряд.
Напишите программу, которая вводит числа в десятичной системе счисления и выводит их в ФСС.
Во входном файле в первой строке содержится число `T` (`0\ <\ T\ <\ 100`) – количество тестов.
Каждый тест распологается на своей строке, он состоит из одного числа `N` (`0\ <\ N\ <\ 10^100`), записанного в десятичной
системе счисления.
В выходной файл для каждого введенного числа вывести его представление в Фибоначчиевой системе счисления.
Число обязательно должно начинаться с 1.
Пример ввода
3 1 100 1000
Пример вывода
1 1000010100 100000000100000
6. Игра
Обход дерева игры, α-β процедураОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (6) |
| 29/04/2013 | Занятие 26 (D) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Макси и Мини играют в следующую игру. Квадратный лист бумаги разделяется линиями на `N\ times\ N` клеток,
и в каждой клетке записывается целое число от –100 до 100. Игроки ходят по очереди.
Каждый игрок может либо взять себе весь оставшийся прямоугольник, либо разрезать его по вертикальной или
горизонтальной линии на два прямоугольника и взять себе любую из частей.
Игра заканчивается, когда игрок при очередном ходе забирает себе всю оставшуюся фигуру.
По окончании игры подсчитывается сумма чисел на взятых игроками частях. Побеждает тот игрок, у которого сумма больше.
Напишите программу, которая по значениям в клетках в начале игры определит
максимальный перевес первого игрока над вторым, если оба играют максимально прибыльно для себя.
В первой строке входного файла содежится число `T` (`0\ <\ T\ ≤\ 10`) – количество тестов в файле.
Каждый тест состоит из набора строк. В первой строке содержится целое число `N` (`0\ <\ N\ ≤\ 10`) – размер поля,
затем следует `N` строк, в каждой содержится `N` целых чисел `A_{ij}` (`-100\ ≤\ A_{ij}\ ≤\ 100`), разделенных
пробелами – числа, записанные в соответствующих клетках.
Для каждого теста вывести на соответствующей строке максимальный перевес первого игрока над вторым по окончании игры,
если оба играют максимально прибыльно для себя.
Пример ввода
2 3 1 1 1 1 1 1 1 1 1 2 -10 1 1 1
Пример вывода
9 -7
7. Задача электрика
Грамматики, рекурсивный разборОлимпиадные задачи на русском языке
| 15/10/2005 | Личное первенство Южного Урала (7) |
| 12/05/2012 | Занятие 18 (C) |
| 28/04/2015 | Занятие 23 (B) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Электрику необходимо рассчитать сопротивление электрической цепи, состоящей из резисторов.
Электрик вводит информацию о цепи в следущей форме. Параллельные участки цепи он заключает в квадратные
скобки [], а последовательные – в круглые (), сопротивление резисторов записывает в виде
целых чисел от 1 до 1000. Для разделения элементов описания он использует пробелы. Например, запись [10 20 30]
означает, что три резистора сопротивлением 10, 20 и 30 Ом соединены параллельно.
Напишите программу для расчета общего сопротивления цепи.
В первой строке входного файла содержится целое число `T` (`0\ <\ T\ ≤\ 10`) – число тестов в файле, на каждой из `T`
последующих строк записана одна цепь в указанной форме. Описание цепей корректно, то есть скобки соответствуют
друг другу, в скобках есть как минимум одно сопротивление. Длина строки описания не превышает 100 символов.
Для каждой цепи из входного файла на соответствующей строке вывести общее сопротивление цепи с точностью 3 знака после запятой.
Пример ввода
3 [10 20 30] (10 20 30) [10 (20 30) 40]
Пример вывода
5.455 60.000 6.897
8. Auto Loan
Решение уравнений (дихотомия, метод Ньютона)Олимпиадные задачи на английском языке
| 15/10/2005 | Личное первенство Южного Урала (8) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Auto dealerships frequently advertise tempting loan offers in order to make it easier for people to afford
the "car of their dreams". A typical sales tactic is to show you various cars, and then talk in terms of what
your monthly payment would be, to say nothing of how much you are actually paying for the car, how much interest
you pay, or how long you have to make payments.
A typical auto loan is calculated using a fixed interest rate, and is set up so that you make the same
monthly payment for a set period of time in order to fully pay off the balance. The balance of your loan starts out
as the sticker price of the car. Each month, the monthly interest is added to your balance, and the amount of
your payment is subtracted from your balance. (The payment is subtracted after the interest is added.)
The monthly interest rate is 1/12 of the yearly interest rate. Thus, if your annual percentage rate
is 12%, then 1% of the remaining balance would be charged as interest each month.
You have been checking out some of the cars at your local dealership, TopAuto.
An excited salesman has just approached you, shouting about how you can have the car you are looking at
for a payment of only monthlyPayment for only loanTerm months! You are to find the annual
percentage rate of the loan, assuming that the initial balance of the loan is given.
Notes
- Because of the way interest is compounded monthly, the actual interest accrued over the course of a year is not necessarily the same as (balance * yearly interest rate). In fact, it's usually more.
- In a real situation, information like this would typically need to be disclosed, but since you aren't at a point of signing any paperwork, the salesman has no legal obligation to tell you anything.
- The answer value must be within `10^{-9}` absolute or relative error of the actual result.
Constraints:
- price will be between 1 and 1000000, inclusive.
- monthly payment will be between 0 and price / 2, inclusive.
- loan term will be between 1 and 600, inclusive.
- the resulting interest rate will be between 0 and 100, inclusive.
First line of input file contains `N` – number of autoloans. Then there are `N` lines, each of these define
one situation by three values `A` `B` `C`, separated by spaces. `A` – floating point price of car, `B` – floating
point monthly payment, `C` – integer loan term (in months).
For each situation you have to output file one line, contained number of percent to 8 digit after dot.
Sample Input
3 6800 100 68 2000 510 4 15000 364 48
Sample Output
0.00000000 9.56205462 7.68785639
9. Prime Polynom
Простые числа, разложение на множителиПолный перебор
Олимпиадные задачи на английском языке
| 15/10/2005 | Личное первенство Южного Урала (9) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.
The first prime numbers are 2, 3, 5, 7, 11, 13, 17, … It is known that no non-constant polynomial function `P(n)`
exists that evaluates to a prime number for all integers `n`. But there are some famous quadratic polynomials
that are prime for all non-negative integers less than `M` (`M` depends on the polynomial).
You will be given integers `A`, `B` and `C`. You should find the smallest non-negative integer `M` such
that `A*M^2\ +\ B*M\ +\ C` is not a prime number.
Constraints
- A will be between 1 and 10000, inclusive.
- B will be between –10000 and 10000, inclusive.
- C will be between –10000 and 10000, inclusive.
Input contains `N` – number of polynoms, followed by `N` lines, each of these define one polynom by
three integers `A` `B` `C`, separated by space character.
For each polynom output smallest non-negative integer `M` such that `A*M^2\ +\ B*M\ +\ C` is not a prime number.
Sample Input
5 1 -1 41 1 1 41 1 1 -13 1 -15 97 1 -79 1601
Sample Output
41 40 0 48 80
