Шдень: 1
| Вид материала | Задача |
СодержаниеЗадача A – Угадай-ка Задача B – Обратный порядок Задача C – N-мерный кубик-рубик Задача D – Испорченная шифровка Задача E – Метод Монте-Карло |
VII Відкритий командний Турнір м. Суми з рограмування 2011
 | секція: | Ш | |
| день: | 1 | ||
 |  | | |
Задача A – Угадай-ка
Ограничение времени: 1 сек.
Входной файл: стандартний ввод
Выходной файл: стандартный вывод
В школе проходит экзамен по интуиции. Каждый ученик пишет список чисел на листке бумаги. У учителя есть заранее подготовлен список чисел. Оценка за урок определяется следующим образом: подсчитывается количество чисел в списке ученика присутствующих в списке учителя. Далее подсчитывается отношение полученного числа к общему количеству чисел в списке ученика. Получается число в интервале от 0 до 1. Далее по линейной пропорции определяется оценка в интервале от 2 до 5. Тоесть число 0 соответствует 2, а число 1 — пятерке. И если в итоге получилось действительное число, то оно округляется по математическим правилам и ставится в журнал.
Входные данные
Первая строка содержит количество чисел n (1 < n < 15000) в списке учителя. Следующие n строк содержат сами числа. Каждое число натурально и не более 109. Следующая строка содержит количество чисел ученика m (1 < m < 100000), за которой следуют m строк с самими числами.
Выходные данные
Вывести количество баллов, которое наберет ученик.
Пример
-
input
output
2
1054
1492
4
1492
65536
1492
100
4
| | секція: | Ш | |
| день: | 1 | ||
| | | | |
Задача B – Обратный порядок
Ограничение времени: 1 сек.
Входной файл: стандартний ввод
Выходной файл: стандартный вывод
Имеется зашифрованный текст, в котором каждое слово записано наоборот и все буквенные символы преобразованы в противоположный регистр. Необходимо восстановить исходный текст. Словом является последовательность латинских букв верхнего или нижнего регистра.
Входные данные
Текст, содержащий не более 1000 строк. Длина каждой строки не более 255 символов. Текст может содержать любой печатный знак.
Выходные данные
Дешифрованный текст.
Пример
-
input
output
This is an example of a simple test. If you did not un-derstand the ciphering algorithm yet, then write the letters of each word in the reverse order. By the way, "reversing" the text twice restores the original text.
SIHt SI NA ELPMAXE FO A ELPMIS TSET. Fi UOY DID TON NU-DNATSRED EHT GNIREHPIC MHTIROGLA TEY, NEHT ETIRW EHT SRETTEL FO HCAE DROW NI EHT ESREVER REDRO. Yb EHT YAW, "GNISREVER" EHT TXET ECIWT SEROTSER EHT LANIGIRO TXET.
| | секція: | Ш | |
| день: | 1 | ||
| | | | |
Задача C – N-мерный кубик-рубик
Ограничение времени: 1 сек.
Входной файл: стандартний ввод
Выходной файл: стандартный вывод
Студентам 3-го курса СумГу Лелику и Болику пришла в голову еще одна замечательная идея. Они были готовы создать многомерный кубик-рубик. Они понимали что на ихнем пути будет много нерешаемых задач, но все-таки взялись за реализацию хитрой игрушки. Первая проблема которая стала перед героями это отличие от обычного кубика. У супер кубика не было граней. Вот задача! Лелик и Болик не растерялись и сошлись на идее: в ячейках мнимого кубика хранить произвольные числа.
Только покончили с первой проблемой, возникла вторая: необходимо сформулировать цель решения данной игры. То-есть состояние которое считается выигрышным. Хотя цель решения было крайне сложно сформулировать, Болик на лету придумал решение несуществующей задачки и решили запускать идею в мир. Первым делом необходимо реализовать компьютерную модель и реализовать алгоритм решения задачи. Ну, как полагается часть этой задачи досталась и Вам.
Входные данные
Входной файл состоит из 4 строк.
- единственное число N < 6, задающее количество размерностей кубика.
- N чисел q1, q2, q3 … qN — размеры кубика во всех N измерениях (qi < 10).
- числа, количество которых равно объему кубика, то-есть произведению его размерностей < 1000000. Это содержимое кубика.
В последней строке N элементов разделенные пробелами, среди которых N-1 - числа pi (0 <= pi < qi), и один единственный знак вопроса.
Выходные данные
На выход подается единственное число — сумма чисел в одном из «столбцов» кубика. Какой именно столбец необходимо суммировать указано в последней строке входного файла. Например если последняя строка равна 1 ? 2, это значит что необходимо суммировать числа, для которых первая координата равна 1, 3-я равна 2 а 2-я координата не фиксирована.
Объяснение
Числа в тестах группируются в следующем порядке
[1 2 3 4][5 6 7 8][9 10 11 12]
[[1 2 3 4][5 6 7 8][9 10 11 12]] [[13 14 15 16][17 18 19 20][21 22 23 24]]
Пример
-
input
output
2
3 4
1 2 3 4 5 6 7 8 9 10 11 12
2 ?
42
3
2 3 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 ? 0
51
| | секція: | Ш | |
| день: | 1 | ||
| | | | |
Задача D – Испорченная шифровка
Ограничение времени: 1 сек.
Входной файл: стандартний ввод
Выходной файл: стандартный вывод
Программисты Вася и Петя на работе привыкли при передаче какого-то сообщения подсчитывать его контрольную сумму. Это делалось следующим образом. Каждая буква сопоставлялась с числом то 0 до 25 (известно что программисты писали исключительно на английском языке маленькими буквами). Далее полученные числа складывались и находился остаток от деления на 26. Это и была контрольная сумма.
Однажды, задержавшись на работе Вася забыл прочитать сообщение от Пети, написанное на бумаге. По дороге домой попал под дождь и некоторые буквы в сообщении были не читабельны, или поменяли свое значение. Оставалось лишь одно, перебирая все недостающие буквы и сравнивая контрольные суммы получить исходное сообщение. Для этого необходимо было определить количество вариантов сообщений, которые подходили под оставшееся сообщение.
Входные данные
В первой строке входного файла содержится текст состоящий из прописных латинских букв и знаков «?». Знаки «?» заменяют не читабельные символы.
Во второй строке находится контрольная сумма исходного сообщения.
Выходные данные
Количество вариантов исходного сообщения подходящего под заданный шаблон. Так как количество вариантов может быть огромным необходимо вывести лишь остаток от деления на 2000000000. Учтите что буквы могут не только стираться но и менять свое значение на другую букву.
Пример
-
input
output
aba?aba
9
1
| | секція: | Ш | |
| день: | 1 | ||
| | | | |
Задача E – Метод Монте-Карло
Ограничение времени: 1 сек.
Входной файл: стандартний ввод
Выходной файл: стандартный вывод
В физике и математике часто встречаются задачи которые решить каким-нибудь детерминированным методом достаточно сложно. В таком случае ученые обращаются к такой науке как теория вероятности.
Ученый школьник Петя из 4Д класса захотел решить одну из таких задач. Но эта задача, которую он выбрал оказалась достаточно сложной, чтоб решать ее детерминированными методами. Прочитав несколько книжек Петя решил использовать метод Монте-Карло для решения.
Задача заключается в нахождении площади много угольника. Для этого необходимо выполнить следующие действия:
- на листке бумаги чертится произвольный многоугольник. Ребра многоугольника не пересекаются.
- выбирается прямоугольная область таким образом, чтоб многоугольник лежал полностью в ней.
- Генерируется произвольное количество случайных точек, лежащих в полученном прямоугольнике, и для каждой точки проверяется принадлежность к многоугольнику.
- Умножив площадь прямоугольной области на количество попавших точек, и поделив на общее количество точек можно получить приблизительное значение площади многоугольника.
Так как Петя еще только в 4 классе, он не умеет работать с большими числами, по-этому часть работы придется сделать Вам.
Входные данные
В входном файле содержится один единственный тест. Каждый тест начинается с одного числа N < 1000 — количество точек многоугольника. Далее следуют N пар чисел xi, yi (-1000 < xi, yi < 1000) — координаты вершин многоугольника в порядке обхода. После описания многоугольника идет набор чисел придуманных Петей. Их количество не больше 100 Начинается этот блок с количества чисел Q. После в Q строках следуют Q пар чисел — координаты точек.
Выходные данные
Для каждой, придуманной Петей точкой, вывести число в отдельной строке:
1 — если точка лежит в многоугольнике
0 — если точка не лежит в многоугольнике.
После Q строчек вывести число — соотношение количества попавших точек к общему количеству точек с точностью 4 знака после запятой.
Пример
-
input
output
4
0 0
1 0
1 1
0 1
5
0.5 0.5
1 1
0 0.5
1 0.5
2 0.5
1
1
1
1
0
0.8000