Задача A. Квадраты и кубы

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных чисел от a до b, включительно. Будем называть k-плотностью этого множества количество пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2 − y3| ≤ k. Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как подходят следующие пары:

x = 1, y = 1, |x2 − y3| = |1 − 1| = 0;

x = 3, y = 2, |x2 − y3| = |9 − 8| = 1;

x = 5, y = 3, |x2 − y3| = |25 − 27| = 2.

Требуется написать программу, которая по заданным натуральным числам a и b, а также целому неотрицательному числу k, определяет k-плотность множества натуральных чисел от a до b, включительно.

Формат входных данных

Входные данные содержат три строки. Первая строка содержит натуральное число a, вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное число k.

Формат выходных данных

Выходные данные должны содержать одно целое число: искомую k-плотность множества натуральных чисел от a до b, включительно.

Ограничения

1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018

Описание подзадач и системы оценивания

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

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
a, bk
1101 ≤ a ≤ b ≤ 1000k = 0полная
2101 ≤ a ≤ b ≤ 1018k = 01полная
3151 ≤ a ≤ b ≤ 10000 ≤ k ≤ 101полная
4151 ≤ a ≤ b ≤ 1060 ≤ k ≤ 101, 3полная
5151 ≤ a ≤ b ≤ 1090 ≤ k ≤ 101, 3, 4полная
6151 ≤ a ≤ b ≤ 1090 ≤ k ≤ 1091, 3, 4, 5полная
7201 ≤ a ≤ b ≤ 10180 ≤ k ≤ 101816полная

Примеры тестов

Стандартный вход Стандартный выход
1
1
30
2
3

Задача B. Парашютное шоу

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

В распоряжении комитета по организации праздников имеется n самолётов и p парашютистов. Необходимо устроить парашютное шоу с определенными требованиями:

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

Шоу нужно сделать максимально красочным, поэтому прыжок должно совершить максимально возможное количество парашютистов. Парашютисты, не задействованные в шоу, остаются на земле.

Кстати, самолёты ограничены по вместимости. Столько проблем у комитета по праздникам!

Сколько парашютистов останется на земле?

Формат входного файла

В первой строке входные данные содержат целые числа p, g и n — общее количество парашютистов, размер выпрыгивающей группы и количество самолетов. Во второй строке — n целых чисел ai, где ai равно максимальной вместимости i-го самолета.

Формат выходного файла

Выходные данные должны содержать одно целое число — количество парашютистов, оставшихся на земле.

Ограничения

1 ≤ p, g, ai ≤ 105

1 ≤ n ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1000 10 10
100 100 100 100 100 100 100 100 100 100
0
2
100 10 8
8 9 10 11 12 13 14 15
100
3
100 4 8
8 9 10 11 12 13 14 15
36

Задача C. Змейка

Автор:О. Бабушкин   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

Подружки Катя и Надя уже давно играют в игру «Змейка».

Поле для игры представляет собой клетчатый квадрат со стороной n. В каждой клетке квадрата может быть либо зеленая лужайка, либо пень. Изначально в их распоряжении находится змейка длиной 1. За один шаг змейка может перемещаться в одном из 4х направлений: вверх, вниз, вправо и влево. Однако змейка не может ползать по пенькам.

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

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

Формат входного файла

В первой строке входного файла находится число n. В последующих n строках содержится по n символов задающих лабиринт. Лужайке соответствует символ ‘.’, пню – ‘#’, i-ому яблоку цифра i

Формат выходного файла

В единственной строке выходного файла должно содержаться одно число – минимальное требуемое число ходов. Если собрать все яблоки не возможно, выведите -1.

Ограничения

2 ≤ n ≤ 10.

2 ≤ k ≤ 8.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
#3.
1.2
#4#
        
6
2
3
#43
1.2
#5#
        
-1

Задача D. Пример

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется написать программу, которая что-то делает

Формат входных данных

Входные данные содержат

Формат выходных данных

Выходные данные должны содержать

Ограничения

1 < N < 100

Примеры тестов

Стандартный вход Стандартный выход
1
0
1

Задача E. Задача имени Подчувалова

Максимальный балл:4   Ограничение времени:1 сек
  Ограничение памяти:256 Мб

Условие

Ответьте на следующие вопросы.

Вопрос 1

Центральная звезда Солнечной системы.

Солнце Марс Сириус Я не знаю

Вопрос 2

Введите слово Mem

Вопрос 3

Сколько будет 4 + 4?

23 64 9 162

Вопрос 4

Кто автор следующих строк? Ввести имя и фамилию на английском через пробел. Make your mama sad type Make your girlfriend mad tight Might seduce your dad type I'm the bad guy, duh

Формат выходного файла

Для решения вам доступны тестовые формы и редактор кода. i-ой строчке редактора соответсвует ответ на i-ый вопрос. Если требуется ввод ответа, то (внезапно) его надо ввести. Для вопросов с одним вариантом ответа требуется записать его номер. Для вопросов с несколькими вариантами ответа введите их номера через пробел. Пример: 1 3 5. Чтобы отобразить редактор нажмите на кнопку справа от названия задачи. Выпадет менюшка. Жмакните на чекбокс редактор. Просьба: несколько раз отправить решение задачи следующими способами

  1. Ответить правильно через тестовые формы
  2. Ответить неправильно через тестовые формы
  3. Ответить правильно через редактор
  4. Ответить неправаильно через редактор
  5. Напишите в редактор всякую дичь


0.213s 0.008s 25