Информатика

2 621 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
Витя работает недалеко от одной из станций кольцевой линии Московского метро, а живет рядом с другой станцией той же линии. Требуется выяснить, мимо какого наименьшего количества промежуточных станций необходимо проехать Вите по кольцу, чтобы добраться с работы домой.

Входные данные
Станции пронумерованы подряд натуральными числами 1, 2, 3, …, N (1-я станция – соседняя с N-й), N не превосходит 100.

Вводятся три числа: сначала N – общее количество станций кольцевой линии, а затем i и j – номера станции, на которой Витя садится, и станции, на которой он должен выйти. Числа i и j не совпадают. Все числа разделены пробелом.

Выходные данные
Требуется выдать минимальное количество промежуточных станций (не считая станции посадки и высадки), которые необходимо проехать Вите.

Примеры
Входные данные Выходные данные Пояснения
1 100 5 6 0 На кольцевой линии 100 станций; проехать с 5-й на 6-ю станцию Витя может напрямую, без промежуточных станций
2 10 1 9 1 На кольцевой линии 10 станций; проехать с 1-й на 9-ю станцию Витя может через одну промежуточную, ее номер 10
В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй — с (K+1)-й по (2*K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Входные данные
Вводятся два числа: K - количество строк, которое печатается на странице, и N - номер строки (1<=K<=200, 1<=N<=20000).

Выходные данные
Выведите два числа - номер страницы, на которой будет напечатана эта строка, и номер строки на странице.
 
Примеры
Входные данные Выходные данные
1 50 1 1 1
2 20 25 2 5
3 15 43 3 13
Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара не заканчивается на подстроку «fixed», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На товары, название которых заканчивается на подстроку «fixed», скидка не распространяется. 

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

Выходные данные
Выведите одно число - итоговую стоимость покупки.
 
Примеры
Входные данные Выходные данные Пояснение
1 5
bananassale 10 x2
breadfixed 5 x5
colafixed 20 x2
gumsale 9 x10
tea 2 x15
166 В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 1 соответственно.
Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+1⋅15=166$.

 
✓ 39✗ 104700средняяВойти и решать
Представьте, что вас наняли в IT отдел сетевого продуктового магазина. Со следующего месяца планируется ввести скидку в 20% на некоторые товары. От вас требуется написать программу расчета финальной стоимости покупки с учетом всех скидок.

Покупка задается в виде списка товаров, где каждый товар описывается в формате <НазваниеТовара> <цена> x<количество>. Если название товара заканчивается на подстроку «sale», то цена на товар при финальном расчете покупки уменьшается на 20% с округлением до целого числа в меньшую сторону. Так, например, если цена товара была 12 рублей, с учетом скидки она составит 9 рублей. На остальные товары скидка не распространяется.

Суммарная стоимость каждого товара вычисляется по формуле finalPrice⋅x, где finalPrice - финальная цена, возможно, с учетом скидки и округлением, а x - количество товара в списке покупок. 
Ваша задача - вычислить итоговую стоимость покупки.

Входные данные
В первой строке дано число n - число наименований товаров в покупке (1≤n≤1000).
В следующих n строках заданы описания товаров в покупке в формате: <НазваниеТовара> <цена> x<количество>.
Название товара состоит из не более чем 20 строчных латинских букв. Цена - натуральное число, которое строго больше 1, но не больше 1000. Количество - натуральное число не больше 100.

Выходные данные
Выведите одно число - итоговую стоимость покупки.
 
Примеры
Входные данные Выходные данные Пояснение
1 5
bananassale 10 x2
breadfixed 5 x5
colafixed 20 x2
gumsale 9 x10
tea 2 x15
181 В тесте из примера итоговые стоимости товаров составят: 8, 5, 20, 7 и 2 соответственно. Итоговая стоимость покупки: 8⋅2+5⋅5+20⋅2+7⋅10+2⋅15=181.

 
✓ 57✗ 83600лёгкаяВойти и решать

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)


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

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.


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

