Информатика

1 132 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
24641#24641
Одновременную работу с несколькими типами информации в интерактивном режиме предоставляет 

1. интерактивная программа управления
2. программа монтажа
3. мультимедиа технология
4. технология интерактивности
Как вы уже знаете, Вупсень очень любит давать задачи на поиск наибольшей общей подпоследовательности, а Пупсень очень любит давать задачи на поиск наибольшей правильной скобочной подпоследовательности. Лунтик решил обрадовать своих друзей и подарить им на новый год две строки. Конечно же, Вупсень и Пупсень сразу, не посмотрев на строки, захотели дать задачу на поиск наибольшей общей правильной скобочной подпоследовательности, но не тут то было: в этих строках не было скобок. Лунтик понимал, что если Вупсень и Пупсень увидят решения с битсетами, то будут грустить, и весь праздник испортится, поэтому он придумал другую задачу: найдите длину наибольшего общего подпалиндрома.

Подпалиндромом называется такая попоследовательность строки, которая читается справа налево также, как и слева направо.
 
Формат входный данных
В первой строке дана строка s, во второй строке строка t, состоящие из строчных латинских букв. 1 <= |s|, |t| <= 50.
 
Формат выходных данных
Выведите одно целое число n - длину наибольшей общей подпоследовательности, являющейся палиндромом.
 
Примеры
Ввод Вывод
mem
kek
1
acab
abca
3
(с) Буков Антон, 11и
Ни для кого не секрет, что Дед Мороз передвигается на особом транспортном средстве, принцип которого известен только самым приближенным зайцам Дедам Мороза. Однако, зайцы немного слабы в составлении маршрутов, и вам придется помочь им.

Принцип работы транспортного средства Деда Мороза(в дальнейшем ПепеЛАЦ(Пепе Летающий агрегат Цвайхандер)) такой:
на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).
Деду Морозу необходимо добраться из точки (x1, y1) в точку (x2, y2). Помогите зайцам Деда Мороза составить маршрут, чтобы ему меньше пришлось ходить по заснеженному лесу.
Поскольку перемещения мгновенные и абсолютно бесплатные(магия же), то минимизировать количество перемещений не надо.

Формат входного файла
Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по
абсолютной величине.

Формат выходного файла
Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке. Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры

Ввод Вывод
3 1
3 -3
-A   
+B
+B
0 0
3 0
-B
+B

 (с) Павел Колодкин, 12И
Жюри составило отчет об учебно-тренировочных сборах по информатике и собирается распечатать его на стандартном листе бумаги. Весь отчет набран одним моноширинным шрифтом, т.е. все символы (включая пробелы) имеют одинаковую ширину. Длина строки при печати этим шрифтом на листе бумаги равна S.
 
Назовем пустотой последовательность пробелов между соседними словами в строке, а также от начала строки до первого слова в ней и от последнего слова в строке до конца строки. Проблема, стоящая перед жюри, состоит в том, что научный руководитель сборов Владимир Михайлович Кирюхин отказывается читать текст, если сумма кубов длин пустот по всем строкам не минимальна. Помогите жюри расположить отчет на листе бумаги так, чтобы В.М. Кирюхин согласился его прочесть и утвердить результаты сборов.
 
Для достижения требуемого расположения текста на бумаге разрешается заменять произвольную пробельную последовательность (т.е. непустую последовательность подряд идущих пробелов или символов перевода строки) любой другой пробельной последовательностью.
 
Входные данные
Первая строка входного файла содержит целое число S (1<=S<=80). 
В последующих строках записан отчет, содержащий не более 500 слов. 
Длина каждой строки отчета не превосходит 250 символов, а длина каждого слова не превос-ходит S.
 
Выходные данные
Вывести в первую строку выходного файла минимально возможную сумму 
кубов пустот по всем строкам. В последующие строки следует вывести 
искомое расположение текста на листе бумаги.
 
Пример входного файла
30
Победители летних учебно-тренировочных сборов по информатике 1997 г.:
Владимир Мартьянов,
Анатолий Пономарев,
Николай Дуров,
Андрей Лопатин.
 
