Упражнения

Входные данные для всех задач записаны в файле input.txt, результат работы нужно вывести в файл output.txt.

01: Числа могут быть где угодно

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

Указание. Считайте весь файл в строковую переменную при помощи метода read() и разбейте ее на части при помощи метода split().

  2

 2

4

02: Обращение строки

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

Строка во входном файле заканчивается символом конца строки '\n', он не должен стать первым. Строка в выходном файле должна заканчивается символом конца строки '\n'.

hello world
 

dlrow olleh
 

03: Построчное обращение

Выведите все строки данного файла в обратном порядке. Для этого считайте список всех строк при помощи метода readlines().

Последняя строка входного файла обязательно заканчивается символом '\n', он не должен стать первым. Последняя строка в выходном файле должна заканчивается символом конца строки '\n'.

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
 

Complex is better than complicated.
Simple is better than complex.
Explicit is better than implicit.
Beautiful is better than ugly.
 

04: Обращение всего файла

Выведите в обратном порядке содержимое всего файла полностью. Для этого считайте файл целиком при помощи метода read().

Последняя строка в выходном файле должна заканчивается символом конца строки '\n'.

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
 

.detacilpmoc naht retteb si xelpmoC
.xelpmoc naht retteb si elpmiS
.ticilpmi naht retteb si ticilpxE
.ylgu naht retteb si lufituaeB
 

05: Длинные строки

В выходной файл выведите все строки наибольшей длины из входного файла, не меняя их порядок.

В данной задаче удобно считать список строк входного файла целиком при помощи метода readlines().

One
Twenty one
Two
Twenty two
 

Twenty one
Twenty two
 

06: Поиск символа

Определите, есть ли во входном файле символ '@'. Выведите слово YES или NO.

Входной файл может быть очень большим, поэтому считывать файл нужно посимвольно.

Valid email:
Bilbo.Baggins@bagend.hobbiton.shire.me

YES

Hello, world!

NO

07: Сумма чисел в строкaх

Дан файл, каждая строка которого может содержать одно или несколько целых чисел, разделенных одним или несколькими пробелами.

Вычислите сумму чисел в каждой строке и выведите эту сумму (для каждой строки выводится сумма чисел в этой строке).

В данной задаче удобно считывать данные построчно.

2 2
 3    4
1       5

4
7
6

08: Сумма чисел в файле

В файле могут быть записаны десятичные цифры и все, что угодно. Числом назовем последовательность цифр, идущих подряд (т.е. число всегда неотрицательно).

Вычислите сумму всех чисел, записанных в файле. В данной задаче удобно считывать данные посимвольно.

 123
aaa456
1x2y3 4 5 6

600

09: Статистика по файлу

Дан файл. Определите сколько в нем букв (латинского алфавита), слов, строк. Выведите три найденных числа в формате, приведенном в примере.

Для экономии памяти читайте файл посимвольно, то есть не сохраняя целиком в памяти файл или отдельные его строки.

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
 

Input file contains:
108 letters
20 words
4 lines
 

10: Шифр Цезаря - 2

Зашифруйте данный текстовый файл шифром Цезаря, при этом символы первой строки файла должны циклически сдвигаться на 1, второй строки — на 2, третьей строки — на три и т.д.

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

Hello
Hello
Hello
Hello

Ifmmp
Jgnnq
Khoor
Lipps

11: Анаграммы

Даны две строки. Определите, можно ли получить одну из другой перестановкой букв.

Программа получает на вход две строки, содержащие только ASCII-символы, не содержащие пробелы.

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

eleven_plus_two
twelve_plus_one

YES

Eleven_plus_two
Twelve_plus_one

NO

12: Числа

Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.

Во входном файле записано два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100000 цифр.

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

280138
798081

8810

123
456

-1

13: Палиндром

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

PARALLELOGRAM

ALRARLA

ONE

E

14: Семипроцентный барьер

В Государственную Думу Федерального Собрания Российской Федерации выборы производятся по партийным спискам. Каждый избиратель указывает одну партию, за которую он отдает свой голос. В Государственную Думу попадают партии, которые набрали не менее 7% от числа голосов избирателей.

Дан список партий и список голосов избирателей. Выведите список партий, которые попадут в Государственную Думу.

В первой строке входного файла написано слово PARTIES:. Далее идет список партий, участвующих в выборах.

