Информатика

Пятачок и Винни-Пух играют в следующую игру. Перед ними лежат две кучи камней. Игроки ходят по очереди, первый ход делает Пятачок. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 61. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 61 или больше камней. В начальный момент в первой куче было четыре камня, во второй куче – S камней; 1 ≤ S ≤ 56.
 

Вопрос 1

Известно, что Винни-Пух выиграл своим первым ходом после неудачного первого хода Пятачка. Укажите минимальное значение S, когда такая ситуация возможна.

Вопрос 2

Найдите такое значение S, при котором у Пятачка есть выигрышная стратегия, причём одновременно выполняются два условия:
− Пятачок не может выиграть за один ход;
− Пятачок может выиграть своим вторым ходом независимо от того, как будет ходить Винни-Пух.

Вопрос 3

Найдите максимальное значение S, при котором одновременно выполняются два условия:
– у Винни-Пуха есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пятачка;
– у Винни-Пуха нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

 

Формат ввода ответов 

На каждое задание ответы пишите с новой строки. Например, если ответ на первый вопрос 1, на второй 2, на третий 4, то ответы надо записать так:

1
2
4

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

Входные данные представлены в файле 26-4.txt следующим образом. В первой строке входного файла записаны два целых числа: N – общее количество коробок и M – грузоподъёмность подъемника в кг. Каждая из следующих N строк содержит одно целое число – массу груза в кг. В ответе запишите два целых числа: сначала максимально возможное количество коробок, затем их общую массу.
Пример организации исходных данных во входном файле: 
8 800
110
70
130
140
80
90
160
45
Ответ: 7 780

В данном случае ответ сформировался следующим образом: сначала выбрали самые большие коробки массой 160+140+130+110=540, далее у нас есть несколько вариантов добавить коробки, из которых выбираем сочетание: 90+80+70, итого 780.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «спросил» или «Спросил» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова "спросил" учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «комендант» или "Комендант" в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf).  Другие формы слова «комендант» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «лошадь» или «Лошадь» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf).  Другие формы слова «лошадь» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «офицер» или «Офицер» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «офицер» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «Петрович» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «Петрович» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «господин» или "Господин" в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «господин» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «Иван» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «Иван» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «Пугачев» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «Пугачев» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «служба» или «Служба» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «служба» учитывать не следует. В ответе укажите только число.

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «дочь» или «Дочь» в историческом романе А.С. Пушкина «Капитанская дочка» (файл task10.rtf). Другие формы слова «дочь» учитывать не следует. В ответе укажите только число.

Имеются сведения о результатах соревнований по школьному многоборью. Многоборье состоит из соревнований по четырем видам спорта, участие в каждом из которых оценивается баллами от 0 до 10 (0 баллов получает ученик, не принимавший участия в соревнованиях по данному виду спорта). Победители определяются по наибольшей сумме набранных баллов. Известно, что общее количество участников соревнований не превосходит 1000. 

Входные данные представлены в файле 26-2.txt следующим образом.
В первой строке вводится количество учеников, принимавших участие в соревнованиях, N. Далее следуют N строк, имеющих следующий формат: 
<номер участника> <Баллы> ,
где:
 - <Номер участника> – целое число ;
- <Баллы> - строка, содержащая четыре целых числа, разделенных пробелом, соответствующих баллам, полученным на соревнованиях по каждому из четырех видов спорта.
При этом <Номер участника> и <Баллы> разделены одним пробелом.

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

Пример входного файла:         
5
1 5 8 6 2 
2 9 9 5 7 
3 0 0 0 0  
4 0 10 5 7 
5 8 7 7 8 

При таких исходных данных получается четыре победителя, поэтому ответ для приведенного примера: 2 103

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов.
Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.

Входные данные представлены в файле 26-1.txt следующим образом. В первой строке входного файла находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 10 000) и N – количество пользователей (натуральное число, не превышающее 2000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке. 

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

Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40
и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера: 2 50
 

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

Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень монотонности» — число одинаковых блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив a, то «степень монотонности» будет равна количеству индексов i, таких что a_i = a_{i - 1}. Для начала вас просят найти не само распределение блюд, а хотя бы минимальную возможную «степень монотонности», которую можно было бы получить некоторой перестановкой заданного набора блюд. Помогите армейской столовой!
Входные данные
В первой строке содержится число n — количество блюд, которые должны войти в расписание (1 ≤ n ≤ 100).
В следующей строке содержится n чисел a_i — блюда (1 ≤ a_i  ≤ 100). Одинаковые блюда обозначены одинаковыми числами, разные — разными.
Выходные данные
В единственной строке выведите одно число — минимальное возможное значение «степени монотонности».
 

Ввод	Вывод
5 1 2 3 1 1	0
6 1 1 2 3 1 1	1

Недавно Вася решил всерьез заняться машинным обучением и распознаванием образов. Однако, наука это обширная, а начинать с чего-то надо, поэтому его учитель информатики посоветовал ему начать с анализа ASCII рисунков.
Он дал Васе рисунок ASCII-графика, который выглядит следующим образом: он представляет собой прямоугольник n × m, состоящий из символов «*» и «.». Левая верхняя клетка прямоугольника считается началом координат — точкой (0, 0), верхняя строка таблицы — осью OX, направленной слева направо, а левый столбец — осью OY, направленной сверху вниз. Таким образом, клетка (x, y) таблицы отвечает за точку (x, y) на графике функции, и если в этой клетке таблицы стоит «*», то f(x) = y, а противном случае в клетке таблицы стоит «.». Гарантируется, что функция, график которой дан Васе, непрерывна и однозначно определена на всем промежутке, то есть:
В каждом столбце таблицы стоит ровно один символ «*»;
В соседних столбцах символы «*» находятся либо в соседних по стороне, либо в соседних по углу клетках.
Для начала, чтобы проанализировать этот график, Вася хочет найти количество локальных максимумов в нем, то есть таких x, что f(x - 1) < f(x) > f(x + 1) (если одно из значений f(x - 1) или f(x + 1) не определено, счиается, что неравенство выполняется).
Входные данные
В первой строке входного находятся два натуральных числа n и m — количество строк и количество столбцов в таблице соответственно (1 ≤ n, m ≤ 100).
В каждой из следующих n строк содержится строка из m символов — описание таблицы. Гарантируется, что таблица представляет собой график функции, описанной в условии.
Выходные данные
В единственной строке выведите одно число — количество локальных максимумов в
данном графике функции.
 

Ввод	Вывод
3 7 *.*...* .*.*.*. ....*..	2
3 5 ..... ****. ....*	1

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Ввод	Вывод
2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	2 3 1 2 1 1 1 1

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.
 

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
 -  Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит. Если указанного свойства не существует, ничего делать не нужно.
 -  Найти количество удаленных свойств у объекта r
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число k_i - количество свойств у i-го объекта, а затем через пробел даны k_i чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

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

Ввод	Вывод
2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	1 0 2 1 2 2 2 2

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта 1 удаленное свойство, а у второго все еще 0.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта теперь 2 удаленных свойства, а у второго 1.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов становится 2 удаленных свойства.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество удаленных свойств у объектов.
 

Пример

№	Входные данные	Выходные данные
1	Pupkin Vasya	Vasya Pupkin