Выведите одно число - количество вариантов.

 

 

Примеры
Входные данные Выходные данные
1 3 7  2
2 1 8 1
3 3 6 4

 

У мальчика Пети есть муравьиная ферма. На ферме есть участок прямоугольной формы, состоящий из NxM квадратов. В правом нижнем квадрате данной области имеется дырка, благодаря которой можно сбежать с фермы. Каждый день очередной муравьишка начинает свой путь с левой верхней клетки. Далее он перемещается в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться он не может), и двигается так до достижения правой нижней клетки. Затем он выбирается наружу. Каждый муравьишка двигается своим уникальным путем (т.е. никакой муравей не повторяет ни один путь другого). Если муравей не может пойти по своему уникальному пути, то он остается на ферме. Посчитайте, сколько муравьев сбежит с фермы и поселится в комнате Пети.
 
Входные данные
Вводятся два числа N и M - размеры таблицы (\(1<=N<=10\), \(1<=M<=10\)).

Выходные данные
Выведите искомое количество способов.

Примечание
При указанных ограничениях число способов входит в тип Longint.
 

 

Примеры
Входные данные Выходные данные
1 1 10 1

 

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки. 
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

Определите, какое наименьшее число туров необходимо отыграть для того, чтобы получить из заданное число баллов N.

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

Программа получает на вход одно число, не превосходящее 106.


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

Требуется вывести одно число: наименьшее количество искомых операций.

 

 

Примеры
Входные данные Выходные данные
1 1 0
2 5 3
3 32718 17

 

Заботливые хозяева квартиры заботятся о таракане Василии. Вечером они выкладывают для него в ряд N хлебных крошек, которые он очень любит. Переходя от одной хлебной крошки к другой, таракан Василий может съесть ее, а может и не съесть. Но он никогда не ест две хлебные крошки подряд.
Посчитайте сколько различных вариантов полакомиться хлебными крошками есть у таракана Василия.

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

На вход программы поступает целое число N  (\(1<=N<=100\) ).


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

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

 

 

Примеры
Входные данные Выходные данные
1 1 2

 

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.


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

Вводится одно число \(0 < N < 31\).


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

Выведите одно число — количество "маршрутов" Радуги.

 

 

Примеры
Входные данные Выходные данные
1 4 7

 

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

Используя данный словарь, проверьте речь Стича на правильность расстановки ударения. Определите количество ошибок, которое сделает Стич.

Входные данные
Сначала вводится число N — количество слов в словаре (\(0 <= N <=20000\)).
Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет запись разговора Стича. Разговор представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Стич поставил ударение). Стич мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные 
Выведите количество ошибок в речи Стича.
 
Примеры
Входные данные Выходные данные Примечание
1
4
cAnnot
cannOt
fOund
pAge
thE pAge cAnnot be found
2
В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Стичем - это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Стич поставил ровно одно ударение, признается верным.
2
4
cAnnot
cannOt
fOund
pAge
The PAGE cannot be found
4
Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

 

✓ 309✗ 848600лёгкаяВойти и решать
Нани с первых минут невзлюбила Стича и даже боялась оставаться вместе с ним в одном доме. Но спустя время она разглядела в малыше добрую душу и приняла его в свою семью. Вместе со Стичем пришлось приютить и его создателя Джамбо, которому пришлось остаться на Земле. 
Чтобы запомнить имена новых знакомых инопланетян, Джамбо вносит их в компьютер. Имена инопланетянин могут содержать самые различные символы, но всегда удовлетворяют особым правилам. Правила следующие: все имена содержат только латинские буквы (заглавные и строчные), цифры и знак подчёркивания. Имя всегда начинается либо с буквы, либо со знака подчеркивания. Другие символы в именах отсутствуют. 
Напишите для Джамбо программу, которая бы проверяла правильно ли он занес в компьютер имя очередного знакомого.