Пример выходного файла
325
     Победители     летних    
учебно-тренировочных сборов по
 информатике 1997 г.: Владимир
Мартьянов, Анатолий Пономарев,
Николай Дуров, Андрей Лопатин.
 
23531#23531
Как определяется понятие информации согласно антропометрической философской концепции?

1. информация и информационные процессы присущи только живой природе и являются ее функцией
2. информация и информационные процессы присущи только человеку
3. информация - фундаментальное понятие
4. информация - всеобщее свойство материи
В городе будущего Иннополис еще во всю идет стройка, но уже сейчас построено n зданий. Крышу каждого здания можно представить как прямоугольник со сторонами, параллельными осям координат. Никакие здания не касаются и не пересекаются.

Инна любит гулять по крышам. Она стоит на крыше здания с номером 1 и хочет попасть на крышу здания с номером n.

Инну можно представить как точку на плоскости. Она может перемещаться по крыше, не выходя за ее границы, но не может находиться на границе крыши. Также она умеет прыгать с крыши на крышу, но только в направлениях, параллельных осям координат. В целях безопасности Инна не может перепрыгивать здания, то есть в любой момент прыжка под ней не должно находиться здание.

Помогите Инне посчитать, какое минимальное количество раз она должна прыгнуть с одной крыши на другую, чтобы попасть на здание с номером n.

Формат входных данных
В первой строке задано натуральное число n — число зданий в Иннополисе (n<= 105). В следующих n строках заданы крыши зданий. Каждая из этих строк содержит четыре целых числа xi1, yi1, xi2 и yi2 — координаты противоположных вершин прямоугольника, описывающего крышу здания (xi1 < xi2; yi1 < yi2) Гарантируется, что никакие два прямоугольника не имеют общих точек. Все координаты — неотрицательные целые числа и <= 109

Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которые Инна должна совер- шить, чтобы добраться с крыши здания 1 до крыши здания n. Если же Инна не может добраться до крыши n-го здания, выведите -1.
Ввод Вывод
4
0 0 3 2
1 6 4 8
1 3 4 5
7 7 10 9
3
3
0 0 3 2
1 3 4 5
7 7 10 9
-1
На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа облада- ет развитой транспортной системой: в Европе есть V интересующих Петра городов и E маршрутов ночных поездов. Каждый маршрут соединяет два различных города, время в пути составляет одну ночь. Поезда по маршруту ходят в обоих направлениях.

Основной целью поездки Петра является осмотр местных достопримечательностей. Поскольку Петр — невероятно занятой человек, то он решил, что все путешествие должно занимать не более четырех дней. Петр уже многое повидал, поэтому на осмотр досто- примечательностей в каждом городе Петр тратит ровно один день. Он хочет составить наиболее практичный тур: каждый день он будет тратить на осмотр города, а каждую ночь — на переезд ночным поездом между городами. Разумеется, Петр не имеет ни ма- лейшего желания посещать один город несколько раз.

Но на этом прагматичность Петра не заканчивается: Петр, как настоящий турист, хо- чет посмотреть на самые красивые европейские достопримечательности. Он долго изучал справочники и для каждого города оценил свою ожидаемую радость от его посещения pi. Теперь он хочет найти маршрут, при котором его радость будет наибольшей. Помогите Петру найти такой маршрут.

Формат входного файла
В первой строке входных данных заданы два целых числа V и E (1 <= V, E <= 3 · 105 ) — количество городов и маршрутов поездов, соответственно. В следующей строке заданы V целых чисел pi (1 <= pi <= 108 ), где pi обозначает ожидаемую радость от посещения го- рода с номером i. В следующих E строках заданы описания маршрутов поездов. Каждое описание состоит из пары различных чисел ai и bi (1 <= ai, bi <= V ) — номеров городов, меж- ду которыми курсирует этот маршрут поезда. Гарантируется, что между каждой парой городов существует не более одного маршрута поезда.

