7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2000

Подразделы

Другие разделы

Дата и время

19/12/2024 18:14:36

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи командных соревнований для школьников 2000

1. Треугольная задача

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

172.gif
Корпорация WarSoft, специализирующаяся на клонах популярных игр, приступила к разработке сетевой RTS–игры "Триада" для троих игроков, в которой у каждого игрока были бы совершенно равные шансы на выигрыш. Это возможно сделать, если вместо обычного квадратного поля использовать треугольное, разделенное на "клетки" – треугольники. Если все ресурсы и строения в стартовой позиции расставить симметрично, то выигрыш игрока будет зависеть только от его опыта и скорости реакции. Все "клетки" треугольного поля были пронумерованы последовательно, начиная с 1, сверху вниз и слева направо, как показано на рисунке.
Таким образом для указания позиции "юнита" (unit, единица войск) достаточно указать номер треугольника, в котором он находится. "Юниты" могут передвигаться в соседние треугольники только через общую сторону двух треугольников. Такое передвижение будем называть ходом.
Напишите программу, которая позволяет определить минимальное число ходов, которое потребуется “юниту”, чтобы перейти из треугольника с номером `N` в треугольник с номером `M`.
Ввод
Во входном файле в первой строке содержатся два натуральных числа `N` и `M` (`1≤N,\ M≤100000`) через один пробел.
Вывод
В выходной файл вывести минимальное число ходов.

Пример ввода

14 3

Пример вывода

5

2. Круглая задача

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

После того как Робинзон Крузо построил свою лодку, он решил обследовать близлежащие острова архипелага из `N` островов. Целью своего путешествия он выбрал `N`-й остров, надеясь, что обнаружит на нем туземное поселение и британского консула. Опасаясь внезапных тропических штормов, он решил не отплывать далеко от берега и переплывать с одного острова на другой, только если расстояние между берегами этих островов (и, следовательно, плавание вдали от берега) не превышает `D` километров.
Для упрощения задачи все острова будем считать кругами с разным радиусом. Напишите программу, которая поможет Робинзону определить, сможет ли он добраться до `N`-го острова.
Во входном файле в первой строке содержатся два целых числа `N` (`2\ ≤\ N\ ≤\ 100`) и `D` (`5\ ≤\ D\ ≤\ 50`), разделенных одним пробелом – число островов и максимальное расстояние, на которое отваживается совершить плавание Робинзон. В следующих `N` строках находится по три целых числа `X_i`, `Y_i`, `R_i` (`0\ ≤\ X_i,\ Y_i\ ≤\ 1000`, `1\ ≤\ R_i\ ≤\ 50`, `1\ ≤\ i\ ≤\ N`) через один пробел – координаты и радиус острова. Первый остров является стартовым, а `N`-й – целью путешествия.
В выходной файл вывести "YES", если Робинзон сумеет добраться до цели, или "NO", если цели невозможно достичь для заданного ограничения `D`.

Пример ввода

5 9
5 25 3
8 12 2
15 15 5
30 15 3
35 5 4

Вывод для примера

YES

3. Квадратная задача

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Сколько различных квадратов можно насчитать в прямоугольнике из `n` на `m` клеток? Например в прямоугольнике 5x5 можно найти 55 различных квадратов (25 квадратов 1x1, 16 квадратов 2x2, 9 квадратов 3x3, 4 квадрата 4x4 и 1 квадрат 5x5).
Во входном файле в первой строке содержатся два натуральных числа `n` и `m` (`1\ ≤\ n,\ m\ ≤\ 1000`) через один пробел.
В выходной файл вывести число квадратов.

Пример ввода

5 5

Пример вывода

55

4. Все пути ведут в нуль

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Любое натуральное число (т.е. целое число большее 0) можно представить в виде произведения двух натуральных чисел `X` и `Y`, таких что `X\ ≤\ Y`. Если заменить в этом разложении число `X` на `X-1`, а `Y` на `Y+1`, то после вычисления произведения получим либо новое натуральное число, либо нуль. Например, для числа 12 возможно три варианта разложения `1*12`, `3*4`, `2*6`. Первый вариант дает 0: `(1-1)*(12+1)=0`, второй вариант дает 10: `(3-1)*(4+1)=10`, а третий – 7: `(2-1)*(6+1)=7`. Если результат отличен от нуля, то повторяя эту процедуру над получившимся натуральным числом, мы в конце концов придем к нулю, независимо от выбираемого варианта разложения.
Напишите программу, которая находит все различные числа, которые могут встретиться на пути к 0, при применении данной процедуры к натуральному числу `N`.
Во входном файле в первой строке содержатся натуральное число `N` (`1\ ≤\ N\ ≤\ 10000`).
В выходной файл вывести все найденные числа, в порядке возрастания, начиная с 0. Числа в списке разделяются одним пробелом. Даже если какое-то число встречается на нескольких путях, оно печатается в списке только один раз.

Пример ввода

12

Пример вывода

0 3 4 6 7 10

5. Транслятор для языка Basic-

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Транслятор переводит программу на языке высокого уровня в программу на машинном языке. Напишите транслятор для упрощенного языка Basic-. В языке Basic- всего 26 переменных, обозначаемых прописными латинскими буквами от A до Z. Так как все переменные целые, то операторы объявления переменных отсутствуют. Для упрощения задачи в языке также отсутствуют операторы ввода-вывода, ветвления и цикла, комментарии, а также все операции и функции, кроме бинарных операций + и –. В результате программа на языке Basic- состоит из последовательности операторов присваивания вида:

<переменная> = <выражение>
где <выражение> это <операнд> или <выражение> + <операнд> или <выражение> - <операнд>
а <операнд> это <переменная> или ( <выражение> )

Каждый оператор присваивания записывается на отдельной строке, не содержит пробелов, длина оператора не превышает 80 символов. Пример программы:
A=B
D=A+(B-C)

Машинный язык, на который транслируется программа, состоит всего из 4 команд:

LOAD <переменная>
Загружает значение переменной в стек.

SAVE <переменная>
Сохраняет вершину стека в переменной.

ADD
Складывает два числа на вершине стеке, сумма помещается в стек.

SUB
Вычисляет разность на двух чисел на вершине стека, разность помещается в стек.

Результат трансляции вышеуказанной программы из двух операторов может выглядеть следующим образом:
LOAD B
SAVE A
LOAD C
LOAD A
LOAD B
ADD
SUB
SAVE D
Это не единственный вариант машинного кода. Результат вычислений не изменится, если поменять местами, например, команды LOAD A и LOAD B.
Во входном файле программа на языке Basic- (один или более операторов присваивания).
В выходной файл вывести результат трансляции программы на машинный язык. Не делайте оптимизирующий транслятор! Последовательность блоков кода для операторов присваивания должна совпадать с последовательностью этих операторов в программе на языке Basic-. Для каждого оператора присваивания должна быть команда SAVE, которая должна быть последней в соответствующем блоке кода. Каждому появлению переменной в правой части оператора присваивания должна соответствовать команда LOAD в машинном коде. В пределах блока кода порядок машинных команд может быть достаточно произвольным, требуется лишь соответствие результата вычислений выражению в правой части оператора присваивания.

Пример ввода

A=B
D=A+(B-C)

Пример вывода

LOAD B
SAVE A
LOAD A
LOAD C
LOAD B
SUB
ADD
SAVE D
loading