Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Восьмая командная олимпиада"

Задача A. Дорожная политика

(Время: 1 сек. Память: 16 Мб)

В некотором государстве приближается транспортная реформа, в результате которой предстоит соединить все N городов дорогами. Требуется определить общее количество дорог в государстве по завершении их строительства.

Входные данные

Входной файл INPUT.TXT содержит натуральное число N – количество городов (N ≤ 4∙109).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
121
246

Система оценки

Решения для N ≤ 104 оцениваются в 40 баллов. Решения для N ≤ 106 оцениваются в 60 баллов.


Задача B. Водолей

(Время: 1 сек. Память: 16 Мб)

У исполнителя «Водолей» есть два сосуда: первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

  1. Наполнить сосуд A (>A).
  2. Наполнить сосуд B (>B).
  3. Вылить воду из сосуда A (A>).
  4. Вылить воду из сосуда B (B>).
  5. Перелить воду из сосуда A в сосуд B (A>B).
  6. Перелить воду из сосуда B в сосуд A (B>A).

Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полностью наполняется.

Требуется составить алгоритм для «Водолея», который позволяет получить в точности N литров в одном из сосудов.

Входные данные

Входной файл INPUT.TXT содержит три натуральных числа A, B и N, не превосходящих 104.

Выходные данные

В выходной файл OUTPUT.TXT выведите алгоритм действий «Водолея», который позволяет получить в точности N литров в одном из сосудов, если же такого алгоритма не существует, то следует вывести «Impossible».

Количество операций в алгоритме не должно превышать 105. Гарантируется, что если задача имеет решение, то существует решение, состоящее не более, чем из 105 операций.

Примеры

INPUT.TXTOUTPUT.TXT
13 5 1>A
A>B
>A
A>B
23 5 6Impossible

Задача C. CSV Reader

(Время: 1 сек. Память: 16 Мб)

CSV (от англ. Comma-Separated Values – значения, разделённые запятыми) – текстовый формат, предназначенный для представления табличных данных.

Описание формата:

Каждая строка файла – это одна строка таблицы. Строки не могут быть пустыми. Каждая строка заканчивается символом перевода строки.

aaa,bbb,ccc
xxx,yyy,zzz

Каждая строка содержит одну или более ячеек, разделенных запятыми. Разные строки могут содержать разное количество ячеек. Значение ячейки может быть пустым. Пробелы являются частью значения ячейки и не должны игнорироваться. После последней ячейки запятая не ставится.

aaa,a and b,bbb
aaa„ccc,ddd

Если значение содержит запятую, оно обязательно обрамляется двойными кавычками. В противном случае двойные кавычки могут отсутствовать.

aaa,"bbb","c , c"

Если обрамленное значение содержит двойные кавычки – они представляются в виде двух двойных кавычек подряд.

"aaa","a ""and"" b"

Ваша задача – написать программу, которая будет читать данные в CSV формате и выводить их на печать в отформатированном виде.

Входные данные

Входной файл INPUT.TXT имеет CSV формат и содержит не более 100 непустых строк. Каждая строка содержит не более 100 символов. Допустимые символы: строчные и прописные английские буквы, цифры, знаки препинания (точка, запятая, вопросительный и восклицательный знак, двоеточие, точка с запятой, двойные кавычки) и пробелы.

Выходные данные

В выходной файл OUTPUT.TXT выведите информацию из файла, отформатированную по следующим правилам:

  • каждая строка содержит одинаковое количество ячеек. Строки могут дополняться справа необходимым количеством пустых ячеек;
  • ширина каждого столбца подбирается автоматически по ширине самого длинного значения;
  • остальные значения выравниваются по левому краю и дополняются справа необходимым количеством пробелов;
  • разделитель между ячейками в строке – вертикальная черта «|».

Пример

INPUT.TXTOUTPUT.TXT
1
a,b,c,d,e
"aa",,"cc",dd
"a,a,a","b,b","c"
"a,""a"",""","a and ""b""",,a"b
a      |b        |c |d  |e
aa     |         |cc|dd | 
a,a,a  |b,b      |c |   | 
a,"a","|a and "b"|  |a"b| 

Задача D. Композиция

(Время: 2 сек. Память: 16 Мб)

Тони пишет программное обеспечение для бирж. Одна из компонент, которой он занимается, должна будет отображать графики рисков и доходности различных финансовых инструментов. В качестве одной из подзадач у него возникла задача построения композиции двух непрерывных кусочно-линейных функций.

Даны две функции: f (x) и g(x), требуется найти представление функции g(f(x)) в виде кусочно-линейной функции.

Входные данные

