Начало
СоревнованияПодразделы
Другие разделы
Дата и время
26/04/2024 19:26:09
Задачи Южно-Уральского командного чемпионата 2005
1. НЛО
Вычислительная геометрияПолный перебор
Поворот, увеличение и другие способы выявления особых точек
Олимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (1) |
| 04/05/2011 | Занятие 24 (F) |
| 18/03/2013 | Занятие 20 (G) |
| 25/11/2015 | Занятие по темам "Cканирование, выявление особых точек" (A) |
| 11/11/2023 | Геометрия (проводит BOGAT) (B) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
На поле фермера Джона приземлилось несколько летающих тарелок. Фермер хочет уничтожить
оккупантов с помощью дезинтегратора, собранного его сыном для школьной научной выставки, но так как конструкция
экспериментальная, можно сделать только один выстрел. Луч дезинтегратора распространяется по прямой и может уничтожить все
тарелки на своем пути, достаточно всего лишь касания. Все тарелки имеют одинаковый размер, не пересекаются и не выходят
за границу поля.
Какое максимальное количество НЛО сможет уничтожить фермер единственным выстрелом, если он может выбрать с какой точки
на краю поля стрелять и в каком направлении?
В первой строке входного файла содержится два целых числа, разделенных пробелом – количество НЛО `N` (`1\ ≤\ N\ ≤\ 100`)
и радиус НЛО `R` (`1\ ≤\ R\ ≤\ 100`). Далее следует `N` строк, в каждой строке содержится два целых числа, разделенных
пробелом – координаты центра `i`-го НЛО `X_i,\ Y_i` в диапазоне от `R` до `1000-R`. Координаты левого нижнего угла
поля – (0,0), а правого верхнего – (1000,1000).
В выходной файл вывести одно целое число – максимальное количество тарелок, уничтожаемых одним выстрелом.
Пример ввода
4 20 100 500 400 400 600 350 500 800
Пример вывода
3
2. Формула, где формула?
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (2) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Даны три целых числа `A`, `B` и `C` в диапазоне от 1 до 100. Напишите программу, которая находит
такое целое число `X` в диапазоне от 1 до `10^9`, чтобы значение выражения `(A^2*B^2+X)*(A^2*C^2+X)*(B^2*C^2+X)`
было квадратом некоторого целого числа.
В первой строке входного файла содержится три целых числа `A`, `B`, `C`, разделенных пробелами.
В первой строке выходного файла вывести одно целое – искомое число `X`. Можно вывести любой вариант.
Пример ввода 1
1 1 5
Пример вывода 1
3
Пример ввода 2
2 3 5
Пример вывода 2
300
3. Поднос
Вычислительная геометрияОлимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (3) |
| 11/11/2023 | Геометрия (проводит BOGAT) (F) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В столовой решили приобрести новые подносы круглой формы. Для уменьшения стоимости
было решено сделать подносы как можно более маленького размера. Обеды в столовой всегда комплексные: первое,
второе и третье. Для каждого блюда используется определенная тарелка (суп может быть разным, но
всегда используется суповая тарелка фиксированного диаметра).
Напишите программу, которая определяет минимальный диаметр подноса. Тарелки на подносе могут соприкасаться,
но не должны накладываться друг на друга или вылезать за края подноса.
Во входном файле в первой строке содержится три вещественных числа, разделенных пробелами в диапазоне от 5 до 50 – диаметры тарелок
для первого, второго и третьего блюда.
В первой строке выходного файла вывести одно вещественное число – минимальный диаметр подноса с точностью `10^{-4}`.
Пример ввода
22.2 15.0 12.5
Пример вывода
37.2740
4. Дом тысячи дверей
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (4) |
| 22/11/2008 | Занятие 9 (F) |
| 17/11/2012 | Занятие 10 (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В доме-лабиринте все комнаты имеют квадратную форму, в каждой стене комнаты по одной двери,
ведущей либо в соседнюю комнату, либо наружу. Но все двери в доме имеют ручку только с одной стороны,
и с той стороны, где нет ручки, дверь открыть нельзя. Двери на плане обозначены символами '>' (больше),
'<' (меньше), 'v' (строчная латинская буква вэ),
'^' (крышечка). Направление уголка соответствует направлению, в котором можно проходить дверь.
В доме спрятано от 1 до 5 золотых монет, обозначенных на плане символом '$' (доллар).
Текущая позиция обозначена символом '*' (звездочка). Символ '.' (точка) обозначает пустую комнату.
Символ '+' (плюс) обозначает пересечение стен.
Напишите программу, которая находит выход из дома. По пути нужно собрать как можно больше монет.
При одинаковом количестве монет предпочтительнее путь, при следовании которым открывается меньшее количество дверей.
Во входном файле содержится план дома-лабиринта. Количество строк нечётно и не превышает 101,
все строки имеют одинаковую нечётную длину от 3 до 101. В нечётно-нечётных позициях плана находятся только
символы '+'. В чётно-чётных только символы '.', '*', '$'.
Символы для дверей могут находиться только в нечётно-чётных позициях плана.
В первой строке выходного файла вывести максимальное количество собранных монет,
а затем через пробел количество открытых дверей. Если выйти из лабиринта невозможно, то вывести одно число `-1`.
Пример ввода
+v+^+^+ <*>.>$< +v+v+^+ <$<$>.> +^+v+v+
Пример вывода
2 4
5. Резисторы
Простые числа, разложение на множителиГенерация всех подмножеств, сочетаний, перестановок
Олимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (5) |
| 26/06/2023 | Лето 2023-1 сложные (F) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Томас Эдисон попытался спаять первый в мире телевизор, но обнаружил, что у него нет резисторов на 6 Ом.
"Не беда, зато у меня есть не менее двух резисторов каждого из остальных номиналов от 1 до бесконечности с
шагом 1 Ом", – подумал Эдисон. – "Можно соединить пару резисторов последовательно или параллельно и получится
нужное сопротивление. Например, можно соединить последовательно резисторы 1 Ом и 5 Ом, или 2 и 4, или 3 и 3.
А можно соединить параллельно резисторы 7 и 42, или 8 и 24, или 9 и 18, или 10 и 15, или 12 и 12. Всего 8 способов.
Хм, а сколько есть способов замены для резистора в 120 Ом?" Эдисон так увлекся решением этой задачи, что
телевизор пришлось изобретать другим.
В первой строке входного файла содержится одно натуральное число `R` (`1\ ≤\ R\ ≤\ 10^9`) – требуемое сопротивление.
В первой строке выходного файла вывести одно целое число – число способов получения сопротивления `R` из двух резисторов
с сопротивлениями, выражаемыми натуральными числами.
Пример ввода
6
Пример вывода
8
6. BB-коды
АвтоматыОлимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (6) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
При вводе сообщений на форуме можно пользоваться специальными BB-кодами.
Чаще всего используются следующие коды: [b] … [/b] – вывести текст, написанный между этими кодами, жирным шрифтом;
[i] … [/i] – наклонным; [u] … [/u] – подчеркнутым. Регистр букв не важен.
BB-коды не могут содержать пробелы или символы перехода на новую строку. При преобразовании текста сообщения в
HTML эти BB-коды заменяются на соответствующие HTML-коды <b> и </b>, <i> и </i>,
<u> и </u>. Открывающий BB-код заменяется только в том случае, если далее в
тексте есть соответствующий ему закрывающий BB-код и наоборот. Буквы b, i, u
в HTML-кодах становятся строчными независимо от регистра букв в BB-кодах. Допускается вложенность одинаковых BB-кодов.
Напишите программу, выполняющую преобразование текста сообщения в HTML.
Во входном файле от 1 до 100 строк длиной не более 100 символов, содержащих текст сообщения.
В выходной файл вывести входной текст после замены указанных BB-кодов на HTML-коды.
Пример ввода 1
[I]Текст [/b] сообщения, [b]содержащий[/i] [b]BB[/b]-коды[/b]
Пример вывода 1
<i>Текст [/b] сообщения, <b>содержащий</i> <b>BB</b>-коды</b>
Пример ввода 2 (соответствие кодов)
[b][b][/b]
Пример вывода 2
[b]<b></b>
7. Жадность
МоделированиеПолный перебор
Олимпиадные задачи на русском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (7) |
| 06/09/2008 | Занятие 1 (E) |
| 23/09/2014 | Занятие 4 (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На столе по кругу расставлены `N` чашек, первоначально в каждой чашке лежит по одной конфете. `K` пронумерованных (для определения очередности ходов) игроков становится около одной из чашек на столе. Затем каждый игрок выбирает себе число от 1 до `N-1`. Игроки ходят по очереди. Ход заключается в следующем. Игрок идет по часовой стрелке вокруг стола, считая чашки, пока не пройдет выбранное им в начале игры число чашек, затем забирает конфету (если она там есть) из чашки, около которой он остановился. Игра завершается, когда все чашки опустеют. После этого игроки съедают полученные конфеты.
Напишите программу, которая поможет `K`-ому игроку, называющему число последним, выбрать число, позволяющее получить как можно больше конфет.
В первой строке входного файла содержится два целых числа, разделенных пробелом – количество чашек `N` и количество участников игры `K` (`1\ ≤\ K\ <\ N\ <\ 100`, `N` является простым). Во второй строке содержится `(K-1)` целое число в диапазоне от 1 до `(N-1)`, разделенных пробелами – числа, названные игроками с номерами от 1 до `(K-1)`.
В первой строке выходного файла вывести одно целое число от 1 до `(N-1)` – число, позволяющее `K`-ому игроку получить как можно больше конфет. Если есть несколько равноценных вариантов для числа, вывести наименьшее число.
Пример вывода
5 2 1
Пример вывода
2
8. Password
Преобразование или подсчет характеристики (например, сумма) заданной или вычисляемой последовательности
Олимпиадные задачи на английском языке
| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (8) |
| 09/01/2017 | Марафон 1 (командный) "Hatter's riddles" (J) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
A password is good if its length is more than 6 characters, and it contains at least two letters, at
least two digits, and at least one nonalphanumeric character.
Write a program that checks the password goodness.
The input file contains one or more lines. Each line contains one password up to 32 characters.
ASCII codes of all characters are between 32 and 126.
Write into the output file one line for each password. Print "GOOD" if the password is good.
Otherwise print "BAD".
Sample Input
MAGENTA A1234567 Bob2005 1+2=three E2-E4
Sample Output
BAD BAD BAD GOOD BAD
9. Warnings
Олимпиадные задачи на английском языке| 05/03/2005 | Южно-Уральский открытый командный чемпионат по программированию (9) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
You are to write the part of a compiler that generates warning messages. The programming language is a simplifed
Basic where the only statements are assignments, SUB, WHILE, IF-THEN-ELSE
constructions and RETURN.
Variable names are limited to single upper case letters, and they're always 32-bit signed integers.
Given a syntactically correct subroutine written in this language, generate the appropriate warning messages as
described below.
The syntax of the language only allows one statement per line. Lines will not have leading or trailing spaces,
but tokens may be separated by several spaces. Formally, the syntax for each line is as follows:
<line> ::= <head> | END SUB | <assignment> | <if> | ELSE | END IF | <while> | WEND | RETURN
<head> ::= SUB <name> (<paramlist>) | SUB <name>
<assignment> ::= <variable> = <expr>
<if> ::= IF <expr> THEN
<while> ::= WHILE <expr> DO
<paramlist> ::= <variable> | <variable>,<paramlist>
<expr> ::= <value> | <expr> <operator> <value>
<value> ::= <variable> | <integer> | (<expr>)
<operator> ::= + | - | * | / | < | > | <= | >= | = | <>
<variable> ::= A | B | … | Z
<integer> ::= A 32-bit signed integer
<name> ::= An identificator from upper case letters
The first line in the subroutine will always be the subroutine head and the last line will always contain
a END SUB statement. No other line may contain a subroutine head and END SUB, although RETURN
statements can occur elsewhere as well.
Furthermore, each IF-statement has a corresponding END IF-statement and an optional ELSE-statement
in between. Each WHILE-statement has a corresponding WEND-statement. The IF and WHILE
statements may be nested, but then they will always be properly nested.
You should generate three different warnings, where appropriate. These are: (quotes for clarity only)
"Line <line>: unreachable code"
"Line <line>: variable <variable> might not have been initialized"
"Line <line>: parameter <variable> is never used"
The first warning should be given on lines which are never executed, no matter how the IF-statements are evaluated.
Each such line will only receive this warning, and no other warnings. Lines containing ELSE, END IF, WEND
and END SUB statements will never receive this warning (these lines don't render into executable code by the
compiler).
The second warning should be given on lines where the value of a variable is used, but that variable might
not have been assigned a value yet. A variable will have a value assigned to it if it's in the parameter
list in the subroutine head, or once it's been assigned a value by an assignment statement.
The third warning should be given on lines containing END SUB for a variable which is in the parameter list
in the subroutine head, but which is never used in the subroutine body.
When determining which warnings to give, you should assume that all IF and WHILE statements
can evaluate to either true or false, no matter which instructions have previously been executed.
The warnings should be sorted primarily by line number. If a line contains several different variables
that all might be uninitialized, those warning messages should be sorted alphabetically by the variable name.
The input file contains a number of subroutines. Lengths of all lines are not more 100 characters.
Write into the output file all founded warnings. If there are no warnings in the input file,
write the message "No warnings".
Sample Input
SUB FIRST(A,B) IF A>5 THEN C = B*A END IF D= B - C Z=Y+X E=T F=E+E*A V=G/(G+1) END SUB SUB SECOND(G) RETURN B=G RETURN END SUB
Sample Output
Line 5: variable C might not have been initialized Line 6: variable X might not have been initialized Line 6: variable Y might not have been initialized Line 7: variable T might not have been initialized Line 9: variable G might not have been initialized Line 13: unreachable code Line 14: unreachable code Line 15: parameter G is never used