Формат выходного файла
В первой строке выходных данных выведите число K (1 <= K <= 4) — количество горо- дов в оптимальном маршруте туриста Петра. В следующей строке выведите номера этих городов в порядке посещения. Города нумеруются начиная с единицы. Если оптимальных маршрутов несколько, выведите любой из них.
Ввод Вывод
5 4
4 2 3 1 5
1 2
2 3
3 4
4 5
4
2 3 4 5
4 3
1 2 3 4
1 2
1 3
1 4
3
4 1 3
✓ 0✗ 151 200средняяВойти и решать
Ваня хочет поехать в школу,куда от его квартиры идёт только шестой трамвай. Проблема в том,что Ваня очень стеснительный и боится садиться 
в трамвай,если в нём больше d человек.Известно,что трамваи идут раз в k минут.Ваша задача состоит в том,чтобы посчитать количество минут,которые простоит Ваня на остановке, 
учитываю Ванину стеснительность:если есть такой пустой трамвай,который идёт Васе,он будет ждать его сколько угодно.Если же таких трамваев несколько,то он,разумеется,сядет на 
тот,что придёт раньше.Если данные введены некорректно,вывести "Absent"; 
Так же известно,что Ваня приходит на остановку в тот момент времени,когда к ней подъезжает первый трамвай
Входные данные: 
Сначала вводятся два числа d и k такие,что 0<=d<=100 и 0<=k<=100. 
Затем вводится t строк(0<=t<=100,само число t нам неизвестно),заканчивающихся одним числом -1 по 2 числа в каждой- количество людей в трамвае и его номер 
Вывод: 
В выводе должно быть одно число-количество минут,которые Ваня простоит на остановке в ожидании трамвая,или же слово "Absent"

(c) Васильев Алексей
По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали n кружек. Геральд суетился и переставлял кружки с l по r в позицию i, Ламберт с упоением доливал Ривский эль в кружки с l по r по s литров в каждую, а вот Эскель , пока никто не видит, выпивал или доливал в каждую кружку с l по r столько, чтобы в них осталось ровно по k литров в каждой. Спустя почти час Йеннифер, которой порядком надоела брань Ламберта и Эскеля, спустилась вниз, чтобы узнать причину шума. После небольшой перепалки Йеннифер решила помочь отнести кружки в главную столовую, где бурное веселье ведьмаков не мешало бы ей спать. Но так как кружки очень тяжелые, то она может унести не более l литров. Естественно, она хочет пойти спать как можно быстрее, а значит собирается унести как можно больше эля, но общим весом не более l.

Помогите Йеннифер узнать, какой максимальный вес и количество кружек с таким весом она может унести?

Формат входных данных
Дано число n(1 <= n <= 10^4) количество кружек и q(1 <= q <= 10^4) – количество операция. Далее идет описание операций(1 <= l <= r <= 10^4)
G l r i - Геральд переставляет кружки с l по r в позицию I (1  <= I <=10^4+1)(вставка отрезка производится перед указанным индексом)
L l r s - Ламберт доливает в кружки с l по r по s литров (1 <= s <= 10^3)
E l r k – Эскель выпивает из кружек с l по r так, чтобы в каждой оказалось по k литров (1 <= k <= 10^3)
Затем на новой строке идет число l(1 <= l <= 10^5) – количество литров которые может унести Йеннифер. 
Изначально в кружках по 0 литров.

Формат выходных данных
На первой строке через пробел вывести последовательность кружек после проделанных операций, а на второй строке максимальное количество кружек, которые сможет унести Йеннифер и их общий вес. 
 
Пример входных данных Пример выходных данных
5 7
L 2 5 10
G 1 3 5
L 1 4 3
L 3 3 4
E 2 3 2
E 2 2 4
E 5 5 15
15
13 4 2 13 15
2 15
 
 
5 6
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
10
5 1 2 3 4
4 10
5 8
E 1 1 1
E 2 2 2
E 3 3 3
E 4 4 4
E 5 5 5
G 5 5 1
G 1 1 6
G 1 5 1
10
1 2 3 4 5
4 10