Затем идет строка, содержащая слово VOTES:. За ним идут названия партий, за которые проголосовали избиратели, по одному названию в строке. Названия могут быть только строками из первого списка.

Программа должна вывести названия партий, получивших не менее 7% от числа голосов в том порядке, в котором они следуют в первом списке.

PARTIES:
Party one
Party two
Party three
VOTES:
Party one
Party one
Party three
Party one
Party one
Party three
Party two
Party one
Party three
Party three
Party one
Party one
Party three
Party three
Party one

Party one
Party three

15: Упорядочить список партий по числу голосов

Формат входных данных аналогичен предыдущей задаче. Выведите список всех партий, участвовавших в выборах, отсортировав его в порядке убывания количества голосов избирателей, а при равном количестве голосов - в лексикографическом порядке.

PARTIES:
Party one
Party two
Party three
VOTES:
Party one
Party two
Party three
Party two
Party three

Party three
Party two
Party one

16: Выборы Президента

В выборах Президента Российской Федерации побеждает кандидат, набравший свыше половины числа голосов избирателей. Если такого кандидата нет, то во второй тур выборов выходят два кандидата, набравших наибольшее число голосов.

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

Если есть кандидат, набравший более 50% голосов, программа должна вывести его имя. Если такого кандидата нет, программа должна вывести имя кандидата, занявшего первое место, затем имя кандидата, занявшего второе место.

Полуэкт Варфоломеев
Варфоломей Полуэктов
Полуэкт Варфоломеев

Полуэкт Варфоломеев

Полуэкт Варфоломеев
Варфоломей Виссарионов
Виссарион Полуэктов
Варфоломей Виссарионов
Варфоломей Виссарионов
Полуэкт Варфоломеев

Варфоломей Виссарионов
Полуэкт Варфоломеев

17: Выборы Государственной Думы

Статья 83 закона “О выборах депутатов Государственной Думы Федерального Собрания Российской Федерации” определяет следующий алгоритм пропорционального распределения мест в парламенте.

Необходимо распределить 450 мест между партиями, участвовавших в выборах. Сначала подсчитывается сумма голосов избирателей, поданных за каждую партию и подсчитывается сумма голосов, поданных за все партии. Эта сумма делится на 450, получается величина, называемая “первое избирательное частное” (смысл первого избирательного частного - это количество голосов избирателей, которое необходимо набрать для получения одного места в парламенте).

Далее каждая партия получает столько мест в парламенте, чему равна целая часть от деления числа голосов за данную партию на первое избирательное частное.

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

На вход программе подается список партий, участвовавших в выборах. Каждая строка входного файла содержит название партии (строка, возможно, содержащая пробелы), затем, через пробел, количество голосов, полученных данной партией – число, не превосходящее 10⁸.

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

Party One 100000
Party Two 200000
Party Three 400000

Party One 64
Party Two 129
Party Three 257

18: Проходной балл

Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.

В конкурсе участвует N человек, при этом количество мест равно K. Определите проходной балл, то есть такое количество баллов, что количество участников, набравших столько или больше баллов не превосходит K, а при добавлении к ним абитуриентов, набравших наибольшее количество баллов среди непринятых абитуриентов, общее число принятых абитуриентов станет больше K.

Программа получает на вход количество мест K. Далее идут строки с информацией об абитуриентах, каждая из которых состоит из имени (текстовая строка содержащая произвольное число пробелов) и трех чисел от 0 до 100, разделенных пробелами.

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

Также возможны две ситуации, когда проходной балл не определен.

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

Если количество абитуриентов, имеющих равный максимальный балл больше чем K, программа должна вывести число 1.

Решение должно использовать O(1) памяти, то есть нельзя использовать списки, длина которых зависит от длины входных данных

5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Иван 60 70 70
Ким Чен Ир 50 50 50
Ким Ир Сен 40 40 40

200

1
Иванов Сергей 40 40 40
Сергеев Петр 100 100 39

0

1
Иванов Сергей 60 60 60
Сергеев Петр 100 40 40

1

19: Полупроходной балл

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

Программа должна вывести значение полупроходного балла, если полупроходного балла не существует, программа должна вывести одно число 0.

Решение должно использовать O(1) памяти, то есть нельзя использовать списки, длина которых зависит от длины входных данных

5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Иван 60 70 70
Ким Чен Ир 50 50 50
Ким Ир Сен 40 40 40

150

1
Иванов Сергей 50 50 50
Сергеев Петр 100 100 100
Ким Ир Сен 100 0 100

