Ну что ж, много народу приходит на тренировки.
Поэтому предлагаю выкладывать условия интересных задач здесь.Добавлено (21.11.2007, 23:44)
---------------------------------------------
Задача А: Треугольник и точка
Определите, лежит ли заданная точка внутри заданного треугольника.
Входной файл (A.IN): первые 3 строки содержат координаты вершин треугольника (в каждой строке по 2 целых числа, разделенных пробелом). Четвертая строка содержит координаты точки, в таком же формате. Все числа – целые, по модулю не превосходящие 10000. Гарантируется, что вершины треугольника не лежат на одной прямой.
Выходной файл (A.OUT): единственная строка содержит слово «In», если точка лежит внутри треугольника, «On», если точка лежит на границе треугольника (вершине либо стороне), или «Out», если она лежит вне него.
Пример:
Входной файл:
-2 -2
3 1
0 1
0 0
Выходной файл:
In
Время на тест: 1 сек.
Добавлено (21.11.2007, 23:45)
---------------------------------------------
Задача B Окружность и треугольник
На плоскости расположены окружность и треугольник. Необходимо определить количество точек, в которых они пересекаются.
Входные данные (файл B.IN):
Первая строка: координаты центра окружности и ее радиус
Следующие три строки: координаты вершин треугольника.Ни одна из вершин не лежит на окружности.
Все числа целые.
В файл B.OUT вывести целое число – количество общих точек.
ПРИМЕР
B.IN:
0 0 4
0 0
0 50
50 0
В.OUT:
2
Добавлено (22.11.2007, 00:03)
---------------------------------------------
а эти с тренировки 14.11.2007
Задача A: Поиск палиндромов
Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например «топот», «bob».
Определите, сколько палиндромов заданной длины K содержит заданная строка S ?
Входные данные находятся в текстовом файле A.IN . В его первой строке содержится целое число K (2 <= K <= 200), а во второй – заданная строка S, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» - не палиндром). Длина S от 1 до 200 символов.
Выходные данные должны быть записаны в текстовый файл A.OUT . В его единственной строке должно находиться количество различных палиндромов длины K, содержащихся в S (т.е. являющихся последовательностями подряд идущих символов в S) (различными считаются палиндромы, начинающиеся с разных позиций в S).
Пример:
Входной файл: Выходной файл:
3
babcbab 3
Время на тест: 2 сек.
---------------------------------------------------------------------------------------------------------------------------------- ---------------------------------
Задача В: Анализ программы
При анализе исходного текста программы полезно знать, присутствуют ли в нем операторы, которые никогда не будут выполняться, т.к. это практически всегда говорит об ошибках в программе. Поэтому модули для такой проверки включаются в состав компилятора для любых языков программирования. Вам необходимо смоделировать работу такой проверяющей подсистемы.
Входные данные находятся в текстовом файле B.IN, состоящем из N строк (1 <= N <= 10000), полученных в результате синтаксического анализа исходного текста программы. Каждая строка этого файла соответствует одному оператору исходного текста и содержит следующие данные:
NEXT – после оператора, соответствующего этой строке, может быть выполнен лишь следующий по порядку оператор;
JUMP номер - после оператора, соответствующего этой строке, может быть выполнен лишь оператор с указанным номером (нумерация операторов начинается с единицы);
JUMP номер1 OR номер2 - после оператора, соответствующего этой строке, может быть выполнен один из двух операторов, номера которых указаны.
Номера операторов отделены от служебных слов одним или несколькими пробелами.
Известно, что программа всегда начинает выполняться с оператора с номером 1.
Выходные данные помещаются в текстовый файл B.OUT и состоят из нескольких строк. Первая строка содержит число невыполняемых операторов, каждая из последующих строк – их номера, расположенные в порядке возрастания.
Пример входных данных.
NEXT
JUMP 4 OR 6
NEXT
JUMP 3
NEXT
JUMP 8
NEXT
NEXT
Пример выходных данных.
2
5
7
Время на тест: 3 сек.
Добавлено (22.11.2007, 00:04)
---------------------------------------------
Задача C: Награда для мудреца
Согласно древней индийской легенде, некогда царь пообещал щедро вознаградить одного мудреца и предложил ему самому выбрать себе награду. Мудрец достал шахматную доску и попросил царя насыпать на нее зерна по следующему правилу: на первую клетку доски положить одно зерно, на вторую – два, на третью – четыре, на четвертую – восемь и так далее, кладя на каждую последующую клетку вдвое больше зерен, чем на предыдущую.
Царь удивился малости просьбы мудреца и, не раздумывая, согласился. Но вскоре он убедился, что всего зерна его царства не хватает, чтобы выполнить эту «небольшую» просьбу…
Попробуйте подсчитать точно, сколько зерен понадобится царю, чтобы заполнить по вышеописанному правилу доску N x N клеток.
Входные данные находятся в текстовом файле C.IN . Его единственная строка содержит целое число N (1 <= N <= 100).
Выходные данные должны быть записаны в текстовый файл C.OUT . Его единственная строка должна содержать точное число зерен, необходимых для заполнения доски.
Пример 1:
Входной файл: Выходной файл:
3 511
Пояснение к примеру 1:
1 2 4
8 16 32
64 128 256
1+2+4+8+16+32+64+128+256=511
Пример 2:
Входной файл: Выходной файл:
10 1267650600228229401496703205375
Время на тест: 2 сек.
-------------------------------------------------------------------------------------------
Задача D: Капризные дети
Няня укладывает спать детей. Но самой ей поспать никак не удается: не успевает она уложить спать одних, как просыпаются другие…
У няни N детей, и все они очень разные. Она уже запомнила, сколько минут ей нужно, чтобы уложить спать k-го ребенка (обозначим это время через ak), и сколько минут после этого он будет спать (обозначим это время через bk). Сама няня может спать, только когда спят все дети.
Помогите няне узнать, в каком порядке нужно укладывать детей, чтобы она могла поспать как можно дольшее время подряд.
Например, пусть есть всего 2 ребенка: a1=1, b1=10, a2=10, b2=20. Если она сначала начнет укладывать первого ребенка, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго, то затем она успеет уложить первого и получит целых 10 минут отдыха.
Входной файл (D.IN): первая строка содержит N (1≤N≤100000). Вторая строка содержит натуральные числа a1 … an , третья - b1 … bn . Числа не превосходят 109 и отделяются друг от друга пробелами.
Выходной файл (D.OUT): единственная строка должна содержать число T, равное максимально возможному времени сна няни, либо 0, если ей поспать не удастся.
Пример:
Входной файл:
2
1 10
10 20
Выходной файл:
10
Время на тест: 2 сек.