Входные данные
На вход программы подаётся символьная строка - имя, которое Джамбо занес в компьютер.

Выходные данные
Программа должна вывести ответ 'YES', если строка представляет собой имя, составленное по правилам задачи, и 'NO' в противном случае.  

 
Примеры
Входные данные Выходные данные
1
Abc123
YES
2
Abc[a!
NO

 

✓ 519✗ 1 044400лёгкаяВойти и решать
Стич всегда готов поделиться кусочком пирога с другом, помочь Лило построить лучший замок из песка и приготовить завтрак для всей семьи. Бери пример :)

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


Входные данные
Каждая строка содержит название блюда, затем через пробел идет количество (натуральное число не превышающее 500000). Последняя строка содержит единственное слово "END!" - признак окончания ввода.

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

 
Примеры
Входные данные Выходные данные
1 Yapper 10
Yapper 5
Clip 9
Clip 8
Yapper 1
END!
Clip 17
Yapper 16

 

✓ 533✗ 534500лёгкаяВойти и решать

Стич - генетический эксперимент 626, созданный злым гением Джамбой Джукибой. И на сколько бы милым не получился Стич по окончании эксперимента, Джамбо все-таки увидел в нем разрушительный потенциал и продолжил работу над ним. Но до того, как закончить работу над Стичем они оба были задержаны Галактической полицией.
Стич был приговорен Верховной Советницей к пожизненной ссылке на пустынный астероид, но по пути сбегает и оказывается на нашей планете на гавайском острове Кауаи, где любовь и забота Лило превратили злого инопланетянина в доброго и отзывчивого друга! Джамбо Джукибо - инопланетянин с планеты Квилтакуан (Kweltikwan). Был отправлен на Землю для поимки Эксперимента 626. Чтобы миссия состоялась Джамбо должен был изучить английский язык. Для этого он создал англо-квилтакуанский словарь. К каждому английскому слову, которое он встречал, Джамбо записывал в словарь несколько слов-переводов на квилтакуанском.
К сожалению, он поздно понял, что ему также необходим квилтакуанско-английский словарь. Он решил сделать квилтакуанско-английский словарь из англо-квилтакуанского за время полета. 
Для каждого квилтакуанского слова, встречающегося в словаре, Джамбо хочет найти все его переводы (то есть все английские слова, для которых квилтакуанское слово встречалось в его списке переводов), и считать их и только их переводами этого квилтакуанского слова.
Помогите Джамбо выполнить работу по созданию квилтакуанско-английского словаря, чтобы он успел к моменту прилета на нашу планету его выучить.

Входные данные
В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на квилтакуанский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.
Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100000.

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

Порядок вывода слов может быть любым. Это касается как самих слов в словаре, так и слов, означающих перевод.

 

Примеры
Входные данные Выходные данные
1 3
apple - malum, pomum, popula
fruit - baca, bacca, popum
punishment - malum, multa
7
baca - fruit
bacca - fruit
malum - apple, punishment
multa - punishment
pomum - apple
popula - apple
popum - fruit

 

✓ 172✗ 454700средняяВойти и решать
Жизнерадостный инопланетянин Стич пытается освоиться на нашей планете и выучить английский язык. Пока он мало что может произнести, но уже может отличить одно слово от другого, хотя возможно он их и не понимает. Сейчас Стич проводит наблюдения за Лилой, и для каждого услышанного слова он произносит сколько раз оно уже было произнесено Лилой ранее. Когда Лило надоедает слушать бормочущего Стича, она называет его по имени и Стич останавливается. Джамба Джукиба, который стал другом Лило и Нани, решил проверить Стича, правильно ли он ведет счет. Помогите ему написать для этого программу.

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

Входные данные
Программа получает на вход текст. Признаком конца текста является слово STITCH, которое располагается в последней строке, других слов в последней строке нет. 

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

 