Входной файл INPUT.TXT содержит два блока, один описывает функцию f, а другой функцию g. Каждый блок начинается с числа l – количества интервалов, на которых соответствующая функция является линейной. (1 ≤ l ≤ 1000, l ≠ 2).

Если l > 2, то следующие l−1 строка содержат точки излома функции. Каждая строка содержит два целых числа: xi, yi (i от 1 до l−1, xi < xi+1). Функция a(x), описываемая блоком, имеет следующий вид:

Здесь ki = (yi+1 − yi)/(xi+1 − xi).

Если же l = 1, то следующая строка содержит одно целое число y, описываемая функция имеет вид a(x) = y.

Все координаты во входном файле не превосходят 109 по модулю.

Выходные данные

В выходной файл OUTPUT.TXT выведите функцию g(f(x)) в том же формате, что и функции, заданные во входном файле. Количество интервалов, на которые разбивается график функции, должно быть минимальным. Гарантируется, что для описания функции потребуется не более 105 интервалов. Выводите вещественные числа с точностью не менее 10−8.

Пример

INPUT.TXTOUTPUT.TXT
13
0 0
2 3
4
0 0
1 3
2 0
4
0 0
0.666666666667 3
1.333333333333 0

Задача E. Пирамиды

(Время: 1 сек. Память: 16 Мб)

Рассматриваемые пирамиды имеют треугольник в основании, то есть являются тетраэдрами. Требуется по заданным длинам рёбер пирамиды найти её объём.

Входные данные

Входной файл INPUT.TXT содержит 6 чисел через пробел – длины рёбер пирамиды ABCD. Длины рёбер – целые положительные числа, не превосходящие 1000. Порядок рёбер: AB, AC, AD, BC, BD, CD.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно вещественное число с четырьмя знаками после запятой – объём пирамиды.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 1 1 1 10.1179
21000 1000 1000 3 4 51999.9937

Задача F. Игра в зачеркивание

(Время: 1 сек. Память: 16 Мб)

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.

Входные данные

Первая строка входного файла INPUT.TXT содержит числа N и K (1 ≤ K ≤ N ≤ 40), во второй строке записаны N символов: английская заглавная O – пустая клетка, английская заглавная X – зачёркнутая клетка.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя (ничья).

Примеры

INPUT.TXTOUTPUT.TXT
14 2
OOOO
1
25 2
OOOOO
2
37 2
OXXOXXO
0

Задача G. Колода карт

(Время: 1 сек. Память: 16 Мб)

Каждые выходные к Никите приходят друзья, чтобы поиграть в карты. Для игры число карт в колоде должно быть кратно количеству игроков.

У Никиты есть колода из N карт. Он решил, что для каждой новой игры он будет выбирать такое количество карт, которым не играли ранее. В карты они играют либо вдвоём, либо втроём. Помогите Никите подсчитать, какое количество игр можно будет сыграть этой колодой.

Входные данные

В единственной строке входного файла INPUT.TXT записано натуральное число N (1 ≤ N ≤ 109) – количество карт в колоде.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно натуральное число – количество игр, которые можно сыграть этой колодой.

Примеры

INPUT.TXTOUTPUT.TXTПояснения
153Можно играть колодами из 2, 3, 4 карт
264Можно играть колодами из 2, 3, 4, 6 карт

Задача H. Ёлочка

(Время: 1 сек. Память: 16 Мб)

Необходимо нарисовать ёлочку, состоящую из N уровней. Каждый из уровней представляет собой равнобедренный треугольник, состоящий из звёздочек. Первая строка каждого уровня содержит одну звездочку. Каждая последующая строка имеет на две звездочки больше предыдущей. Первый уровень имеет M звёздочек в основании, каждый последующий повторяет предыдущий с добавлением одной строки. Все линии из звёздочек должны быть выровнены по центру.

Входные данные

Входной файл INPUT.TXT содержит целые числа M и N – размер основания первого уровня и количество уровней соответственно (3 ≤ M < 50, 1 ≤ N ≤ 50, M - нечётно).

Выходные данные

В выходной файл OUTPUT.TXT выведите прямоугольник, состоящий из символов «.» и «*», который отражает ёлочку. Ширина прямоугольника должна соответствовать ширине последней строки нижнего уровня ёлочки.

Примеры

INPUT.TXTOUTPUT.TXT
13 1.*.
***
25 2...*...
..***..
.*****.
...*...
..***..
.*****.
*******

Система оценки

Решения, работающие только для M=3 и N ≤ 10, будут оцениваться в 20 баллов.

Решения, работающие только для N=1, будут оцениваться в 20 баллов.

Решения, работающие только для M=3, будут оцениваться в 40 баллов.



Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru



Подали совет купить диплом юриста http://i-diplomu.com/yurist учти всего 5 кликов.