0

20: Призеры олимпиады

В олимпиаде участвовало N человек, каждый из которых мог набрать от 0 до 100 баллов. По положению об олимпиаде жюри может наградить не более 45% от числа участников, округляя их число до целого при необходимости вниз.

При этом если последний участник, попавший в 45% набирает столько же баллов, сколько первый участник, не попавший в 45%, то решение по этим участникам, и всем участникам, набравшим такой балл принимается следующим образом:

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

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

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

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

Решение должно использовать O(1) памяти, то есть нельзя использовать списки, длина которых зависит от длины входных данных

Иванов Сергей 70
Сергеев Петр 30
Петров Василий 40
Васильев Андрей 80
Андреев Денис 50
Денисов Роман 90
Романов Иван 70
Ким Чен Ир 60
Ким Ир Сен 100

70

Иванов Сергей 50
Сергеев Петр 70
Петров Василий 40
Васильев Андрей 10
Андреев Денис 50
Денисов Роман 20
Романов Иван 30
Ким Чен Ир 70
Ким Ир Сен 100

70

Иванов Сергей 30
Сергеев Петр 60
Петров Василий 20
Васильев Андрей 100
Андреев Денис 30
Денисов Роман 80
Романов Иван 20
Ким Чен Ир 40 
Ким Ир Сен 10

40

21: Поезда

Некоторый поезд в пути следования останавливается на N станциях (станция номер 1 — начальная, а станция номер N — конечная). Дан список пассажиров поезда, для каждого из которых известно, на какой станции он садится, а на какой — выходит. Определите, на каких перегонах (то есть между какими соседними станциями) в поезде было наибольшее число пассажиров.

Первая строка входного файла содержит количество станций N. В следующих строках находится информация о пассажирах в следующем формате:

Фамилия Имя станция_посадки станция_выхода

Программа должна вывести список перегонов, на которых в поезде было набольшее число пассажиров. Каждый перегон выводится в виде двух последовательных номеров станций, разделенных знаком “-”.

5
Иванов Сергей 1 5
Сергеев Петр 3 5
Петров Кирилл 1 2

1-2
3-4
4-5

22: Гистограмма

Вовочка ломает систему безопасности Пентагона. Для этого ему понадобилось узнать, какие символы в секретных зашифрованных посланиях употребляются чаще других. Для удобства изучения Вовочка хочет получить графическое представление встречаемости символов. Поэтому он хочет построить гистограмму количества символов в сообщении. Гистограмма – это график, в котором каждому символу, встречающемуся в сообщении хотя бы один раз, соответствует столбик, высота которого пропорциональна количеству этих символов в сообщении.

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

Для каждого символа c кроме пробелов и переводов строк выведите столбик из символов «#», количество которых должно быть равно количеству символов c в данном тексте. Под каждым столбиком напишите символ, соответствующий ему. Отформатируйте гистограмму так, чтобы нижние концы столбиков были на одной строке, первая строка и первый столбец были непустыми. Не отделяйте столбики друг от друга. Отсортируйте столбики в порядке увеличения кодов символов.

Hello, world!

     #   
     ##  
#########
!,Hdelorw

Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;

All mimsy were the borogoves,
And the mome raths outgrabe.

         #              
         #              
         #              
         #              
         #              
         #         #    
         #  #      #    
      #  # ###  ####    
      ## ###### ####    
      ##############    
      ##############  ##
#  #  ############## ###
########################
,.;ADTabdeghilmnorstuvwy

23: Покер

Даны 5 целых чисел, каждое от 1 до 13. Выведите одну из следующих строк:

• если все 5 числе одинаковы, то выведите "Impossible", иначе
• если одинаковы 4, то вывести "Four of a Kind", иначе
• если одинаковы 3 и 2, то вывести "Full House", иначе
• если есть 5 последовательных, то вывести "Straight", иначе
• если одинаковы 3, то вывести "Three of a Kind", иначе
• если одинаковы 2 и 2, то вывести "Two Pairs", иначе
• если одинаковы 2, то вывести "One Pair", иначе
• вывести "Nothing".

1 3 9 3 2

One Pair

1 5 5 4 4

Two Pairs

1 5 2 4 3

Straight

10 11 12 13 1

Nothing

24: Быки и коровы

