Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Запросы в массив#29643
Вам нужно реализовать структуру данных на базе массива, которая сможет отвечать на данные типы запросов:

0 - вывести размер массива и знак перехода на новую строку;
1 x - добавить в конец массива число x;
2 - удалить последний элемент массива;
3 x y - вставить число y между элементами массива x и x + 1;
4 x - удалить элемент №x;
5 - вывести все элементы массива в порядке их следования в нем через пробел. В конце выведите знак перехода на новую строку;
6 x - изменить размер массива на x. Если x меньше текущего размера массива, то все элементы, начиная с элемента №x отбрасываются. Если x больше текущего размера массива, то появившиеся элементы массива будут равны 0.
 
Формат входных данных
- в первой строке содержится число N (\(1 <= n <= 100\));
- в следующих N строках содержатся запросы в формате, записанном в условии.
 
Формат выходных данных
Выведите ответы на запросы типа 0 и 5.
Standard Template Library
✓ 340✗ 1 216700средняяВойти и решать
Тихий Дон №1#29641
В мирное время казаки занимаются сельским хозяйством. Пантелей Прокофьевич Мелехов выращивает специальные математические овощи, которые растут по очень странным правилам: у каждого семечка i этих овощей есть значение урожайности ai, а урожайностью всей грядки является произведение урожайностей всех семян, посаженных на ней. У Мелехова есть N семян. Помогите ему выбрать из этих семян несколько так, чтобы при посадке этих семян урожайность грядки была максимальна.
 
Входные данные:
В первой строке содержится число N (1 <= N <= 15)
Во второй - N чисел ai, возможно вещественных (|ai| < 10)
 
Выходные данные:
Выведите максимальную урожайность грядки с точностью не менее 6 знаков после запятой, которой можно добиться с данным набором семян. Гарантируется, что оно больше 1.
 
Ввод Вывод
5
2.0 -1.2 4.7 -2.9 -1.1
 32.712000

(с) Григорьев Е., 2018
Битовые операции
✓ 52✗ 93600лёгкаяВойти и решать
Интернет-магазин#29635
Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида:
Покупатель товар количество,
где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.
 
Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
 
 
Входные данные
В первой строке входного файла содержится число N (\(1<=N<=100000\)) —количество записей содержащихся в данной базе данных. Вводятся сведения о покупках в указанном формате.
 
Выходные данные 
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
 
 
Пример
№ Входные данные Выходные данные
1
6
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5
Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5
Словари
✓ 746✗ 991600лёгкаяВойти и решать
Файловая система#29634
В файловую систему одного суперкомпьютера проник вирус, который сломал контроль за правами доступа к файлам. Для каждого файла Ni известно, с какими действиями можно к нему обращаться:
 
запись W
чтение R
запуск X
 
Вам требуется восстановить контроль над правами доступа к файлам (ваша программа для каждого запроса должна будет возвращать OK, если над файлом выполняется допустимая операция, или же Access denied, если операция недопустима).
 
Входные данные
В первой строке содержится число N (1 <= N <= 10000) - количество файлов содержащихся в данной файловой системе.
В следующих N строках содержатся имена файлов и допустимых с ними операций, разделенные пробелами. Длина имени файла не превышает 15 символов.
Далее указано число M (1 <= M <= 50000) - количество запросов к файлам.
В последних M строках указан запрос вида Операция Файл. К одному и тому же файлу может быть применено любое количество запросов.
 
Выходные данные
Для каждого из M запросов нужно вывести в отдельной строке Access denied или OK.
 
 
Пример
№ Входные данные Выходные данные
1 
4
helloworld.exe R X
pinglog W R
nya R
goodluck X W R
5
read nya
write helloworld.exe
execute nya
read pinglog
write pinglog
 
OK
Access denied
Access denied
OK
OK
Словари
✓ 911✗ 1 139600лёгкаяВойти и решать
Разложение на простые - 1#29549
Требуется разложить целое число N на простые множители, представив его в виде произведения простых множителей и вывести результат в порядке возрастания.
 
Входные данные  
На вход падается число N (\(2 <= N <= 10^9\)).
 
Выходные данные 
Выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».
 
Примеры
№ Входные данные Выходные данные
1 5 5
2 30 2*3*5
Простые числа и разложение на множители
✓ 954✗ 1 847400лёгкаяВойти и решать
Разложение на простые - 2#29548
Требуется разложить целое число N на простые множители, представив его в виде произведения степеней простых множителей и вывести результат в порядке возрастания.
 
Входные данные 
На входе дано число N (\(2 <= N <= 10^9\)).
 
Выходные данные 
Вывести разложение N на простые множители.
 
Примеры
№ Входные данные Выходные данные
1 2 2
2 1008 2^4*3^2*7
Простые числа и разложение на множители
✓ 627✗ 1 580500лёгкаяВойти и решать
Длины чисел#29518
Назовём длиной числа количество цифр в его десятичной записи. Например, длина числа 2017 равна 4, а длина числа 7 равна 1. Дан набор из N целых неотрицательных чисел, каждое из которых меньше 109.
Необходимо определить, числа какой длины реже всего (но не менее одного раза) встречаются в данном наборе и сколько в нём чисел этой длины. Если числа разной длины встречаются одинаково часто (и реже, чем числа любой другой длины), нужно выбрать меньшую длину.
Напишите эффективную по времени и по памяти программу для решения этой задачи.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (\(1 <= N <= 10000\)). В каждой из последующих N строк записано одно неотрицательное число, не превышающее 109.
Пример входных данных:
5
12
417
125
327
4801
Пример выходных данных для приведённого выше примера входных данных:
2 1
В данном наборе реже всего (по 1 разу) встречаются числа длины 2 и 4.
 
ЕГЭ - вычислительные задачи
✓ 725✗ 1 765500лёгкаяВойти и решать
Дед мороз, снегурочка и конфеты#29497

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. 

Дед Мороз и Снегурочка – волшебники, поэтому число утренников N, на которых они побывали, может быть очень большим. 

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

Программа будет считаться эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программа будет считаться эффективной по времени, если при увеличении размера входных данных N в t раз (t – любое число) время её работы увеличивается не более чем в t раз.

 
Входные данные
В первой строке вводится одно целое положительное число – количество утренников N. Каждая из следующих N строк содержит два целых числа: D – количество пришедших на очередной утренник детей; K – количество конфет в мешке Деда Мороза на этом утреннике. 

Гарантируется выполнение следующих соотношений: \(1 <= N <= 10000\), \(1 <= D <= 100\) (для каждого D), \(D <= K <= 1000\) (для каждой пары D, K)

Выходные данные
Программа должна вывести одно число – то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.
 

 

Примеры
№ Входные данные Выходные данные
1
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
 31
ЕГЭ - вычислительные задачи
✓ 573✗ 1 391600лёгкаяВойти и решать
По мотивам ЕГЭ 2018 - 1#29496
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов  последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
 
Входные данные
В первой строке входных данных задаётся количество чисел N (\(1 < N <= 100000\)). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

Выходные данные
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
 

 

Примеры
№ Входные данные Выходные данные
1
4
2
6
13
39
 4

Пояснение. Из четырёх заданных чисел можно составить 6 попарных произведений: 2·6, 2·13, 2·39, 6·13, 6·39, 13·39 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234).
 

ЕГЭ - вычислительные задачи
✓ 469✗ 816500лёгкаяВойти и решать
Дремучий лес#29481
Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.
 
    - Судиславль находится в точке с координатами (0, 1).
    - «Берендеевы поляны» находятся в точке с координатами (1, 0).
    - Граница между лесом и полем — горизонтальная прямая y=a, где a — некоторое число (0 ≤ a ≤ 1).
    -  Скорость передвижения СЭС по полю составляет Vp, скорость передвижения по лесу — Vf. Вдоль границы можно двигаться как по лесу, так и по полю.

Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.
 
Входные данные
В первой строке входного файла содержатся два положительных целых числа Vp  и Vf  (1≤ Vp, Vf ≤ 105) . Во второй строке содержится единственное вещественное число — координата по оси Oy  границы между лесом и полем a  (0 ≤ a ≤ 1) .
 
Выходные данные
В единственной строке выходного файла выведите вещественное число с точностью не менее 8 знаков после запятой — координата по оси Ox точки, в которой инспекция СЭС должна войти в лес.
 
Ввод Вывод
5 3
0.4		 0.783310604
5 5
0.5
 0.500000000
Бинарный поиск по ответу
✓ 147✗ 239700средняяВойти и решать
Пузырьковая сортировка: количество обменов#29475
Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.
 
Входные данные
На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 109.
 
Выходные данные
Выведите одно число – количество обменов пузырьковой сортировки.
 
Примеры
№ Входные данные Выходные данные
1
5
1 2 3 4 5 
 0
2
5
5 4 3 2 1
 10
Сортировка "пузырьком"
✓ 2 539✗ 2 085200лёгкаяВойти и решать
Пузырьковая сортировка#29474
Требуется отсортировать массив по неубыванию методом "пузырька".
 
Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).
 
Выходные данные
Вывести получившийся массив.
 
Примеры
№ Входные данные Выходные данные
1
5
5 4 3 2 1
 1 2 3 4 5
Квадратичные сортировки
✓ 2 890✗ 5 442200лёгкаяВойти и решать
Клавиатура#29472
Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.
 
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.
 
Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.
 
Входные данные
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.
 
Выходные данные
В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.
 
 
Ввод Вывод
5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5
yes
no
no
no
yes

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача A
Сортировка подсчетом
✓ 580✗ 442500лёгкаяВойти и решать
Разброс#29470
Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 107.
 
Входные данные
Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*109. Никакие два не различаются более, чем на 107.
 
Выходные данные
Выведите данные числа в порядке неубывания.
 
Ввод Вывод
1
863961129 
 863961129 
5
1866455200 1866455199 1866455198 1866455197 1866455196 
 1866455196 1866455197 1866455198 1866455199 1866455200 
Сортировка подсчетом
✓ 484✗ 1 021600лёгкаяВойти и решать
Носки#29468
Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.
 
Формат входных данных
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.
 
Формат выходных данных
Выведите M чисел – толщину носкового покрытия в каждой точке.
Сортировка подсчетом
✓ 616✗ 858500лёгкаяВойти и решать
Сортировка подсчетом#29467
Реализуйте алгоритм сортировки подсчетом для произвольных чисел, по модулю не превосходящих 10000.
 
Входные данные
На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.
 
Выходные данные
Выведите на экран отсортированный по неубыванию массив.
 
Примеры
№ Входные данные Выходные данные
1
5
1 3 4 2 5
 1 2 3 4 5
Сортировка подсчетом
✓ 1 265✗ 4 097500лёгкаяВойти и решать
Расписание для 9И#29451
В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

Входные данные:  В первой строке входных данных содержится число N – кол-во уроков и число M – количество последовательных пар уроков наверное.
В следующих M строках задаются 2 слова, которые обозначают названия предметов.
Известно что, граф не может зациклиться и предметы не могут быть в расписании 2 раза
Слова, которые можно вводить: PE,Math, Russian, Biology,Geometry, Literature, Science, Geography
 
Выходные данные: Задача — выстроить предметы в подходящем для всех пар порядке.
 
Ввод Вывод
3 2
PE Math
Math Literature		 PE
Math
Literature

(c) Бганцова А., 2018 г.
Топологическая сортировка
✓ 14✗ 19700средняяВойти и решать
Спасти новобранцев#29450
Группа солдат-новобранцев прибыла в армейскую часть N777. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо. 
 
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. 
 
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен. 
 
Входные данные 
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 
 
Выходные данные 
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры
№ Входные данные Выходные данные
1
4 5 
1 2 
2 3 
3 4 
1 4 
4 1
 No

(c) Пасынков С., 2018 г.
Топологическая сортировка
✓ 29✗ 25500лёгкаяВойти и решать
Дороги королевства#29449
В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом! 
 
Формат файла входных данных: 
Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно. 
 
Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города. 
 
Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние. 
 
Формат файла выходных данных: 
Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
 
Ввод Вывод
4 4 
aaa bacc cqe de 
1 4 
4 2 
4 3 
3 2
 1 4 3 2
3 3 
fi bru a 
1 2 
2 3 
3 1
 -1
(с) Филимонов И.
Топологическая сортировка
✓ 19✗ 8600лёгкаяВойти и решать
Поделиться
Класснуть