Книга “Алгоритмы и программы”
Задачи из главы 2 “Однопроходные алгоритмы”
- В последовательности целых чисел найдите минимальное число и количество его повторений. Решение
Примеры. Вход: -2 -1; выход: -2; 1.
Вход: 3 10 3; выход: 3 2. - На плоскости задан круг с центром в начале координат и набор точек. Его радиус, количество точек и их координаты вводятся с клавиатуры. Найдите точку вне круга, ближайшую к нему. Решение
- Вдоль координатной прямой размещены \(N\) отрезков. Каждый отрезок задается координатами начала и конца \(x_{min}\) и \(x_{max}\). Нужно найти какую-либо точку, принадлежащую всем отрезкам, или сообщить, что таких точек нет. Решение
Примеры.
Вход: 2
0 2
3 7
Выход: no
Вход 3
0 5
-1.5 3
Выход: 2.5 - На координатной плоскости заданы \(N\) прямоугольников, стороны которых параллельны осям координат. Такие прямоугольники называются изотетичными. Каждый прямоугольник задан диапазонами координат \([x_{min}; x_{max}]\) и \([y_{min}; y_{max}]\). Найдите какую-нибудь точку, принадлежащую всем прямоугольникам, или сообщите, что таких точек нет.
- Отрезок последовательности целых чисел образует числа, идущие в ней подряд. Найдите номера чисел, которыми начинается и заканчивается отрезок с максимальной суммой, а также эту сумму. Решение
Примеры.
Вход: -2 -1 0; выход: 2 2 -1.
Вход: 1 2 -3 3 0; выход: 1 2 3. - Солдаты инопланетной армии перед походом строятся в колонну, поворачиваясь к командиру правым или левым боком. По команде они начинают готовиться к движению. Если двое соседних солдат стоят лицом друг к другу, оба за одну секунду разворачиваются на 180o. Развороты разных пар солдат происходят одновременно. Армия сможет начать движение, если в колонне не будет солдат, стоящих лицом друг к другу. По начальному расположению солдат нужно определить, отправится ли когда-нибудь армия в поход, и если да, то через сколько секунд и какое общее количество разворотов выполнят солдаты. Решение
Вход. Последовательность символов “<” и “>” длиной до \(9\cdot 10^4\) в одной строке текста. Символ “<” означает, что солдат стоит лицом налево, “>” – направо.
Выход. Время и общее количество разворотов (через пробел), если армия сможет отправиться в поход, иначе слово “infinite”.
Примеры.
Вход Выход
>><< 3 4
<> 0 0
>><>< 3 5 - Вам нужно разбить бронированные плиты на оборонной башне противника, которая в плане имеет вид \(N\)-угольника. Для каждой стороны известно количество прикрывающих ее плит. Стрельба ведется из специальной двуствольной пушки – она ездит по рельсам вокруг башни и за один выстрел разбивает (по вашему желанию) или две плиты на одной стороне башни, или по одной плите на двух соседних сторонах. Найдите наименьшее число выстрелов, необходимых для разрушения всех плит.
Вход. В первой строке текста – количество тестов \(M\), в каждой из следующих \(M\) строк – тест. Тест задает число сторон \(N (3\le N\le 10^7)\) и \(N\) целых неотрицательных чисел – количества плит на сторонах. Решение
Выход. В одной строке количества выстрелов, разделенные пробелами.
Примеры. Тесту 3 1 3 1 соответствует выход 3, тесту 3 1 2 1 – выход 2, тесту 3 1 0 1 – выход 1. - В строке текста записаны слова, разделенные пробелами в произвольном количестве. Сжатие текста состоит в том, что между словами оставляется по одному пробелу, а после последнего слова пробелы удаляются (пробелы перед первым словом сохраняются). Сжатый текст записать в другой файл. Если строка содержит только пробелы, то все они сохраняются. Решение
- Комментарием в тексте будем называть последовательность символов, которая начинается на “(*”, заканчивается “*)” и не содержит “*)” внутри. Удалите в заданном тексте все комментарии.
- Многочлен с переменной \(x\) записывают, соблюдая такие правила: многочлен состоит из слагаемых со знаками “+” или “-” между ними; каждое слагаемое представляет собой или произведение натурального коэффициента на степень \(x\) (например, \(5*x^2\)), или только степень \(x\) (например, \(x^3\)), или только коэффициент (например, \(7\)); степень записывается в виде \(x\), знак ^, показатель степени (натуральное число); в выражении нет пробелов, после него в конце строки записан один пробел. Вычислите значение многочлена при заданном действительном значении \(x\).
- Последовательность открывающих “(” и закрывающих скобок “)” называется скобочным выражением. Скобочное выражение называется правильным, если: а) скобки сбалансированы и в каждой паре скобка вначале открывается, а затем закрывается; б) скобка закрывается после того, как закрыты все скобки, открытые внутри нее. Выясните, образуют ли скобки правильное выражение.
Вход. Каждая строка текста содержит отдельный текст. Гарантировано, что в строках нет символов, отличных от скобок.
Выход. Строка из символов 0 и 1, соответствующих тестам (1, если выражение в тесте правильно, иначе 0).
Пример. Вход. ()() (())() (())) ())( Выход. 1100 - Заданы две последовательности символов и нужно определить все вхождения первой из них во вторую.
- В последовательности все значения, кроме одного, встречаются четное число раз, а одно – нечетное число раз. Определите это значение.
- Подсчитать количество появлений каждой буквы во входном тексте.
- Из последовательности целых чисел выбрать три числа, произведение которых максимально.
- Заданы \(2n\) положительных целых чисел, которые можно разбить на пары так, что суммы чисел во всех парах одинаковы. Определите, можно ли их разбить на пары так, что произведения чисел во всех парах одинаковы.
- Дана последовательность натуральных чисел. а) Известно, что некоторое число встречается в ней чаще, чем все остальные числа, вместе взятые. Найдите это число. б) Выяснить, существует ли число, которое встречается в ней чаще, чем все остальные числа, вместе взятые. Найдите это число, если оно существует.
- Клиенты приходят к парикмахеру, занимают очередь, если она есть, и стригутся в порядке прихода. Мастер, освободившись, сразу готов к стрижке следующего клиента. Для каждого клиента известна длительность его стрижки \(t\): клиент уходит через \(t\) единиц времени после начала стрижки. Вход. В первой строке текста – количество клиентов \(m\). В каждой из следующих \(m\) строк записана пара целых положительных чисел – момент прихода клиента и длительность его стрижки. Моменты прихода заданы относительно начального момента времени и образуют неубывающую последовательность. Определите моменты ухода.
- В натуральном числе вычеркнуть цифру так, чтобы оставшееся число было как можно больше.
- Текст содержит слова в алфавите \(a, …, z\), разделенные пробелами и знаками пунктуации в произвольном количестве. Слова со строки на строку не переносятся. Знаки пунктуации: “:”, “;”, “.” и “,”. Напишите программу печати текста с удалением однолитерных слов, лишних пробелов и знаков пунктуации.
- Текст содержит символы 0 и 1, последовательность которых считается непрерывной независимо от разбиения текста на строки. Написать программу определения, содержит ли текст образцы из 0 и 1, заданные в отдельных строках длиной не больше 1000. Например, текст, образованный строками 00 и 11, содержит образцы 001 и 011 и не содержит образцов 10 и 111.