Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Вариант 1
Имеется паутина на плоскости, состоящая из нитей, параллельных осям координат. В основе конструкции паутины лежит бесконечное множество вертикальных нитей, пронумерованных слева направо, начиная с единицы. Смежные вертикальные нити могут быть соединены горизонтальными нитями на некоторой высоте. Для каждой вертикальной нити на определенной высоте может быть не более одного подобного соединения. На одной из вертикальных нитей, в самом верху (выше всех горизонтальных соединений) находится паук, который начинает свое движение вниз. Натыкаясь на очередную нить, паук меняет свое направление. Движение паука продолжается до тех пор, пока все горизонтальные нити не окажутся выше паука. По заданной конструкции паутины и начальному расположению паука требуется определить номер нити, на которой окажется паук в конце своего движения.Входные данные
Первая строка входного файла INPUT.TXT содержит два числа K и M, где K – номер нити, соответствующей начальному положению паука. Далее идут M строк, определяющих горизонтальные соединения, по одному в каждой строке. Каждое такое соединение определяется двумя числами P и H, обозначающие соединение смежных вертикальных нитей с номерами P и P+1 на высоте H. Во входных данных все числа натуральные, имеющие следующие ограничения: K, P, H ≤ 109, M ≤ 105.Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
Вариант 2
Последовательность a1, a2, a3, … , an-1, an называется пилообразной, если она удовлетворяет одному из следующих условий: 1) a1 < a2 > a3 < … > an-1 < an 2) a1 < a2 > a3 < … < an-1 > an 3) a1 > a2 < a3 > … < an-1 > an 4) a1 > a2 < a3 > … > an-1 < an Дана числовая последовательность. Требуется определить длину самой длинной ее пилообразной непрерывной подпоследовательности.Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число N – количество элементов последовательности. Во второй строке файла через пробел записаны N элементов целочисленной последовательности {ai}. Ограничения: N<106, |ai| < 32000.Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — длину самой длиной непрерывной пилообразной подпоследовательности.Вариант 3
В соревнованиях по прыжкам с шестом было замечено одно интересное явление: на очередном этапе соревнований успешные и неуспешные попытки прыжков чередовались: успешный, неуспешный, успешный, неуспешный и т.д. (первый был успешным). Спортсменам разрешалась только одна попытка. Тот, кто преодолевал планку, переходил в следующий тур (этап), а тот, кто делал неудачную попытку – выбывал из соревнований. Таким образом, первым выбывал всегда спортсмен с номером 2, а последним – победитель с номером 1. Требуется написать программу, которая по количеству участников и номеру спортсмена вычислит, каким по счету данный спортсмен выбыл из соревнований.Входные данные
В единственной строке входного файла INPUT.TXT содержатся два натуральных числа: общее число спортсменов N и порядковый номер спортсмена в стартовом списке M. Числа разделены пробелом (1 ≤ M,N ≤ 109).Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести каким по счету спортсмен M выбыл из соревнований. Если это победитель состязания, то выводится число N.Вариант 4
Парламент некоторой страны принял новый закон о праздничных днях. Согласно этому закону первые K дней года, а также 23 февраля и 8 марта объявляются праздничными, а все остальные праздники отменяются. При этом все выходные (суббота и воскресенье), попавшие на праздничные дни, переносятся на следующие за этими праздниками рабочие дни. В зависимости от того, на какой день недели приходится 1 января, количество нерабочих дней, которые идут подряд, может меняться. Требуется определить, какое наибольшее количество нерабочих дней может идти подряд.Входные данные
Во входном файле INPUT.TXT записано единственное число K (1 ≤ K ≤ 50).Выходные данные
В выходной файл OUTPUT.TXT требуется записать единственное число — наибольшее количество нерабочих дней, идущих подряд.Вариант 5
Простым числом будем называть натуральное число, большее единицы и делящееся только на единицу и на само себя. Выпишем все простые числа в порядке возрастания и i-ое в этом порядке число обозначим pi (число 2 при этом будет иметь номер 1). Так, например, p1 = 2, p2 = 3, p3 = 5, p52 = 239. Скажем, что число pi является сверхпростым, если i = pk для некоторого k. Иными словами, сверхпростое число — это простое число, номер которого в списке простых чисел, упорядоченном по возрастанию, является простым числом. Дано натуральное число k. Упорядочим все сверхпростые числа по возрастанию. Найдите k-ое сверхпростое число в этом порядке.Входные данные
Входной файл INPUT.TXT содержит натуральное число k (1 ≤ k ≤ 500).Выходные данные
В выходной файл OUTPUT.TXT выведите k-ое сверхпростое число.Вариант 6
Знаменитый химик Д. И. Менделеев, будучи директором Главной палаты мер и весов, интересовался задачей составления набора гирь, чтобы с их помощью можно было взвесить любой груз. Выяснилось, что если при взвешивании груза класть гири и на левую и на правую чашки весов, то самым удобным является набор гирь в троичной системе. Для взвешиваний используют чашечные весы и большой набор гирь 1, 3, 9, 27, 81 грамм и т.д. (для любого k ≥ 0 есть только одна гиря весом 3k грамм). На одну из чашек весов положили груз весом N грамм. Какие гири нужно положить на левую и правую чашки, чтобы их уравновесить?Входные данные
Входной файл INPUT.TXT содержит символ C и число N, разделенные пробелом. C — символ «L» или «R», обозначающий соответственно левую или правую чашку весов, на которой лежит груз. N – масса груза в граммах (1 ≤ N ≤ 109).Выходные данные
В выходной файл OUTPUT.TXT выведите две строки: первая строка должна начинаться с «L:», вторая – с «R:», после чего через пробел должны идти в порядке возрастания массы веса гирь, которые нужно положить на левую и правую чашу весов, соответственно.Вариант 7
Дано N целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. С данными числами произвели указанную операцию таким образом, что осталось минимально возможное количество чисел. Требуется написать программу для определения этого количества.Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральные числа L и N (N ≤ 100, L ≤ 3200), во второй строке N чисел (в диапазоне от -32768 до 32767), записанных через пробел.Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – ответ на задачу.Вариант 8
Задано n чисел a1, a2, … , an. Выберите из них четные числа, у которых третья справа цифра в их представлении в восьмеричной системе счисления нечетна. Выбранные числа отсортируйте по неубыванию и выведите в выходной файл.Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 105). Вторая строка входного файла содержит n целых чисел: a1, a2, … , an. Они отделены друг от друга пробелами и заданы в десятичной системе счисления. Для всех i (1 ≤ i ≤ n ) верно неравенство 64 ≤ ai ≤ 109.Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите количество k искомых чисел. Во второй строке выведите эти числа в указанном порядке в десятичной системе счисления.Вариант 9
Требуется вычислить факториал целого числа N. Факториал обозначают как N! и вычисляют по формуле: N! = 1 * 2 * 3 * … * (N-1) * N, причем 0! = 1. Так же допустимо рекуррентное соотношение: N! = (N-1)! * NВходные данные
В единственной строке входного файла INPUT.TXT записано одно целое неотрицательное число N (N < 1000).Выходные данные
В выходной файл OUTPUT.TXT нужно вывести одно целое число — значение N!.Вариант 10
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички. Напишите программу, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.Входные данные
В единственной строке входного файла INPUT.TXT записано одно целое число N (1 ≤ N ≤ 109).Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – минимальное количество спичек, требуемых для составления заданного количества квадратов.Вариант 11
Назовем перестановку из N чисел 1…N K-перестановкой, если любые два соседних в ней элемента отличаются не более, чем на K. Требуется найти число K-перестановок из N чисел от 1 до N.Входные данные
Входной файл INPUT.TXT содержит натуральные числа N и K (K ≤ N ≤ 9).Выходные данные
В выходной файл OUTPUT.TXT выведите целое число — ответ на задачу.Вариант 12
Задан ряд последовательных натуральных чисел от M до N (M < N), из которого удаляют сначала все числа, стоящие на нечетных местах. Затем, из оставшегося ряда удаляют все числа, стоящие в нем на четных местах. Эти действия повторяют до тех пор, пока не останется одно число. Требуется написать программу, которая находит оставшееся число.Входные данные
Входной файл INPUT.TXT содержит число M в первой строке и число N во второй (M < N < 109).Выходные данные
В выходной файл OUTPUT.TXT выведите оставшееся число.Вариант 13
Вам поручена реализация утилиты, которая будет обрабатывать HTML-документы старых версий и подсчитывать в них количество символов каждого размера. HTML-документ состоит из обычного текста и тегов — управляющих элементов, заключенных в угловые скобки. Для управления размером шрифта используется тег font с атрибутом size: <font size=»x»>. Если x — натуральное число, то размер шрифта устанавливается равным x. Кроме того, x может иметь вид +y или -y, где y — целое положительное число. В этом случае размер шрифта соответственно увеличивается или уменьшается на y. Действие тега заканчивается с появлением соответствующего закрывающего тега </font>. Все остальные теги вы не должны обрабатывать. Можете считать, что теги не содержат лишних пробельных символов. По умолчанию размер шрифта равен 10, и изменения не будут выводить его из интервала от 1 до 50.Входные данные
Входной файл INPUT.TXT содержит описание HTML-документа, по длине не превосходящее 5000 символов.Выходные данные
В выходной файл OUTPUT.TXT выведите для каждого шрифта, которым был написан хотя бы один непробельный символ, на отдельной строке через пробел его размер и количество соответствующих ему непробельных (с ASCII кодами не равными 9, 10, 13 и 32) символов в порядке возрастания размера.Вариант 14
Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.Входные данные
В первой строке входного файла INPUT.TXT находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка — сегмент со стеной. Размер сегментов – 5х5 метров, высота стен – 5 метров. (3 ≤ N ≤ 50)Выходные данные
В выходной файл OUTPUT.TXT выведите одно число — площадь видимой части внутренних стен лабиринта в квадратных метрах.Вариант 15
(Время: 1 сек. Память: 16 Мб Сложность: 49%) Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть задана строка, в которой записано слово S, состоящее из N букв английского алфавита. Путем вычеркивания из этого слова некоторого набора символов, можно получить строку, которая будет палиндромом. Требуется написать программу, с помощью которой можно определить, сколько существует способов вычеркивания из заданного слова некоторого (возможно пустого) набора символов, чтобы образованная таким образом строка была палиндромом. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми.Входные данные
В первой и единственной строке входного файла INPUT.TXT записано слово S, состоящее из N символов (1 ≤ N ≤ 30).Выходные данные
В выходной файл OUTPUT.TXT выведите найденное число способов.Вариант 16
Некоторые наборы из n слов длины n обладают интересным свойством — их можно расположить в клетках квадрата n×n так, что все слова набора можно прочитать как в вертикали, так и по горизонтали. Примером такого набора слов является {«DATE», «FIND», «IDEA», «NEXT»}. Их можно расположить так: Заметьте, что каждое слово можно прочитать как по горизонтали, так и по вертикали. Такие квадраты называются словарными квадратами, наибольший известный словарный квадрат в английском языке имеет размер 10×10. Рассмотрим еще один пример словарного квадрата: Вам даны такие 2n слов, что из них можно построить два различных словарных квадрата размера n×n. Ваша задача состоит в том, чтобы разбить эти слова на две группы, по n слов в каждой, и построить из слов каждой группы словарный квадрат. Гарантируется, что все данные вам слова являются английскими словами (некоторые из них могут быть достаточно редкими словами, именами, или специальными терминами).Входные данные
Первая строка входного файла INPUT.TXT содержит целое число n (2 ≤ n ≤ 10). Каждая из следующих 2n строк содержит слово, состоящее из заглавных букв английского алфавита. Каждое слово содержит ровно n букв.Выходные данные
В выходной файл OUTPUT.TXT выведите два словарных квадрата, построенных из данных слов. Разделите квадраты пустой строкой.Вариант 17
Произошло радиоактивное заражение местности. Составлена карта зараженности. Она представляет собой прямоугольную таблицу N×M, в клетках которой записана зараженность соответствующего участка. Требуется написать программу, которая найдет путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации.Входные данные
Входной файл INPUT.TXT содержит в первой строке числа N и M, а в следующих N строках – по M чисел – карта зараженности местности. Числа в строках разделяются одним пробелом. 1 ≤ N ≤ 30, 1 ≤ M ≤ 30, зараженность участка – целое число от 0 до 100.Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – суммарную долю радиации.Вариант 18
Ядро операционной системы содержит в себе строку S длиной N символов. Генерация пароля происходит с использованием символов строки S. Паролем будем называть подстроку Si,j строки S длиной не менее одного и не более N символов. Подстрокой Si,j строки S называется строка, последовательно составленная из символов S[i], S[i+1], S[i+2], … , S[j-1], S[j]. Символы в строке нумеруются последовательно начиная с единицы. Пароль Si,j считается защищенным, если в нем встречается не более K одинаковых символов. Вашей задачей является по заданной строке S и числу K определить количество различных вариантов выбора защищенного пароля. Два варианта выбора пароля S1i,j и S2i’,j’ называются различными, если i ≠ i’ или j ≠ j’.Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N (1 ≤ N ≤ 106) и K (1 ≤ K ≤ N), разделенных одиночным пробелом, где N – количество символов в строке S; K – максимальное количество одинаковых символов в пароле. Вторая строка входного файла содержит ровно N символов. Каждый символ является либо маленькой английской буквой, либо цифрой. Каждая строка входного файла заканчивается символом перевода строки.Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число – количество вариантов выбора защищенного пароля.Вариант 19
Числа Фибоначчи F1, F2, … определяются начальными значениями и соотношением: F1=1; F2=2; Fn=Fn-1+Fn-2. Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом. Требуется написать программу, которая по двум заданным строкам, представляющим числа A и B в системе счисления Фибоначчи, находила строку, представляющую число A+B также в этой системе счисления. Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.Входные данные
Входной файл INPUT.TXT в первой строке содержит число A и B во второй. Длина записи чисел A, B и их суммы A+B в системе счисления Фибоначчи не превышает 255 знаков.Выходные данные
В выходной файл OUTPUT.TXT выведите значение суммы A+B в системе счисления Фибоначчи.Вариант 20
Перестановка (P0, P1, …, PN−1) чисел от 0 до N−1 называется антиарифметической, если не существует такой тройки индексов 0 ≤ i < j < k < N, что тройка Pi, Pj, Pk образует три последовательных члена некоторой арифметической прогрессии. Например, перестановка (3, 1, 0, 4, 2) антиарифметическая, а (0, 4, 5, 3, 1, 2) – нет (так как 0, 1, 2 – арифметическая прогрессия). Ваша задача по заданному значению N построить любую антиарифметическую перестановку.Входные данные
Входной файл INPUT.TXT содержит целое число N (3 ≤ N ≤ 50000).Выходные данные
В выходной файл OUTPUT.TXT выведите любую антиарифметическую перестановку длины N или -1, если такой нет.Вариант 21
Для ускорения прохождения «коротких» заданий на ЭВМ выбран пакетный режим работы с квантованием времени процессора. Это значит, что всем заданиям пакета по очереди представляется процессор на одинаковое время 10 с (круговой циклический алгоритм разделения времени). Если в течение этого времени заканчивается выполнение задания, оно покидает систему и освобождает процессор. Если же очередного кванта времени не хватает для завершения задания, оно помещается в конец очереди — пакета. Последнее задание пакета выполняется без прерываний. Пакет считается готовым к вводу в ЭВМ, если в нем содержится K заданий. Новый пакет вводится в ЭВМ после окончания обработки предыдущего. Задания поступают в систему с интервалом времени 60 ± 30 с и характеризуются временем работы процессора 50 ± 45 с. Требуется смоделировать процесс обработки N заданий и определить время начала и окончания каждого процесса.Входные данные
На первой строке входного файла INPUT.TXT находятся числа N и K — число процессов и количество процессов в пакете (1 ≤ N ≤ 1000, 1 ≤ K ≤ 100). Гарантируется, что N делится на K. Далее следуют N строк с информацией о времени формирования и необходимое время на выполнение для каждого процесса. Все процессы стартуют в один день и следуют в порядке возрастания времени ввода их в систему.Выходные данные
Выведите в выходной файл OUTPUT.TXT для каждого процесса в отдельной строке время его старта и время окончания через пробел в формате ЧЧ:ММ:СС.Вариант 22
Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333. Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь приведенной справа таблицей. В этой таблице символами «а», «b», «с» обозначены различные цифры. Например, под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888». Пользуясь предложенной оценкой, найдите наиболее красивое разбиение заданного номера.Входные данные
Входной файл INPUT.TXT содержит одну строку из 7 цифр – заданный телефонный номер.Выходные данные
Выведите в первой строке выходного файла OUTPUT.TXT наиболее красивое разбиение номера, а во второй – величину его красоты. Если разбиений с максимальной величиной красоты несколько, выведите в выходной файл любое из этих разбиений.Вариант 23
Внутри адронного коллайдера образовалось N разновидностей новых частиц в количестве A1, … ,AN единиц каждая. Большая часть новых частиц, однако, успевает прореагировать между собой раньше, чем эти частицы сможет уловить детектор, поэтому физикам очень важно предсказать конечный итог реакции между частицами. Для простоты будем считать, что в реакции участвуют 2 частицы, с одним из следующих результатов, в зависимости от типа:-
- Первая частица уничтожает вторую
- Частицы отскакивают друг от друга без какого-либо вреда
Входные данные
В первой строке входного файла INPUT.TXT задано количество видов частиц N (1 ≤ N ≤ 4). В следующей строке записаны N чисел, определяющие начальное количество частиц каждого типа Ai (1 ≤ Ai ≤ 2). Следующие N строк формируют матрицу B[N][N] из чисел 0 и 1. Ненулевое значение ячейки Bij указывает, что частица типа i при столкновении уничтожает частицу типа j. Если Bij не ноль и Bji не ноль, то в результате взаимодействия уничтожается либо частица i, либо частица j, но не обе сразу.Выходные данные
В первой строке выходного файла OUTPUT.TXT следует вывести количество возможных исходов K. В каждой из последующих K строк должно содержаться описание исхода эксперимента в формате исходного файла.Вариант 24
Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки. XML-строка состоит из открывающих и закрывающих тегов. Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв английского алфавита, а затем закрывающая угловая скобка (>). Примеры открывающих тегов: <a>, <dog>. Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв английского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>. XML-строка называется корректной, если она может быть получена по следующим правилам:- Пустая строка является корректной XML-строкой.
- Если A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
- Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв английского алфавита.
Входные данные
Входной файл INPUT.TXT содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы английского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47). Строка во входном файле заканчивается переводом строки.Выходные данные
В выходной файл OUTPUT.TXT должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.Вариант 25
Рассмотрим перестановочный шифр, называемый «Решетка» («перестановочный» означает, что символы, составляющие послание, не изменяются, но меняются местами). Суть его заключается в следующем. Выбирается четное число n, затем в квадрате n×n вырезается n2/4 клеток. При этом клетки выбираются так, что если наложить решетку на квадрат n х n, и затем последовательно развернуть ее на 90, 180 и 270 градусов, то каждый раз квадратики, совмещенные с вырезанными клетками, будут различны. Такой квадрат n×n называется «правильным ключом». Ваша задача посчитать количество «правильных ключей». Так как это число может быть очень большим, мы предлагаем Вам найти его значение по модулю m. Ключи, получаемые поворотом на 90, 180 и 270 градусов считаются различными.Входные данные
Входной файл INPUT.TXT содержит целые числа n и m (2 ≤ n, m ≤ 106), n — четно.Выходные данные
В выходной файл OUTPUT.TXT выведите количество «правильных ключей» размером n×n по модулю m.
О сайте
Ссылка на первоисточник:
http://www.niro.nnov.ru
Поделитесь в соцсетях: