Информатика

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

1. исходные данные - результат
2. исходные данные - алгоритм - результат
3. алгоритм - исходные данные - результат
4. алгоритм - результат
Линейные алгоритмы
—Войти и решать
Перестановки с другим началом (С', С)#23336
Перестановкой размера n называется упорядоченный набор из n чисел, в котором каждое число от 1 до n встречается ровно один раз. Например, (4, 2, 3, 5, 1) - это перестановка размера 5.
Нам дано число n и последовательность a, в которой k натуральных чисел.
Вычислите, сколько существует перестановок размера n, которые не начинаются на данную последовательность.

Формат входных данных
В первой строке содержатся два натуральных числа n и k (1 <= n <= 9,  1 <= k <= 100) .
Во второй строке содержатся k натуральных чисел,  составляющие последовательность a. Каждое из этих чисел не превышает 100.
Формат выходных данных
Выведите количество перестановок размера n- которые не начинаются на данную последовательность a.
Ввод Вывод
3 2
2 1		 5
5 2
4 4		 120
5 6
2 3 9 5 6 6		 120
Комбинаторика
✓ 34✗ 63800средняяВойти и решать
Денежная система (С, В')#23335
Денежная система Небритании развивалась на протяжении многих лет, изначально небританцы пользовались пшиллингами 0-го уровня - обычными монетками.
Во время правления  Генриха 1-го были введены пшиллинги 1-го уровня, которые равнялись 10 пшиллингам 0-го уровня.
Во время правления  Генриха 2-го были введены пшиллинги  2-го уровня, которые равнялись 20 пшиллингам 1-го уровня.
Во время правления  Генриха 3-го были введены пшиллинги 3-го уровня, которые равнялись 30 пшиллингам 2-го уровня.
И так далее, а именно, во время правления Генриха k-го были введены пшиллинги k-го уровня, которые равнялись 10k пшиллингам (k − 1)-го уровня.
Сейчас в казне Небритании огромная сумма, равная n пшиллингам 0-го уровня. Запишите ее фразой вида "столько-то пшиллингов такого-то уровня, столько-то пшиллингов такого-то уровня
и т. д.", причем суммарное количество упомянутых вами пшиллингов всех уровней должно быть минимальным.
 
Формат входных данных
В первой строке содержится натуральное число n ( 1<= n <= 1015).
 
Формат выходных данных
Выведите несколько пар целых чисел, по одной на строке. При этом пара (a, b) означает фразу
" a пшиллингов b-го уровня".
Номера уровней в вашей фразе должны строго убывать. Можно совсем не использовать пшилинги какого-то уровня, в этом случае не нужно выводить про них ничего. Количество пшиллингов
каждого упомянутого вами уровня должно быть положительно (a > 0).
Ввод Вывод
7777 1 3
8 2
17 1
7 0
6030 1 3
3 1
Вывод формулы
✓ 23✗ 37900средняяВойти и решать
Касса (D, C')#23333
Оля решила стать предпринимателем, и недавно открыла свой магазин "Н-аудио". Магазин работает уже в течение целых n дней, и в конце каждого дня Оля приходит, и записывает на листочек количество денег в кассе магазина. При этом, в конце дня деньги из кассы не изымаются,  то есть, после первого дня в кассе хранится выручка за первый день, после второго дня выручка за первый и второй дни и так далее. Оле стало интересно, в какой из n дней выручка магазина была максимальна. Если таких дней несколько, то Олю интересует первый такой день.
 
Формат входных данных  
в  первой строке входного файла находится целое число n - количество дне, в течение которых
работал магазин 1 <= n <= 105 . В i-ой из следующих n строчек содержится целое число ai -
описание баланса рублей в кассе магазина после i-ого дня 0 <= ai <=109
гарантируется, что деньги из кассы никогда не забирали, то есть ai > ai?1 -  для любого i от 2 до n.
 
Формат выходных данных
В единственной строке выходного файла выведите два целых числа - номер дня, в котором
выручка магазина была максимальна, и величину этой выручки. Если таких дней несколько, то
выведите самый ранний из них. Дни в магазине нумеруются с единицы?
 
Ввод Вывод
3
4
5
17		 3 12
5
1
1
3
5
5		 3 2
Линейный поиск
✓ 113✗ 311600лёгкаяВойти и решать
Турист Петр#23315
На отдыхе в Теплой Стране Вера познакомилась с симпатичным волейболистом- трактористом Петром. Турист Петр, кстати, собирается после отличного отдыха в Теплой Стране отправиться в путешествие по городам Европы. Как известно, Европа облада- ет развитой транспортной системой: в Европе есть 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средняяВойти и решать
Пляжный волейбол#23314
Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.

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

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

Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствую- щем считалке номером K. Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны Q считалок, соответствующих различным значениям K. Для каждого из этих чисел Ki необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две коман- ды будут играть в матче с номером Ki.

Формат входного файла
Первая строка входных данных содержит единственное целое число N — количество команд (2 <= N <= 100 000). Вторая строка содержит N различных чисел от 1 до N — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди. Третья строка содержит единственное целое число Q (1 <= Q <= 100 000) — коли- чество известных Вере считалок. Каждая из следующих Q строк содержит число Ki (1 <= Ki <= 1018) — номер очередного интересующего Веру матча. Обратите внимание, Ki может быть больше N. Формат выходного файла Выведите Q строк: для каждого интересующего Веру числа Ki два числа в любом порядке — силы команд, сыграющих на Ki-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.

Примеры
Ввод Вывод
4
1 3 2 4
1
3		 3 4
4
2 1 4 3
3
1
5
2		 2 1
4 2
2 4


Комментарии
Разберем первый тест из условия:
  Кто играет Состояние очереди Победитель Проигравший
Матч № 1
Матч № 2
Матч № 3		 1 3
3 2
3 4		 2 4
4 1
1 2		 3
3
4		 1
2
3

Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.
Конструктив
✓ 0✗ 431 100средняяВойти и решать
Сумма чисел последовательности - Задание 3#23242
Напишите программу, которая находит сумму квадратов целых чисел от a до b.

Входные данные
В одной строке задаются два числа a и b (\(-100 < a,\ b < 100\)).

Выходные данные
Выведите одно число - сумму квадратов целых чисел от a до b.
 

 

Примеры
№ Входные данные Выходные данные
1 1 5 55


Пояснение ответа: 1*1+2*2+3*3+4*4+5*5=55

Цикл for
✓ 9 019✗ 11 036100лёгкаяВойти и решать
Сумма чисел последовательности - Задание 2#23241
Напишите программу, которая находит сумму целых чисел от a до b (включительно), где a и b вводятся с клавиатуры.

Входные данные
В одной строке заданы два целых числа a и b (\(-100 <a,\ b < 100\)).

Выходные данные
Выведите ответ на задачу.
 

 

Примеры
№ Входные данные Выходные данные
1 1 5 15

 

Цикл for
✓ 9 120✗ 30 382200лёгкаяВойти и решать
Оператор цикла for. Таблица умножения#23082
Вам необходимо написать программу, которая по заданному с клавиатуры натуральному числу N (N<=10) напечатает таблицу умножения на данное число, например, для N=2, программа должна выводить следующую информацию: 
2*1=2
2*2=4
2*3=6
2*4=8
2*5=10
2*6=12
2*7=14
2*8=16
2*9=18
2*10=20
Цикл for
✓ 11 682✗ 35 901200лёгкаяВойти и решать
23073#23073
Дано натуральное число N (N<=15). Заполните и выведите на экран квадратный двумерный массив размером NxN по следующему правилу:
1 2 3 4 5 6 
2 3 4 5 6 1 
3 4 5 6 1 2 
4 5 6 1 2 3 
5 6 1 2 3 4 
6 1 2 3 4 5
Каждый элемент массива отделяется от другого одним пробелом, каждая строка массива выводится с новой строки
Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 6
1 2 3 4 5 6 
2 3 4 5 6 1 
3 4 5 6 1 2 
4 5 6 1 2 3 
5 6 1 2 3 4 
6 1 2 3 4 5
 
 

Двумерные массивы
✓ 134✗ 126600лёгкаяВойти и решать
23072#23072
Дано натуральное число N (N<=15). Заполните и выведите на экран квадратный двумерный массив размером NxN по следующему правилу:
1 1 1 1 1 1
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252
 
 
Каждый элемент массива отделяется от другого одним пробелом, каждая строка массива выводится с новой строки
Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 6 1 1 1 1 1 1
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252
 

Двумерные массивы
✓ 132✗ 88600лёгкаяВойти и решать
Ожидание трамвая#23042
Ваня хочет поехать в школу,куда от его квартиры идёт только шестой трамвай. Проблема в том,что Ваня очень стеснительный и боится садиться 
в трамвай,если в нём больше d человек.Известно,что трамваи идут раз в k минут.Ваша задача состоит в том,чтобы посчитать количество минут,которые простоит Ваня на остановке, 
учитываю Ванину стеснительность:если есть такой пустой трамвай,который идёт Васе,он будет ждать его сколько угодно.Если же таких трамваев несколько,то он,разумеется,сядет на 
тот,что придёт раньше.Если данные введены некорректно,вывести "Absent"; 
Так же известно,что Ваня приходит на остановку в тот момент времени,когда к ней подъезжает первый трамвай
Входные данные: 
Сначала вводятся два числа d и k такие,что 0<=d<=100 и 0<=k<=100. 
Затем вводится t строк(0<=t<=100,само число t нам неизвестно),заканчивающихся одним числом -1 по 2 числа в каждой- количество людей в трамвае и его номер 
Вывод: 
В выводе должно быть одно число-количество минут,которые Ваня простоит на остановке в ожидании трамвая,или же слово "Absent"

(c) Васильев Алексей
Задачи на моделирование
✓ 0✗ 101 200средняяВойти и решать
Веселый Новый Год#23039
У нас было 2 набора юного химика, 75 мятных таблеток, 5 упаковок оберточной бумаги, полфунта детских драже и целое множество подарков всех сортов и расцветок, а также машинки, куклы,  мешок вкусного оленьего корма, пинта чистого сока и стадо быстрых оленей.
Не то что бы это был необходимый запас для поездки. Но если начал развозить подарки, становится трудно остановиться.
Единственное что вызывало у меня опасение - это олени. Нет ничего более непредсказуемого, чем стадо северных оленей, кто знает чего от них ожидать?  Я догадывался, что рано или поздно они дадут о себе знать.
Самое страшное, что домов, куда нужно доставить подарки, более 10^100000000 и ребенок сильно расстроится, узнав, что не получил подарка на Новый Год. Этого допускать нельзя, благо вы - не единственный Санта, и вам будет достаточно доставить подарки только в своем городе. Детишек в вашем городе не больше 10^4, но все они живут в разных домах. У вас есть список, в котором не больше 10^4 элементов, каждый элемент списка представляет собой 2 целых числа – координаты дома следующего ребеночка.  Доставив подарки в очередной дом, вы, как порядочный Санта, обязаны стирать координаты этого дома из своего списка. Но ваши олени не хотят спокойно доставлять подарки, они коллективно прокладывают на их взгляд более оптимальный и правильный маршрут, и выбирают номер следующего дома из вашего списка по своей очень логичной и тривиальной формуле:
Nnext  = |(K1  - K2  ) *R|% L,
где Nnext – номер следующего дома в вашем списке (Как делают настоящие ТРУ-программисты? Они считают элемент с  единицы нуля!)  K1  - количество еще не посещенных домов, K2 – количество уже посещенных домов, R – коэффициент рандомности стада и L – длина текущего списка. Заметим, что после посещения дома, количество элементов в вашем списке уменьшается, вы же порядочный Санта, верно? Вечером, после тяжелого трудового дня, вы, как и остальные труженики Новогоднего фронта,  выкладываете в свой блог количество  километров, которые сегодня преодолели. Изначально вы находитесь в доме с индексом 0 и считается, что подарок в этот дом уже доставлен.  Зная столь тривиальную, понятную и очевидную формулу расчета следующего дома, а также имея список домов и  хорошо зная свое стадо, вплоть до их коэффициента рандомности, скажите какое расстояние  вы пройдете за всю поездку? Ответ округлите вверх до целых, в таких вещах можно чуть-чуть  преувеличить.  
 
Входные данные:
В первой строке входного файла находятся целые положительные числа N, R (1<N<=10000,1< R <1000000) – количество детей в вашем списке и коэффициент рандомности вашего стада, соответственно.
В следующих N строках находятся по 2 целых числа X,Y (-100000<=X,Y<=100000) – координаты конкретного  дома.
Выходные  данные:
Выведете одно целое число – ответ на поставленную задачу.
 
Пример, как же без примера:
Входит:
4 2
1 1
0 0
2 0
2 1
Выходит:
6

(с) Ярослав Свиридов 10и
Задачи на моделированиереализация
✓ 4✗ 271 100средняяВойти и решать
Зл 9.26#22042
Дано слово вертикаль. Путем "вырезок" и "склеек" его букв получить слова тир и ветка. 
Результирующие слова выводить в столбик.

Пример входных и выходных данных
№ теста Входные данные Выходные данные
1 вертикаль тир
ветка
Строки
✓ 163✗ 135400лёгкаяВойти и решать
Набор точек на плоскости#22029

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

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

Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.

Пример входных данных:
6
0 0
2 0
3 3
5 5 
-6 -6
1 2
Пример выходных данных для приведенного выше примера входных данных:
6
ЕГЭ - вычислительные задачи
✓ 341✗ 831600лёгкаяВойти и решать
Ведьмак#22027
По приезде Геральда в Каэр-Морхен уже наступила зима. Вокруг стояла тишина, а окна замка приветливо светились в темноте. Редкие факелы создавали теплую и согревающую атмосферу, освещая ровный белый ковер из снега. Среди этой красоты особенно порадовал Геральда отъезд Весемира, ведь теперь можно закатить грандиозную пьянку!
Для этого на кухонный стол достали 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и
Задача о рюкзакереализация
✓ 1✗ 31 200средняяВойти и решать
Украшение елки#22025
В преддверии Нового Года Вася купил ёлку и решил её украсить. Для этого он должен достать с верхней полки шкафа самые красивые украшения. К сожалению, ставить стул на стул было плохой идеей… Теперь у него вместо коробки украшений – куча, состоящая из украшений, осколков и вещей из других коробок. Конечно же, её нужно разобрать. Но Вася так хочет смотреть новогодние фильмы! Помогите ему написать программу, которая разберёт кучу мусора за него. 
 
Входные данные
На вход подаётся две строки. Первая – примеры украшений. Вторая – собственно куча. 
 
Выходные данные
Нужно вывести количество украшений каждого вида, а также количество разбитых (обозначены точкой) украшений. 
 
Примеры
№ Входные данные Выходные данные
1
60oQ 
484QQQQ.Qhu.6.oodnh...ddh76762..300ojha.
6: 3 
0: 2 
o: 3 
Q: 5 
Broken: 9
2
80 
..7.8.7.8.9.8 
8: 3 
0: 0 
Broken: 7 
 
Строки
✓ 488✗ 801600лёгкаяВойти и решать
Поделиться
Класснуть