Пояснения к 1 примеру
1. 0 10 10 10 10
2. 10 0 10 10 10
3. 13 3 13 13 10
4. 13 3 17 13 10
5. 13 2 2 13 10
6. 13 4 2 13 10
7. 13 4 2 13 15
Йеннифер может унести 15 литров. Это значит что она может взять либо одну кружку (15 литров или 13 литров), либо две кружки(4 и 2 литра или 13 и 2 литра). Так как она хочет унести как можно больше кружек, то ответ 2.
Пояснения к 3 примеру
1. 1 0 0 0 0
2. 1 2 0 0 0
3. 1 2 3 0 0
4. 1 2 3 4 0
5. 1 2 3 4 5
6. 5 1 2 3 4
7. 1 2 3 4 5
8. 1 2 3 4 5
Йеннифер может унести 10 литров. Наилучший вариант будет 4 и 3 и 2 и 1 литр. Ответ 4.

(с) Аксенов Владимир 10и
На протяжении многих лет Вася работает программистом в одной очень большой и очень из- вестной компании. Эта компания обеспечивает своих сотрудников всем необходимым для приятной и плодотворной работы: бесплатными обедами, транспортом от дома до места работы и многим, многим другим. И вот в один прекрасный солнечный день Вася понял, что ему очень наскучил вид из окна его офиса, и ему нужно, чтобы за окном было что-то новое и прекрасное. А что может быть лучше чудесного горного пейзажа? Придя к этой мысли, Вася попросил своего менеджера подобрать себе новый офис с красивым видом на горы.

В той местности, где располагается офис Васи, каждая гора принадлежит некоторой горной цепи. Так как Васе хочется, чтобы вид из окна его офиса был идеальным, то он попросил подобрать себе такой офис, чтобы никакие две горные цепи, видимые из окна, не пересекались. Менеджер Васи нашел прекрасный новый офис, из которого видно N горных цепей, но он никак не может определить, понравится ли Васе вид из окна этого офиса. Помогите ему!

Более формально, вид из окна офиса представляет собой набор горных цепей, пронумерованных от 1 до N, где горная цепь с номером i представляет собой ломаную на плоскости из li звеньев с вершинами в точках (xi,j , yi,j ), причем для любых i, j выполнено xi,j < xi,j+1.

Кроме этого, окно в офисе имеет фиксированную ширину, поэтому все горные цепи начинаются и заканчиваются на одной вертикали, то есть существуют такие числа A и B, что для любого номера i горной цепи выполнено xi,0 = A, xi,li = B.

Отметим, что из определения горной цепи следует, что для любого значения абсциссы A <= x <= B на ломаной с номером i существует единственная точка (x, yi(x)) с этим значением абсциссы, при- надлежащая этой ломаной. Будем говорить, что горная цепь i находится строго выше горной цепи j в точке x, если выполнено строгое неравенство yi(x) > yj (x).

Естественно считать, что цепь под номером i пересекается с цепью под номером j, если су- ществуют такие два значения абсциссы x1, x2, что цепь i находится строго выше цепи j в точке x1, но при этом цепь j находится строго выше цепи i в точке x2, то есть выполнены неравенства yi(x1) > yj (x1) и yj (x2) > yi(x2). Обратите внимание на поясняющие рисунки, расположенные в примечании к задаче.

Вам необходимо определить, подойдет ли подобранный офис Васе, и, если нет, то найти любую пару пересекающихся горных цепей.

Формат входных данных 
В первой строке входных данных через пробел идут два целых числа: A и B (−109<=A < B<=109 ).
Во второй строке входных данных находится единственное число N — количество горных цепей, видимых из окна подобранного менеджером Васи офиса (1 <= N <= 100 000).
Далее следуют описания N горных цепей. В первой строке i-го описания содержится число li => 1 — количество звеньев ломаной, из которых состоит соответствующая горная цепь. В следую- щих li + 1 строках описания содержатся два целых числа — координаты (xi,j , yi,j ) вершин ломаной (0 <= j <= li). Суммарное число звеньев всех ломаных не превосходит 200 000.
Гарантируется, что для каждой горной цепи вершины соответствующей ей ломаной идут во входных данных в порядке возрастания абсциссы, причем для любого i выполнено xi,0 = A, xi,li = B.

