Информатика

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

The sum of the digits of number 123 is 6

 
СтрокиЦикл for
✓ 8 967✗ 34 522200лёгкаяВойти и решать
Декодирование сообщения#23418

По каналу связи передаётся последовательность слов в латинском алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом:
1)      Сначала слово кодируется с помощью неравномерного двоичного кода с кодовыми словами: Е – 0; Р – 10; А – 11;
2)      К полученной двоичной последовательности справа приписывается цифра 1;
3)      Полученная двоичная цепочка переворачивается, то есть, из цепочки 01010111 получается 11101010;
4)      Искомое число N вычисляется в результате перевода двоичной цепочки, полученной на предыдущем шаге, в десятичную систему.
 

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем (добавляем единицу в конец) в 111100101, а потом в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 1010011112.
Напишите программу, которая, получив на вход натуральное число, декодирует переданное сообщение и определяет, сколько раз в исходном слове встречаются гласные буквы. Считается, что входное число может быть представлено в виде значения целого типа в используемом языке программирования.

Пример входных данных
5483

Пример выходных данных
АЕРАЕРР
4

Примечание. В этом примере: исходное слово: АЕРАЕРР. Кодовая двоичная последовательность: 110101101010, после добавления 1 справа получим: 1101011010101.
ЕГЭ_информатикаЕГЭ-04. Кодирование и декодирование информации
✓ 57✗ 140800средняяВойти и решать
Уравнение с пропущенными цифрами#23416
Задано уравнение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из  возможных решений.
 
Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов. 
 
Выходные данные
Требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".
 

Примеры
№ Входные данные Выходные данные
1 ??2?4+9?=355 00264+91=355
 
Динамическое программированиеДинамическое программирование по подстрокам
✓ 2✗ 371 300средняяВойти и решать
Шаблон и слово#23413
Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).
 
Входные данные 
В первых двух строках записаны шаблон и слово: в одной из них записан шаблон - последовательность больших  латинских букв, "?" и "*", в другой  - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные
Вывести YES, если слово подходит, NO, если не подходит.
 
Примеры
№ Входные данные Выходные данные
1
ABBCDA
A*CDA
 YES
2
AADAAVA
A*DA*AA*
 NO
 