В игре “Быки и коровы” один игрок загадывает четырехзначное число, состоящее из различных цифр, а другой игрок угадывает это число, называя также четырехзначные числа с различными цифрами. Загадавший число на каждое из названных чисел сообщает, сколько в нем “быков” (т. е. цифр, которые не только присутствуют и в задуманном, и в названном числе, но даже стоят на одних и тех же местах) и “коров” (цифр, которые присутствуют в обоих числах, но стоят на разных местах).

Дана запись партии (последовательность тестовых чисел и ответов на них), но задуманное число неизвестно. Определите задуманное число.

Во входном файле содержится несколько строк, в каждой строке записано по три числа. Первое – названное четырехзначное число (оно не начинается с нуля), второе – количество “быков”, третье – количество “коров”.

Требуется вывести одно задуманное четырёхзначное число. Это число не начинается с 0.

Гарантируется, что ответ в задаче существует и является единственным.

1234 0 0
5678 2 2
6578 0 4

5687

25: Домино

Проводя генеральную уборку на дачном чердаке, Саша нашел в комоде кучу доминошек из разных наборов. Каждая доминошка представляет собой прямоугольник, разделенный на две половинки. На каждой из половинок нарисовано от 0 до 6 точек. Ориентации доминошки не имеют — их можно как угодно поворачивать.

В совсем раннем детстве Саша видел, как играют в домино: суть игры заключается в том, что надо брать доминошку и как можно громче колотить ею об стол, крича при этом «рыба!». Услышав доносящийся с чердака грохот, наверх поднялся Сашин дедушка. Он смог объяснить Саше настоящие правила игры в домино: игроки составляют длинную цепочку, в которой соседние доминошки касаются половинками с одинаковым числом точек.

Саше решил называть «дружными доминошками» пару доминошек, которые можно поставить в игре рядом (т.е. доминошки в паре соприкасаются половинками с равными числами) в том или ином порядке. Играть в домино ему не с кем, поэтому Саша развлекается тем, что всевозможными способами составляет пары и считает количество «дружных доминошек».

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

В первой строке входного файла содержится натуральное число \(N\) — количество доминошек (\(1 \le N ≤ 100000\)).

В каждой из последующих строк содержится описание доминошки: два целых числа \(X\) и \(Y\) (\(0 \le X, Y \le 6\)) — количество точек на каждой из половинок доминошки.

Выведите одно число — количество пар «дружных доминошек».

2
1 2
2 1

1

5
1 2
2 3
3 1
4 3
4 3

8

Примечание. Во втором тесте дружными являются следующие пары: 1-2 2-3, 1-2 3-1, 2-3 3-1, 2-3 4-3, 2-3 4-3, 3-1 4-3, 3-1 4-3, 4-3 4-3

26: Школа танцев

В школу бальных танцев профессора Падеграса записались \(n\) учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора?

В первой строке задано число \(n\) (\(1 \le n \le 10^6\)). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из \(n\) символов a и b (символ a соответствует девочке, а символ b — мальчику).

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

3
bab

2

8
abbababa

13

27: Банковские карты

Банк переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Вводится натуральное число \(X\) без ведущих нулей (\(1 \le X < 10^{1000}\)).

Выведите искомое \(N\) без ведущих нулей.

179

2

12013456789

22

28: Драгоценные камни

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

Купцы хотят продать шаху \(n\) драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет. Видов драгоценных камней на Востоке известно не очень много всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. Он заранее определил несколько упорядоченных пар типов камней: \((a_1, b_1)\), \((a_2, b_2)\), ..., \((a_k, b_k\)). Эти пары он называет красивыми, их множество мы обозначим как \(P\). Теперь представим ряд камней, которые продают купцы, в виде строки \(S\) длины \(n\) из строчных букв латинского алфавита. Шах считает число таких пар \((i, j)\), что \(1 \le i \lt j \le n\), а камни \(S_i\) и \(S_j\) образуют красивую пару, то есть существует такое число \(1 \le q \le k\), что \(S_i = a_q\) и \(S_j = b_q\).

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

Первая строка входного файла содержит целые числа \(n\) и \(k\) (\(1 \le n \le 100000\), \(1 \le k \le 676\)) число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку \(S\), описывающую типы камней, которые привезли купцы.

Далее следуют \(k\) строк, каждая из которых содержит две строчных буквы латинского алфавита и описывает одну из красивых пар камней.

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

7 1
abacaba
aa

6

7 3
abacaba
ab
ac
bb

7