Формат выходных данных 
Если же офис подходит Васе, то есть никакие две горные цепи из входных данных не пересека- ются, в единственной строке выходных данных выведите слово "Yes" (без кавычек).
Иначе выведите в первой строке слово "No" (без кавычек), а на следующей строке выведите два числа — номера двух пересекающихся горных цепей. Горные цепи нумеруются согласно их появлению во входных данных, начиная с 1.

Примеры
Ввод Вывод
-3 3
2
1
-3 2
3 1
2
-3 2
0 4
3 2
Yes
0 4
2
3
0 3
1 3
3 1
4 1
1
0 2
4 2
No
1 2


Замечание

Напоминаем, что абсциссой точки называется её x-координата, а ординатой — её y-координата. В первом примере хотя ломаные и касаются друг друга в точке (−3, 2), но, согласно данному выше определению, они не пересекаются. Во втором примере в точке x1 = 1 одна ломаная выше другой, а в точке x2 = 3 — наоборот, то есть горные цепи пересекаются.

 

У Гудвина есть последовательность чисел из которой он хочет удалить три элемента так, чтобы последовательность была наиболее симпатичной.

Кривизна последовательности задается функцией  , то есть разностью, между суммой элементов, стоящих на нечетных местах, и суммой элементов, стоящих на четных местах.

После удаления из последовательности трех элементов все остальные сдвигаются на нужные места. Например, из последовательности {1, 2, 3, 4, 5} можно получить последовательность {2, 4}.

Входные данные

В первой строке записано целое число n (4 ≤ n ≤ 106) — количество элементов в исходной последовательности. Во второй строке записаны n разделенных пробелами целых чисел — члены последовательности, разделенные пробелами. Все числа в последовательности по модулю не превышают 109.

Выходные данные

Выведите единственное число — минимальную кривизну последовательности, которая может быть получена из данной удалением трех элементов.

Примеры тестов

Входные данные

4
1 2 3 4
Выходные данные
1
Входные данные
5
1 2 3 4 5
Выходные данные
-4

Примечание

Тесты разделены на группы, но оцениваются отдельно

  • n ≤ 81 — 20 баллов
  • n ≤ 300 — 10 баллов
  • n ≤ 5000 — 20 баллов
  • Без дополнительных ограничений — 50 баллов 
В клубе N человек. Многие из них - друзья. Так же известно, что друзья друзей так же являются друзьями. Требуется выяснить, сколько всего друзей у конкретного человека в клубе.
 
Входные данные
 
В первой строке входного файла INPUT.TXT заданы два числа: N и S (1 <= N <= 100; 1 <= S <= N), где N - количество человек в клубе, а S – номер конкретного человека. В следующих N строках записано по N чисел - матрица смежности, состоящая из единиц и нулей. Причем единица, стоящая в i-й строке и j-м столбце гарантирует, что люди с номерами i и j – друзья, а 0 – выражает неопределенность.
 
Выходные данные
 
В выходной файл OUTPUT.TXT выведите количество гарантированных друзей у человека с номером S, помня о транзитивности дружбы.

Пример

Ввод:
3 1
0 1 0
1 0 1
0 1 0

Вывод
2
Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу ai воинов, которых он может завербовать в свою армию.
Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему ci золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено ai < aj , то ci ≤ cj . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Входные данные
В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа ai и ci (1 ≤ ai ≤ 100, 1 ≤ ci ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если ai < aj , то ci ≤ cj .

Выходные данные
В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.
 
Примеры
Входные данные Выходные данные
1
3
1 1
2 2
4 3
5
 
В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились
к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.
21802#21802
Преобразование, изменяющее структуру текста называется

1. редактированием
2. форматированием
3. стилизацией
4. структуризацией
21800#21800
Представление текста в виде списка называется

1. проверкой правописания
2. форматированием
3. редактированием
4. стилизацией
21794#21794
Программа, предназначенная для создания, просмотра, редактирования, форматирования, сохранения и печати текстовых документов, которая может содержать объекты
различной природы - это

1. текстовый редактор
2. текстовая программа
3. текстовый процессор
4. текстовый обработчик
Поделиться
Класснуть