Динамическое программирование: один параметрСтроки
✓ 5✗ 121 100средняяВойти и решать
Восстановление скобок#23412
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
 
Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
 
Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·109.
 
 
Примеры
№ Входные данные Выходные данные
1 ????(? 2
 
Динамическое программирование по подстрокамДинамическое программирование: два параметра
✓ 116✗ 190800средняяВойти и решать
*Удаление пробелов#23384
На вход подается одна строка текста (не больше 255 символов).
Нужно вывести эту же строку, удалив все парные пробелы (то есть, если где-то в строке идет подряд 2 или более пробелов, то в этом месте нужно оставить только один из них).
 
Примеры
№ Входные данные Выходные данные
1    My    name is    Vasya...  My name is Vasya...
Алгоритмы обработкиСтроки
✓ 3 780✗ 8 636500лёгкаяВойти и решать
Перестановка слов#23383
На вход подается одна строка, в которой записаны фамилия и имя человека (разделенные ровно одним пробелом).
 
Выведите эту же информацию, однако сначала имя, а потом фамилию.
 
Пример
№ Входные данные Выходные данные
1 Pupkin Vasya Vasya Pupkin
 
Ввод, вывод данныхСтроки
✓ 7 206✗ 7 330100лёгкаяВойти и решать
День рождения#23382
На день рождения пришли N человек. В некоторый момент именинник  решил, что пора устроить какую-нибудь игру. Он выяснил, что i-й человек  согласен вступить в игру, если в ней уже принимают участие не менее A[i] и не более B[i] человек. Единожды вступив в игру, никто из нее 
не выходит.

Требуется выяснить, может ли именинник установить такую 
последовательность вступления в игру, что в итоге все 
присутствующие станут ее участниками. (Сам именинник в игре участия 
не принимает.) 
 
Входные данные. 
Сначала вводится количество гостей N (1<=N<=100). Затем вводится 
N пар чисел A[i] и B[i] (все эти числа из диапазона от 0 до N-1).
 
Выходные данные. 
Если можно установить последовательность вступления гостей в игру, 
чтобы в итоге все стали ее участниками, то нужно вывести номера гостей 
в том порядке, в каком они могут вступать в игру. Если всех вовлечь 
в игру не удастся, выведите одно число - 0.
 
Пример 1
Пример входного файла
5
4 4
0 3
1 4
1 3
2 2
 
Пример выходного файла
2 3 5 4 1
 
Пример 2
Пример входного файла
3
1 1
1 1
1 1
 
Пример выходного файла
0
 
Пример 3
Пример входного файла
1
0 0
 
Пример выходного файла
1
Жадный алгоритмРазбор случаев
—Войти и решать
Список#23381
В фирме, выпускающей компьютерные комплектующие, все изделия получают последовательные номера от 1 до N. Каждое изделие после его изготовления поступает в отдел контроля качества, где оно проверяется, и либо уходит в продажу, либо заносится в список бракованных изделий и списывается. К сожалению, список бракованных изделий иногда оказывается чересчур длинным. Тогда для его сокращения подряд идущие числа заменяются интервалом: через тире указываются номера первого и последнего изделия интервала.
Например, вместо 
1,3,4,5,6,7,8,10,12,16,17,20,21,22,23,24
записывается
1,3-8,10,12,16-17,20-24
 
Напишите программу, которая по полному списку номеров бракованных изделий выдаст этот список в сокращенном виде.
 
Входные данные
В первой строке вводится сначала число N - общее количество изделий, затем число M - количество изделий, оказавшихся бракованными. Во второй строке вводятся в возрастающем порядке номера бракованных изделий. 
 
Выходные данные
Выведите в одной строке список номеров бракованных изделий в сокращенном виде. Интервалы должны разделяться запятой. В строке не должно быть пробелов.
 
Ограничения
1<=M<=N<=1000000.
 
Примеры
№ Входные данные Выходные данные
1
10 5 
1 3 5 7 9
 1,3,5,7,9
2
40 16
1 3 4 5 6 7 8 10 12 16 17 20 21 22 23 24
 1,3-8,10,12,16-17,20-24
3
11 11
1 2 3 4 5 6 7 8 9 10 11
 1-11
4
10000 1 
5
 5
Алгоритмы обработкиОдномерные массивы
✓ 1 426✗ 1 883600лёгкаяВойти и решать
Два массива#23379
Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.
 
Входные данные
В первой строке ввода записано число N - количество элементов в первом массиве. Во второй строке  - N чисел (элементы массива). В третьей строке записано число M - количество элементов во втором массиве. В четвертой строке  - элементы второго массива.
Количество элементов каждого массива не превышает 100. Сами элементы по модулю не превышают 1000. Все числа целые.
 
Выходные данные
Выведите те элементы первого массива, которых нет во втором.Элементы необходимо вывести в том порядке, в каком они идут в первом массиве.
 
Примеры
№ Входные данные Выходные данные
1
7
3 1 3 4 2 4 12
6
4 15 43 1 15 1
 3 3 2 12
 
Алгоритмы обработкиОдномерные массивы
✓ 4 020✗ 5 275300лёгкаяВойти и решать
Британские ученые (В, А', А)#23376
Согласно исследованиям британских ученых, люди способны воспринимать слова в тексте, если в каждом слове оставить на месте первую и последнюю буквы, а остальные перемешать произвольным образом; например, слово "программа" может быть прочитано даже если оно записано как
"пгрроммаа" или "пморгамра".
Вам дан словарь с несколькими словами, а также некоторый текст. Для каждого слова из текста определите, можно ли его прочитать как одно из слов словаря, руководствуясь правилами, описанными выше.
 
Формат входных данных
В первой строке записано одно целое число n (1 <=  n <= 105)  - количество слов в словаре.
В следующих n строках записаны слова из словаря, по одному на строку. Гарантируется, что все слова в словаре различны.
В следующей строке записано одно целое число m (1 <= m <= 105) - количество слов в тексте.
В следующих m строках записаны слова из текста, по одному на строку.
Каждое слово состоит только из строчных букв латинского алфавита; ни в какой строке ввода нет пробелов и других разделителей. Суммарная длина всех слов не превосходит 105.
 
Формат выходных данных
Для каждого слова из текста выведите "YES" если его можно прочесть как одно из слов словаря, и "NO" в противном случае. Ответы для слов из текста следует выводить в том же порядке, в
котором слова перечислены во вводе; следует выводить по одному ответу на строку.

 
Ввод Вывод
4
bird
sun
lksh
summer
4
brid
snu
sommer
sis		 YES
NO
NO
NO
Задача на реализациюСловари
✓ 18✗ 68900средняяВойти и решать
Сливаемся!#23375
Слияние двух упорядоченных последовательностей чисел в одну упорядоченную  основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-
довательностей легко выполняется в том числе и человеком вручную.

В этой задаче по полученной в результате слияния неубывающей последовательности чисел вам предстоит восстановить две исходных неубывающих последовательности одинакового размера.
Некоторые числа в исходных последовательностях известны, а некоторые заменены знаком "?".
Результат слияния известен полностью. Вам необходимо подставить на место знаков вопроса числа так, чтобы исходные последовательности были неубывающими и при слиянии образовывали заданную результирующую последовательность.

Входные данные
В первой входного файла строке содержится число N  количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса 
содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел -  результат слияния.
Выходные данные
Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если
в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.

Ввод Вывод
2
? 4
3 ?
1 3 4 5		 1 4
3 5

Разбор случаевСортировка слиянием
—Войти и решать
Мобильный интернет#23374
Мобильный интернет прочно вошел в нашу жизнь. Операторы связи предлагают различные способы оплаты мобильного интернета и, зная свои потребности, можно выбрать наиболее дешевый
из подходящих тарифов.

Рассмотрим следующие тарифные планы:
1. Единовременно каждый месяц платится 350Р за 3000 мегабайт. Также можно докупать дополнительные пакеты по 300 мегабайт за 30Р каждый, которые действуют до конца месяца.
2. 500 мегабайт в день за 29Р в сутки. За дни, в которые интернет не используется (скачано 0 мегабайт), плата не взимается.
3. Оплата за использованный трафик  1, 2Р за 1 мегабайт.
4. Безлимитный интернет на месяц за 790Р.
5. Лимитированный тариф  16000 мегабайт на месяц за 590Р.
 
По известному количеству трафика в каждый из 31 дней одного месяца определите, сколько денег уйдет на оплату интернета при использовании каждого из тарифных планов или сообщите, что использование тарифа невозможно (недостаточно трафика). 

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

Выходные данные
Выведите пять чисел в отдельных строках  стоимость трафика за месяц при использовании
соответствующего тарифа или −1, если требуемое использование интернета недопустимо в рамках
соответствующего тарифа (например, суммарный или суточный трафик превосходит ограничение
тарифа).
Стоимость требуется вывести в формате <рубли> <копейки>.

Ввод Вывод
3001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 380 0
-1
3601 20
790 0
590 0

Вычисление по заданной формулеЗадача на реализацию
✓ 0✗ 5—Войти и решать
Прямоугольное поле чудес (В, А',A)#23372
Коля попал на телеигру "Прямоугольное поле чудес". В финале этой игры Коле показали прямоугольное поле размера n х m клеток, в каждое клетке которого записано целое число.  Коля может
заменить числа в некоторых клетках на противоположные (т.е. вместо числа x записать в клетку число −x). Коля выиграет автомобиль, если сумма чисел в каждой строке и в каждом столбце будет равна нулю. Помогите Коле найти нужную расстановку чисел, либо определите, что ее не существует и Коля не сможет выиграть.
 
Формат входных данных
В первой строке записано два целых числа n и m (1 <= n, m <= 5)  - размеры поля.
В следующих n строках записано по m целых чисел, разделенных пробелами - числа, записанные в клетках поля. Все числа по модулю не превосходят 106.
 
Формат выходных данных
Если ответ существует, в первой строке выведите YES, в следующих n строках выведите по m чисел через пробел - числа в клетках поля после изменений/
Если ответа не существует, в первой строке выведите NO.
Ввод Вывод
3 3
1 1 2
2 2 4
3 3 6		 YES
1 1 -2
2 2 -4
-3 -3 6
Задача на реализациюРекурсия
✓ 13✗ 511 200средняяВойти и решать
Опять двойка (В, В')#23370
Пете нравится цифра 2. Он считает число красивым, если в его десятичной записи ровно две цифры 2. Петя хочет получить большой список красивых чисел и повесить его на стенку.
ПомогитеПете и выведите все красивые числа, не превосходищие n.
 
Формат входных данных
В первой и единственной строке записано одно целое число n (1 <= n <= 106).
 
Формат выходных данных
Выведите все целые положительные числа, не превосходящие n, в десятичной записи которых ровно две цифры 2.  Числа следует выводить в порядке возрастания, по одному на строке.
 
Ввод Вывод
179 22
122
1  
 
Замечание
Обратите внимание, что список может быть пустым, в этом случае ничего выводить не нужно.
Задача на реализациюСтроки
✓ 47✗ 77800средняяВойти и решать
Овечка Толя (C, B')#23369
Овечка Толя умеет клонироваться - тогда рядом с ней появляется такая же овечка с той же логикой и привычками.
Когда овечка встречает n стогов сена то происходит следующее:

-  Если n меньше 4 то овечка выкидывает эти n стогов сена в ближайший овраг. Иначе:

-  Если n делится на 5, то овечка сбрасывает n/5 стогов сена в ближайший овраг; клонируется;
    сама обрабатывает 3n/5 стогов сена с помощью этой же процедуры, а ее клон обрабатывает 
     оставшиеся n/5 стогов сена с помощью этой же процедуры. Иначе:
 
- Овечка съедает 4 стога сена и обрабатывает оставшиеся n-4 стогов с помощью этой же процедуры.

Овечка Толя однажды увидела n стогов сена - это число вам дано. Сколько стогов сена будет
съедено ей и всеми е клонами при описанном процессе ?
 
Формат входных данных
 В первой строке содержится натуральное число n <= 6 n <= 106
 
Формат выходных данных
Выведите количество, стогов съеденных в итоге Толей и клонами
 
Ввод Вывод
29 8
Задача на реализациюРекурсия
✓ 23✗ 24900средняяВойти и решать
Организация конференции (С, B')#23368
Недавно в солнечный весенний день директору Летней Флатландской Компьютерной Школы (ЛФКШ) Сергею Александровичу пришла в голову идея организовать первую флатландскую конференцию для школьников по программированию. Теперь перед ним стоит задача выбрать место проведения. 

Флатландия представляет собой прямоугольник из m строк и n столбцов, в каждой из клеток которого расположен один город? Сергей Александрович уже посчитал для каждого города количество желающих принять участие в конференции. Известно, что флатландцы не любят далеко ездить, так что в каком бы городе она проводилась,  в конференции смогут принять участие только школьники из самого города и соседних с ним по стороне городов. Формально говоря, если конференция проводится в городе, находящемся в i-ой строке и j-ом столбце, то в этой конференции будут участвовать школьники из городов (i, j), (i − 1, j) ( при условии, что i > 1) ,  (i + 1, j) (при условии, что i < m), (i, j − 1) (при условии, что j > 1) , и (i, j + 1) , (при условии, что j < n).
Сейчас Сергей Александрович хочет понять,  в каких городах возможно поселить всех приезжих участников.  Пока он выясняет количество доступных мест в гостиницах Флатландии, вам предстоит посчитать для каждого из возможных городов проведения, скольким школьникам потребуется предоставить жиль на время конференции.
Обратите внимание на то, что школьникам, живущим в том же городе, в котором проводится конференция, поселение не нужно.

Формат входных данных
В первой строке записаны два числа m и n (1 <= m, n <= 350) - размеры Флатландии. В каждой из последующих m строк содержатся по n чисел.
В i-ой стоке и j-ом столбце содержится число ai,j ( 0<=  ai,j  <=10000)  -  количество школьников из города (i, j),  желающих принять участие в конференции.
Формат выходных данных
Выведите m строк по n чисел в каждой. Число в строке с номером i и стобце с номером j должно равняться количеству приезжих участников конференции, если местом проведения будет
выбран город, с координатами (i, j).
 
Ввод Вывод
3 4
1 0 3 2
5 6 1 2
1 1 0 11		 5 10 3 5
8 7 11 14
6 7 13 2
1 1
5		 0
Двумерные массивыЗадача на реализацию
✓ 20✗ 21900средняяВойти и решать
Совсем другие штурмовики#23366
Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — dt , здоровье — h единиц.

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

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

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*105),  de, dt , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( de, dt , h <= 109). В следующей строке задано n натуральных чисел ai — число единиц здоровья i-го солдата армии противника (ai <= 109).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.
 
Ввод Вывод
3 3 1 1 2
1 2 3		 3
4 10 2 1 2
1 2 1 2		 5
3 1 1 2 5
1 2 3		 -1
Бинарный поискБинарный поиск по ответу
✓ 1✗ 31 200средняяВойти и решать
Коды Грея#23365
На занятиях по дискретной математике Сереже рассказали про двоичные коды Грея — это такое упорядочение всех 2n различных двоичных векторов длины n, что любые два соседних, а также первый и последний, вектора различаются ровно в одном разряде.

Для закрепления материала преподаватель задал им следующее задание: в коде Грея в каждом двоичном векторе ровно один бит заменен на знак вопроса «?». Требуется заменить обратно все знаки вопроса «?» на «0» или «1», чтобы получился код Грея.

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

Формат входных данных
В первой строке содержится целое число n — длина двоичных векторов. Следующие 2n строк содержат двоичные вектора длины n, в каждом из которых ровно один символ заменен на знак вопроса «?».
Формат выходных данных
В первой строке выведите «YES», если решение существует, и «NO» — в противном случае. В случае положительного ответа выведите исходный код Грея, если возможных вариантов ответа несколько, выведите любой.
 
Ввод Вывод
2
0?
0?
1?
1?		 YES
00
01
11
10
3
?00
0?1
01?
0?0
?10
1?1
10?
1?1		 NO

Система оценки
 
Номер подзадачи Баллы Ограничения Комментарии
1 37 1<=n<=4 Баллы начисляются, если все тесты пройдены.
2 63 1<=n<=12 Баллы начисляются, если все тесты этой и предыду- щих подзадач пройдены.

 
КонструктивРекурсия
✓ 2✗ 261 100средняяВойти и решать
Поделиться
Класснуть