Примеры
Входные данные Выходные данные
1 one two one tho three
STITCH
0 0 1 0 0
2 a b a c a b a d a b a c a b a
STITCH
0 0 1 0 2 1 3 0 4 2 5 1 6 3 7 

 

✓ 104✗ 148600лёгкаяВойти и решать

Напишите программу, которая вычисляет сумму элементов матрицы.

Входные данные: в первой строке записаны через пробел размеры матрицы: количество строк и количество столбцов ( 1 <= M <= 100 ). В следующих строках записаны строки матрицы, в каждой – по натуральных чисел, разделённых пробелами.

Выходные данные: программа должна вывести одно число – сумму элементов матрицы.

Пример.
Входные данные Выходные данные
1 4 5
1 2 3 4 5
6 12 8 9 10
11 12 12 14 15
16 17 18 12 20
207
Алфавитно-частотный словарь - это частотный словарь, в котором слова с указанием их частоты (встречаемости) расположены по алфавиту.
Постройте словарь, отсортированный по частоте слов, в котором слова расположены порядке уменьшения их частоты встречаемости, справа от каждого слова должно быть указано сколько раз оно встречается в тексте. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке.  Признаком окончания текста является "END!". 

Входные данные
На вход подаются строки текста. Последняя строка содержит одно единственное слово "END!" и является признаком окончания текста.

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

 
Примеры
Входные данные Выходные данные
1 один два
три один
два
END!
два 2
один 2
три 1
✓ 707✗ 2 152500лёгкаяВойти и решать
На вход подается одна строка, в которой записаны фамилия и имя человека (разделенные ровно одним пробелом).
 
Выведите эту же информацию, однако сначала имя, а потом фамилию.
 
Пример
Входные данные Выходные данные
1 Pupkin Vasya Vasya Pupkin
 
✓ 16✗ 70500лёгкаяВойти и решать
Словарь синонимов — описывает синонимические ряды, то есть группы слов, имеющих тождественное или достаточно близкое значение. Словарь синонимом часто используют копирайтеры.
У вас имеется словарь, состоящий из пар слов-синонимов. Все слова в словаре различны. Выведите к предлагаемому слову синоним.

Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, в каждой из которых содержится ровно два слова-синонима. В последней N+1 строке следует одно слово.

Выходные данные
Выведите на экран синоним к данному слову.

Примечание
Используйте в своей программе словарь.
 


Примеры
Входные данные Выходные данные
1 2
Dictionary Map 
List Array
Array
List

 

✓ 1 149✗ 789400лёгкаяВойти и решать
Даша предлагает Маше сыграть в следующую игру. Даша пишет на листочке одно число, а задача Маши записать другое число, используя только цифры, которые есть в числе Даши. Напишите программу, которая выводит цифры, используемые Машей для записи своего числа, если Маша выполнила условие Даши, в противном случае выведите на экран слово losing

Входные данные: на вход подаются два натуральных числа (сначала число Даши, затем число Маши), не превыщающие 109. Каждое число в отдельной строке
Выходные данные: выведите в порядке возрастания требуемые цифры, или слово losing

 

Примеры
Входные данные Выходные данные
1 5112648
1246
1 2 4 6
2 64141
1246
losing

 

✓ 49✗ 133600лёгкаяВойти и решать
Маша предлагает Мише сыграть в следующую игру. Маша пишет на листочке два числа, а перед Мишей лежат карточки с цифрами от 0 до 9. Задача Миши выбрать себе такие карточки, на которых записаны цифры, которые используются для записи как первого числа, так и второго.

Входные данные: на вход подаются два натуральных числа, не превыщающие 109. Каждое число в отдельной строке
Выходные данные: выведите на экран в порядке возрастания карточки, которые должен взять Миша. Если Миша не может взять ни одной карточки, то выведите -1

 

Примеры
Входные данные Выходные данные
1 514
233
-1
2 1248
3472
2 4

 

✓ 103✗ 133500лёгкаяВойти и решать
Поделиться
Класснуть