Задачи по программированию
Задача G. Линия
Имя входного файла: G.in
Имя выходного файла: G.out
Максимальное время выполнения задачи – 10 секунд.
Дана последовательность k-линейных многочленов на отрезке [а,b] и их значения на концах отрезка. Выяснить, сколько линий пересекутся в заданной точке с координатами (х, у).
Формат входных данных
В первой строке число k – количество линейных многочленов, во второй – концы отрезка а и b, в третьей – координаты точки х,у, последующие k строк – значения в точке а и в точке b для каждого многочлена.
Формат выходных данных
Одно число – количество линий, пересекающихся в заданной точке.
Пример
| G.in | G.out |
| 1.0 2.0 1.5 5.0 5.0 10.0 2.0 4.0 5.0 5.0 2.0 10.5 8.0 2.0 |
Задача H. Окужность
Имя входного файла: H.in
Имя выходного файла: H.out
Максимальное время выполнения задачи – 10 секунд.
Узор состоит из m (2..10) окружностей, заданных своими координатами центров (х, у) и радиусов r. Найти наибольшее количество окружностей, центры которых лежат на линиях первой окружности.
Формат входных данных
В первой строке число m – количество окружностей, в следующих m строках – центр х, у и радиус г каждой окружности/
Формат выходных данных
Одно число – количество таких окружностей.
Пример
| H.in | H.out |
| 2.0 3.0 2.0 4.0 1.0 1.0 4.0 4.0 3.0 7.0 4.0 2.0 |
Задача B. Геометрическая прогрессия
Имя входного файла: B.in
Имя выходного файла: B.out
Максимальное время выполнения задачи – 15 секунд.
Задана последовательность действительных чисел. Количество чисел в этой последовательности не превышает 10000. Необходимо определить, можно ли выстроить эти числа в отрезок геометрической прогрессии. Порядок может и не совпадать.
Формат входных данных
Во входном Файле, через пробел в одну или несколько строк записаны действительные числа.
Формат выходных данных:
Вывести "YES"- если такую последовательность можно построить, или "NO"- если это не так.
Пример
| B.in | B.out |
| 1 2 4 8 16 32 64 128 | YES |
Задача D. Точки на окружности
Имя входного файла: D.in
Имя выходного файла: D.out
Максимальное время выполнения задачи – 10 секунд
Заданы координаты N точек в декартовой системе координат. Определить наибольшее количество точек (K>1), лежащих на одной окружности, центром которой является координата (X0,Y0). Вывести наименьший радиус найденной окружности. Если таких точек нет, то вывести “No solution”.
Формат входных данных
В первой строке задается N (2<=N<=1000). Во второй строке координата центра окружности X0,Y0. Следующие N строк – координаты точек.
Формат выходных данных
В одной строке через пробел вывести количество точек и радиус окружности с тремя знаками после запятой или сообщение “No solution”.
Примеры
| D.in | D.out |
| 0.0 0.0 1.0 0.0 0.0 1.0 2.0 2.0 2.0 1.0 | 2 1.000 |
| 0.0 0.0 1.15 0.0 0.0 1.15 1.3 0.0 -1.15 0.0 0 -1.17 | 3 1.150 |
| 1.0 1.0 1.0 0.0 0.0 5.0 1.3 0.0 -1.15 0.0 0 -1.17 | No solution |
Задача B. Лист Мёбиуса
Технические требования:
Имя файла: b
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 2 сек.
Археологи нашли в раскопках длинный лист Мёбиуса с набранными на нем буквами (лист Мёбиуса не имеет начала и конца, т.е. нет верха и низа и все символы располагаются как будто на одной стороне). Если отметить начало, то можно найти одно и то же слово несколько раз. Так как лист Мёбиуса не имеет начала и конца, то символы могут быть как в начале строки, так и в конце. Поэтому, при поиске строки необходимо все символы циклически сдвигать влево, забирая символ с конца и переставляя его на первое место, так чтобы их можно было прочитать с начала строки. Определите, сколько раз встречается на этом листе заданный набор символов и сколько раз при поиске потребуется сделать циклический сдвиг символа влево.
Формат входных данных
В первой строке записаны символы, найденные на листе Мёбиуса в заданном порядке (их может быть от 2 до 10 000), во второй – набор символов для поиска.
Формат выходных данных
В одну строку через пробел вывести количество повторений и наименьшее количество циклических сдвигов влево при поиске заданного набора символов. Считать прописные и строчные буквы разными.
Примеры
| input.txt | output.txt |
| абракадабра бра | 2 10 |
| абрикос коса | 1 3 |
Задача C. Матрёшки
Технические требования:
Имя файла: с
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 2 сек.
Множество из N (N <= 1000) прямоугольных параллелепипедов задано измерениями этих параллелепипедов (длина и ширина основания, высота).
Нужно сделать так, чтобы параллелепипеды были вложены друг в друга как «матрешки». При вложении стороны параллелепипедов располагаются параллельно и перпендикулярно друг другу; параллелепипеды могут быть повёрнуты, чтобы разместиться в очередном.
Требуется написать программу, указывающую порядок вложения параллелепипедов или сообщающую об отсутствии решения задачи.
Примечание. Параллелепипеды ограничены каркасом ненулевой толщины. Это означает, что, например, параллелепипед размером 10 × 11 × 12 не может быть помещён в параллелепипед размером 10 × 11 × 13.
Формат входных данных
Первая строка — N; в каждой из следующих N строк — три действительных числа — измерения соответствующего параллелепипеда.
Формат выходных данных
Строка, содержащая N чисел, — номера параллелепипедов исходной последовательности в порядке вложения параллелепипедов друг в друга, начиная с большего, или сообщение «NO».
Примеры
| input.txt | output.txt |
| 1 2 3 10 30 20 5 6 8 | 2 3 1 |
| 1 2 40 10 30 20 5 6 8 | NO |
Задача A. Маленький принц
Технические требования:
Имя файла: а
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 1 мин.
В сказке-были Сент-Экзюпери маленький принц рассчитал свой путь от своей планеты до Земли и обратно, побывав на нескольких других планетах. Но если предположить, что планеты стоят на месте, а планет больше- то, как маленькому принцу найти наименьший путь от своей планеты и обратно, побывав на каждой из них один раз?
Формат входных данных
В первой строке задано число N (1<=N<=10)- количество планет, не считая планеты маленького принца. Во второй строке три действительных числа X, Y, Z координаты планеты маленького принца. В следующих N строках координаты планет, представленных тремя действительными числами Xi, Yi, Zi.
Формат выходных данных
В первой строке вывести наименьшее расстояние, пролетевшее маленьким принцем, в формате 6 знаков после десятичной запятой. Во второй строке вывести номера планет в порядке их обхода, не учитывая планету маленького принца.
Примеры
| input.txt | output.txt |
| 0 0 0 1 0 0 0 1 0 | 3.414214 1 2 |
Задача B. Новогодние хлопушки
Технические требования:
Имя файла: b
Имя файла для входных данных: input.txt
Имя файла для выходных данных: output.txt
Время на выполнение каждого теста: 1 сек.
На Новый год гости, используя каждый по одной принесенной хлопушке, умудрились «захламить» весь дом. Каждая из хлопушек выстреливает N разноцветных шаблонов в виде кругов радиуса R. Определить количество гостей, если известно, что пол квартиры, площадью S=a*b, был покрыт этими кругами в один слой так плотно, как это возможно. Если и осталось какое-то свободное место на полу, то только из-за того, что было недостаточно кругов в последней хлопушке.
Формат входных данных
В первой строке задано число N (0<N<=1000) и радиус кругов R (действительное положительное число <=10). Во второй строке заданы стороны комнаты a и b (1<=a, b <=500).
Формат выходных данных
Вывести одно число – количество гостей.
Примеры
| input.txt | output.txt |
| 10 0.5 3 4 | |
| 1 5 10 10 | |
| 11 0.5 5 4 |
Задача F. Подарок
На Новый год каждый ребенок хочет, чтобы Дед Мороз принес им и своим друзьям подарки. Он просит об этом в своих открытках для Деда Мороза. Дед Мороз очень любит детей и он готов собрать новогодние подарки в один мешок и принести им и их друзьям. Для Деда Мороза не существует понятие стоимости или цены подарка. Количество детей, пославших открытку Деду Морозу, может быть меньше чем общее количество детей, для которых нужны подарки. Если Дед Мороз попросит, то ребенок может отказаться от своего подарка в пользу подарка друга, но сам дарит друзьям только выбранные им самим подарки. Ребенок так же может отказаться от подарка друга, если Дед Мороз принес ему подарок, который он попросил для себя в открытке.
Дед Мороз старый, поэтому ему тяжело донести все подарки детям. Поэтому он подбирает свой бесценный груз так, чтобы общий вес был не больше указанного и чтобы подарок получил каждый ребенок и только один. Помогите Деду Морозу собрать мешок. Если это сделать невозможно, то сообщить ему: «Impossible, sorry!».
Формат входных данных
В первой строке задано число N (integer>0) – количество детей, и S – предельный вес новогодних подарков. В каждой последующей строке указан вес подарка и через пробел имена детей: первым в списке – имя отправившего открытку, затем список его друзей. Имена детей в списке не повторяются.
Формат выходных данных
Если вес мешка с подарками для детей не больше веса указанного предела, то вывести этот вес с точностью до 4 знака после запятой, иначе вывести «Impossible, sorry!»
Примеры
| Входные данные | Выходные данные |
| 50 50.5 10.5 Kat Sasha Olga Valentina 5.8 Sasha Kat 6.7 Mariya Sasha Olga | 35.5000 |
| 1 1.9999 10 Viktor | Impossible, sorry! |
Задача F. Снегурочка (1 сек.)
Под Новый год Дед Мороз должен найти свою внучку Снегуручку. Он решил отправить ей открытку с новогодними поздравлениями. Но он не знает, где она может быть. Так как Снегурочка все равно будет во всех городах Земли, то открытка когда-нибудь дойдет до нее. Ему хотелось бы, чтобы это произошло как можно быстрее. Для этого он должен знать хотя бы название города и его индекс. Тогда Дед Мороз решил воспользоваться случаем. Он открыл карту Земли и ткнул наугад «пальцем в небо». И так он проделал N раз (N – номер Нового года). По последнему выбранному городу он определил индекс этого города и отправил открытку Снегурочке в этот город.
Напишите программу действий Деда Мороза так, чтобы она по введенной переменной N выдавала индекс найденного города.
Формат входных данных (input.txt)
Задано целое число N (integer>0).
Формат выходных данных (output.txt)
Вывести число с шестью цифрами - индекс города.
Примеры
| input.txt | output.txt |
День программиста
C 2009 года наша страна празднует день программиста 13 сентября.
Каким днем недели будет 13 сентября указанного года (начиная с 2009 до 10 000 года нашей эры)? Следует учитывать, что год високосный, если он кратен 4 и при этом не кратен 100, либо кратен 400, например, 2012 и 2400 - високосные года, а 2100 – не високосный. День недели вывести по-английски: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday.
Пример входных данных:
Пример выходных данных:
Sunday
Найди слово «программа»
Дан набор слов, в котором, удалив из него подряд идущие буквы и, может быть, знаки препинания и пробелы, можно найти слово «программа». Выведите те символы, которые нужно удалить, чтобы получить это слово.
Набор слов не превышает 255 символов русского и латинского алфавита, цифр, пробелов и знаков препинаний. Слово «программа» может быть как на русском, так и на английском языке (program), прописными или строчными буквами. Если слово найти не удалось, то ничего не выводить.
Например, в строке: «I am product Grandfather and my Mother. My name is Lena.» нужно удалить следующие символы: «I am duct ndfather and y Mother. My name is Lena.», чтобы получить слово «proGram».
Пример входных данных:
I am product Grandfather and my Mother. My name is Lena.
Пример выходных данных:
I am duct ndfather and y Mother. My name is Lena.
Правильный код
Новый программист написал программу для нахождения суммы первых N (от 1 до 10 000) натуральных чисел, но для некоторых значений ответ получил не верный.
| Pascal | C++ |
| var S: shortint; I: byte; N:Word; begin s:=0; read(n); for I:=1 to n do begin s:=s+I; end; writeln(s); end. | #include int main(){ short int S; unsigned short int I; unsigned int N; cin>>N; S=0; for (I=1;I cout<<S; return 0; } |
Минимально исправьте код программы, чтобы выводился правильный результат.
Пример входных данных:
Пример выходных данных:
Задача 5. Количество слов
Ограничение по времени: 1 с.
Будем считать, что слово – это набор символов, отделенных некоторым непустым количеством символов, обозначающих разделитель между словами. Задана непустая строка из таких символов-разделителей. Определить количество слов в тексте.
Входные данные
В первой строке задана строка символов-разделителей (от 1 до 10 символов). Во второй строке - заданный текст (от 0 до 10000 символов).
Выходные данные
Количество слов в строке.
Пример
| Вход | Выход |
| ., межфакультетская олимпиада по программированию |
Задача «Считалка»
Многие дети начинают играть со считалок. Играющий, на которого попадает последнее слово текста, выходит из круга. Предположим, что в кругу стоит N детей. Составить программу, которая выведет номера детей в том порядке, в каком они выходят из круга.
Входные данные: В первой строке задается количество детей (1<N<= 1000). Во второй строке вводится сама строка считалки (количество слов в строке от 2 до 1000, слова состоят не более 25 символов и разделены пробелом, в конце строки стоит точка).
Выходные данные: Вывести через пробел номера детей, которые выйдут из круга по порядку (последний пробел не выводится), а номер голящего (последнего оставшегося в кругу) во второй строке.
Пример входных данных:
Раз два три четыре пять вышел зайчик погулять.
Пример выходных данных:
8 6 5 7 10 3 2 9 4
Отправить по электронной почтеНаписать об этом в блогеОпубликовать в TwitterОпубликовать в Facebook
Главная страница
Подписаться на: Сообщения (Atom)
