Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Следующий палиндром#34850

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

Ввод	Вывод
4321	4334

Вывод формулы Строки

✓ 18✗ 1041 000средняяВойти и решать

Заработная плата#34832

В некоторой компании работают три сотрудника — Алексей, Виктор и Сергей. Их месячный оклад составляет A, B и C рублей соответственно. При этом Алексей работает на полную ставку, а Виктор и Сергей — на половину ставки, то есть работают вдвое меньше, чем Алексей.

По итогам месяца директор компании хочет распределить между этими сотрудниками премиальный фонд, который составляет N рублей. При этом директор хочет распределить премиальный фонд таким образом, чтобы итоговая зарплата (сумма оклада и премии) у этих сотрудников оказалась пропорциональна проведённому на работе времени, то есть зарплата Алексея должна оказаться ровно в два раза больше, чем зарплата Виктора и Сергея. Более формально, если премия Алексея составит x рублей, премия Виктора — y рублей, премия Сергея — z рублей, то A + x = 2 (B + y) = 2 (C + z), x + y + z ≤ N. При этом бухгалтерия требует, чтобы размер премии (как и размер оклада) выражался целым числом рублей, а директор хочет распределить максимально большую часть премиального фонда, то есть сумма x + y + z должна быть максимально возможной, не превышая при этом N.

Напишите программу, которая определит, какую премию нужно назначить каждому из сотрудников.
Программа получает на вход сначала три целых числа A, B, С, записанные в отдельных строках, — размеры окладов Алексея, Виктора и Сергея (A > 0, B > 0, С > 0). В четвёртой строке входных данных записано одно целое число N — размер премиального фонда (N ≥ 0).
Программа должна вывести три числа — размер премии Алексея, Виктора и Сергея. Если премиальный фонд нельзя распределить так, чтобы выполнялись требуемые условия, программа должна вывести одно число 0.

Ввод	Вывод	Примечание
7 3 4 12	5 3 2	С учетом премии зарплата Алексея составит 12 рублей, Виктора и Сергея — 6 рублей.
20 10 11 2	0	Добиться нужного соотношения премиальных выплат невозможно.

Вывод формулы Задача на реализацию

✓ 55✗ 90800средняяВойти и решать

Лифт в бизнес-центре - 2#34779

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

Бизнес-центр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. На каждом этаже работает ровно один сотрудник. Все сотрудники утром приезжают на парковку, которая расположена в подвальном помещении, на один этаж ниже первого. Бизнес-центр оборудован лифтом, который вмещает неограниченное число людей, но вредный лифтёр сегодня готов отвезти всех сотрудников только на один какой-то этаж.

У каждого сотрудника есть выбор: он может пойти вверх пешком по лестнице, на подъём на один этаж при этом будет уходить A секунд. Либо он может сесть в лифт, который отвезёт всех сотрудников на какой-то выбранный ими вместе этаж. Выйдя из лифта, сотрудник может подняться до своего этажа (также тратя A секунд на подъём на один этаж), либо спуститься до нужного этажа вниз, тратя B секунд на спуск на один этаж. Лифт тратит C секунд на подъём на один этаж.
Определите минимальное время, за которое все сотрудники разойдутся по своим этажам, если они наилучшим образом выберут этаж, на который едет лифт, и свою стратегию поведения (подниматься по лестнице или ехать на лифте, а затем идти по лестнице).

Первая строка входных данных содержит число N – количество этажей в бизнесцентре. Следующие три строки содержат числа A, B, С – время, необходимое сотруднику на подъём на один этаж, на спуск на один этаж и время, необходимое лифту на подъём на один этаж. Все числа – целые положительные, не превосходящие 2×10⁹ , при этом A ≥ B, A ≥ С. Программа должна вывести единственное целое число – минимальное время, за которое все сотрудники могут добраться до своего этажа.

Ввод	Вывод	Примечание
6 20 10 5	45	В здании 6 этажей. Сотрудник поднимается на один этаж за 20 секунд, спускается за 10 секунд. Лифт поднимается на один этаж за 5 секунд. Чтобы быстрее всем добраться до мест, лифт едет на 5-й этаж за 25 секунд. Сотрудник, который работает на 6-м этаже, выходит из лифта и поднимается за 20 секунд, всего его путь занимает 45 секунд. Сотрудник, работающий на 3-м этаже, едет на лифте и спускается на 2 этажа, это также занимает 45 секунд. Сотрудники с 4 и 5-го этажей также едут на лифте, их путь будет быстрее 45 секунд. На 1 и 2-й этажи сотрудники поднимаются пешком по лестнице за 20 и 40 секунд соответственно. Итого все сотрудники добираются до своих этажей не более чем за 45 секунд.

Вывод формулы Задача на реализацию

✓ 32✗ 221900средняяВойти и решать

Тройка#34774

У Олега есть карта «Тройка», на которой осталась одна поездка на наземном транспорте. От дома Олега до школы можно доехать на трамвае, троллейбусе или автобусе. Трамвай ходит через каждые 15 минут, троллейбус — через каждые 10 минут, автобус — через каждые 5 минут, при этом в 8:00 одновременно от остановки отправляются и трамвай, и троллейбус, и автобус (то есть трамвай отправляется в 8:00, 8:15, 8:30, 8:45, 9:00; троллейбус — в 8:00, 8:10, 8:20, 8:30, 8:40, 8:50, 9:00; автобус — в 8:00, 8:05, 8:10, 8:15 и т. д.). Трамвай едет до нужной остановки X минут, троллейбус — Y минут, автобус — Z минут.

Когда Олег пришёл на остановку, на часах было 8 часов M минут. Определите минимальное время, через которое Олег окажется на нужной ему остановке (считая время ожидания транспорта и время поездки на транспорте). Если какой-то транспорт отправляется в тот же момент, когда Олег пришёл на остановку, то Олег успевает на нём уехать.
Программа получает на вход сначала три целых положительных числа X, Y, Z, не превосходящие 100, записанные в отдельных строчках, — время поездки на трамвае, троллейбусе, автобусе соответственно. В четвёртой строке входных данных записано целое число M (0 ≤ M ≤ 59) — момент времени (в минутах), когда Олег пришёл на остановку.
Программа должна вывести одно натуральное число — минимально возможное суммарное время ожидания транспорта и поездки.

Ввод	Вывод	Примечание
25 10 20 12	18	Олег пришёл на остановку в 8:12. Ему нужно подождать 8 минут и сесть на троллейбус, который довезёт его за 10 минут.

Задача на реализацию Целые числа

✓ 109✗ 178800средняяВойти и решать

Полоски радуги#33692

В школе № 2007 на уроке информатики в системе SilverTests Васе попалась следующая задача: «В младшей группе одного объединённого детского сада воспитательница изучала с детишками порядок цветов радуги. Она отыскала семь соответствующих цветных мелков и начала рисовать полоски, не нарушая последовательности цветов. Начала она с красной полоски. Когда доходила до фиолетовой полоски, опять рисовала красную. Воспитательница успела нарисовать N полосок, когда у неё закончились мелки. Напишите программу, которая вычисляет количество полосок каждого цвета». Вася взялся писать программу, но тут обнаружилось, что на клавиатуре отсутствует клавиша с буквой «i». Помогите Васе написать программу с учётом этого обстоятельства.

Входные данные: Вводится одно целое положительное число N > 0.
Выходные данные: Выведите ответ на задачу.

Если в коде программы встречается буква «i» система выдаст сообщение: Использование запрещенных операторов

Примеры

№	Входные данные	Выходные данные
1	3	'red - 1' 'orange - 1' 'yellow - 1' 'green - 0' 'blue - 0' 'sky - 0' 'purple - 0'

Вывод формулы Целые числа

✓ 46✗ 144800средняяВойти и решать

Гирлянды из лампочек#33670

Из цветных лампочек комплектуют новогодние гирлянды. Сначала лампочки связываются в "снежинку" ровно по K штук в каждой, а потом "снежинки" - в гирлянды, причем каждая гирлянда вмещает не более M "снежинок". Последняя гирлянда (только она одна) может быть короче других (включать в себя меньше "снежинок", чем остальные). Всего имеется N лампочек. Сколько всего получится гирлянд, сколько "снежинок" будет в последней гирлянде и сколько лампочек останется неиспользованными (нужно использовать как можно больше лампочек)? Написать программу: вводятся три числа целых N, M, K в одной строке; вывести три числа в одной строке - сначала количество получившихся гирлянд, затем количество "снежинок" в последней гирлянде, а затем количество неиспользованных лампочек

Примеры

№	Входные данные	Выходные данные
1	35 3 4	3 2 3

Вычисление по заданной формуле Линейные алгоритмы

✓ 178✗ 883800средняяВойти и решать

Книги в библиотеке#33668

В библиотеке на стеллажи расставляют книги. Книги ставятся на полки ровно по K штук на каждую, если полка не может быть заполнена полностью, она остается пустой. В каждом стеллаже по М полок. Последний стеллаж может быть заполнен не полностью. Всего имеется N книг. Сколько всего понадобится стеллажей, сколько полок будет заполнено на последнем стеллаже и сколько книг останется не выставлено на стеллажи (выставить нужно как можно больше книг)? Написать программу: вводятся три числа целых N, M, K в одной строке; вывести три числа в одной строке - сначала количество потребовавшихся стеллажей, затем количество заполненных книгами полок на последнем стеллаже, а затем количество не выставленных книг

Примеры

№	Входные данные	Выходные данные
1	50 70 8	1 6 2

Вычисление по заданной формуле Линейные алгоритмы

✓ 104✗ 782800средняяВойти и решать

*Дартс#33627

Вилли играл дружеский матч с Эмми на звание чемпиона мира. Когда им надоедали долгие шахматные баталии, они переключались на дартс. Игра в дартс заключалась в следующем: каждый бросал дротик в круг, который располагался на расстоянии нескольких метров. Круг имел особую разметку, разделенную на несколько областей окружностями радиусом 10 и радиусом 5 (см. рисунок). Попадание дротика в красную область приносило 20 баллов, попадание в зеленую - 15 баллов, попадание в желтую - 30 баллов, а попадание в центр - 50 баллов. Если дротик попадал на границу областей, то это давало количество баллов, равное максимальному баллу из граничащих областей.
Попадание дротика будем условно кодировать точкой с координатой (x ,y). Вилли и Эмми сделали по 2 броска дротиками. Необходимо посчитать, кто из них победил.
Напишите программу, которая будет подсчитывать и выводить победителя этой игры. Вывести имя победителя (W - Вилли, E - Эмми) и через пробел, набранные им баллы. При равенстве вывести W=E и количество баллов.

Входные данные
На вход подаются 4 строки по 2 числа в каждой строке (все числа целые). Первые две строки - координаты точек (x ,y), куда попали дротики Вилли (W), третья и четвертая строка - куда попали дротики Эмми (E).

Выходные данные
Выведите имя победителя (W - Вилли, E - Эмми) и через пробел, набранные им баллы. При равенстве вывести W=E и через пробел количество набранных баллов.

Примеры

№	Входные данные	Выходные данные
1	0 0 -5 7 1 1 5 7	W 65
2	0 0 5 5 0 0 5 5	W=E 70

Линейные алгоритмы Условный оператор

✓ 941✗ 4 665800средняяВойти и решать

Последовательность#33303

Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.

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

Дано натурально число число N (1 ≤ N ≤ 10¹⁸).

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

Выведите число, которое стоит на k-ом месте в последовательности.

Ввод	Вывод
1	0
10	2

Арифметические алгоритмы (Теория чисел)Рекурсия Целые числа

✓ 4✗ 301 000средняяВойти и решать

Проверка на целое число#33148

Дано вещественное число. Проверить является ли оно целым с точность до 6-го знака.

Примеры

№	Входные данные	Выходные данные
1	1.000001	NO
2	1.000000	YES

Вещественные числа Условный оператор

✓ 194✗ 1 417800средняяВойти и решать

Улучшение успеваемости#33121

В лицее на уроках информатики ответы учеников оцениваются целым числом баллов от 2 до 5. Итоговая оценка по информатике выставляется как среднее арифметическое оценок на всех уроках, округленное до ближайшего целого числа. Если среднее значение находится ровно посередине между двумя целыми числами, то оценка округляется вверх.

Примеры округления оценок приведены в таблице.

Оценки на уроках	Среднее арифметическое	Итоговая оценка
2, 3, 5	\({ {2 + 3 + 5} \over 3 }= 3 {1 \over 3}\)	3
3, 3, 4, 4	\({ {3 + 3 + 4 + 4} \over 4 }= 3 {1 \over 2}\)	4
5, 5, 5, 3, 5	\({ {5 + 5 + 5 + 3 + 5} \over 5 }= 4 {3 \over 5}\)	5

Все ученики лицея стремятся получить итоговую оценку по информатике не ниже 4 баллов. К сожалению, один из учеников получил на уроках a двоек, b троек и c четверок.Теперь он планирует получить несколько пятерок, причем хочет, чтобы итоговая оценка была не меньше 4 баллов. Ему надо понять, какое минимальное количество пятерок ему необходимо получить, чтобы добиться своей цели.

Требуется написать программу, которая по заданным целым неотрицательные числам a, b и c определяет минимальное количество пятерок, которое необходимо получить ученику, чтобы его итоговая оценка по информатике была не меньше 4 баллов.

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

Входные данные содержат три строки. Первая строка содержит целое неотрицательное число a, вторая строка содержит целое неотрицательное число b, третья строка содержит целое неотрицательное число c (0 ≤ a, b, c ≤ 10¹⁵, a + b + c ≥ 1).

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

Выходные данные должны содержать одно число: минимальное число пятерок, которое необходимо получить ученику, чтобы итоговая оценка была не меньше 4 баллов.

Ввод	Вывод
2 0 0	2

Бинарный поиск Вывод формулы Целые числа

✓ 27✗ 225900средняяВойти и решать

Вося и Доша#33120

Папа Воси покупал ёлочку 31 декабря, поэтому ему впихали последнюю и очень странную. У этой ёлочки всего 2 ветки, и каждая из них разветвляется ещё на две ветки, и эти ветки ещё на две, и ещё, и ещё... и так N раз.
Вося захотел повесить на бедное дерево свои любимые ёлочные игрушки: разноцветные шарики с красивой надписью "С++". Но Восе удобно вешать свои шарики только на "конечные" веточки (веточки, которые не разветвляются), и ему даже не лень стало из сосчитать. В итоге Вося повесил на ёлочку K шариков и пошёл помогать маме стругать оливье.
Тогда до ёлочки добралась его сестра, начинающий математик Доша. Она захотела украсить ёлочку мишурой, наматывая её на каждую ветку (одна мишура на одну ветку). Считать она, однако, умеет только до 100, поэтому позвонила своему другу, то есть вам, с просьбой сказать, сколько мишуры ей нужно.
Считайте, что вы следили за этой ёлочкой, поэтому знаете и N, и K (0 < N, K <= 10^9). Помогите Доше как можно быстрее, ведь ей пора бежать за тазиком для оливье.

Ввод	Вывод
90 84	173

Вывод формулы Задача на реализацию

✓ 6✗ 0900средняяВойти и решать

кунтер-струк#33118

В игре кунтер-струк: локальное отступление добавили новое НЕЛЕТАЛЬНОЕ оружие с названием ХАХАЙКА. Суть ХАХАЙКИ заключается в том, что она заставляет обрадоваться каждого персонажа на N секунд. Число секунд высчитывается по определённой формуле, которая состоит из модуля произведения округленного вверх корней уравнения ax2+bx+c=0 и умноженного на количество секунд удержания сочетаний клавиш “Alt + f4”=m. От вас требуется найти количество N секунд, если это невозможно, то вывести на экран -1;

Формат входных данных

На вход подаются числа a,b,c,m -10*100^4 ≤ a, b, c ≤ 10*100^4; 1 ≤ m ≤ 10*100^4

Выводится одно целое число, количество N секунд.

Ввод	Вывод
1 -2 1 5	5
1 3 2 4	8

Вывод формулы Вычисление по заданной формуле

✓ 5✗ 81 000средняяВойти и решать

Инопланетный геном#32979

Геном жителей системы Тау Кита содержит 26 видов оснований, для обозначения которых будем использовать буквы латинского алфавита от A до Z, а сам геном записывается

строкой из латинских букв. Важную роль в геноме играют пары соседних оснований, например, в геноме «ABBACAB» можно выделить следующие пары оснований: AB, BB, BA,

AC, CA, AB.

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

Вам даны два генома, определите степень близости первого генома второму геному.

Программа получает на вход две строки, состоящие из заглавных латинских букв. Каждая строка непустая, и её длина не превосходит 10⁵.

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

Ввод	Вывод	Примечание
ABBACAB BCABB	4	Следующие пары оснований первого генома встречаются во втором геноме: AB, BB, CA, AB. Обратите внимание на то, что пара AB в первом геноме встречается два раза, поэтому и подсчитана в ответе два раза.

Алгоритмы обработки Строки Хеш

✓ 108✗ 317800средняяВойти и решать

Лифт#31924

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

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

Первая строка ввода содержит четыре целых числа A, B, C и D, разделенных одним пробелом (1 ≤ A, B, C, D ≤ 20, A≠B, C≠D, A≠C).

Вывести одно целое число – количество единиц времени от момента вызова лифта до момента, когда Петр выйдет из лифта на этаже B.

Ввод	Вывод
3 9 2 5	10
3 9 5 2	13

Примечание:

Пояснение к примеру 1

Лифт за 1 единицу времени доедет до 3-го этажа, остановится на 1 единицу времени, чтобы Петр сел в лифт, затем через 2 единицы времени доедет до 5-го этажа и остановится на 1 единицу времени для высадки предыдущего пассажира, через 4 единицы времени лифт довезет Петра до 9-го этажа, и через 1 единицу времени Петр выйдет из лифта.

Вывод формулы Условный оператор

✓ 117✗ 1 666900средняяВойти и решать

Роза ветров#29448

При выборе места строительства жилого комплекса при металлургическом комбинате необходимо учитывать "розу ветров" (следует расположить жилой комплекс так, чтобы частота ветра со стороны металлургического комбината была бы минимальной). Для этого в течении года проводилась регистрация направления ветра в районе строительства. Данные представлены в виде массива, в котором направление ветра ветра за каждый день (365) кодируется следующим образом:
1 - северный (N),
2 - южный (S)
3 - восточный (E)
4 - западный (W)
5 - северо-западный (NW)
6 - северо - восточный (NE)
7 - юго-западный (SW)
8 - юго-восточный (SE).
Определить, как должен быть расположен жилой комплекс по отношению к комбинату

Входные данные:
В первой строке подается 365 значений от 1 до 8 (направление ветра)

Выходные данные:
Вывести соответствующие буквы (аббревиатуру - смотри список выше), с какой стороны следует построить жилой комплекс

Алгоритмы обработки Одномерные массивы

✓ 96✗ 1 017800средняяВойти и решать

RAID#28422

При хранении данных одна из основных задач – соблюдение баланса между расходами на количество дисков и надёжностью записи. Одним из компромиссных по надёжности и стоимости хранения данных является RAID-3 – избыточный массив независимых дисков с выделенным диском для хранения блоков чётности. Наш RAID-3 состоит из пяти дисков, на четырёх из которых содержится информация, а на пятом – блоки контрольных битов чётности. При записи четырёх байтов (по байту на каждый из четырёх дисков) вычисляется контрольный байт четности, составленный из контрольных битов. Для каждого из восьми разрядов вычисляется сумма значений битов в этих разрядах во всех байтах данных, при этом значение контрольного бита выбирается так, чтобы сумма значений во всех разрядах (включая контрольный) была чётной. Например, у нас есть два основных диска и на них записывается байты 10010010 и 01110111. Тогда значение контрольного байта равно 11100101 – в каждом разряде сумма получается чётной.

Один из четырёх основных дисков в RAID-3 вышел из строя. Известны значения байтов в трёх оставшихся дисках и значение байта на контрольном диске. Какой байт был записан на сломавшемся диске? Все числа приведены в десятичной системе счисления.

– значения на первых трех дисках: 177, 177, 177, контрольный байт: 177;

– значения на первых трех дисках: 79, 79, 79, контрольный байт: 0;

– значения на первых трех дисках: 46, 56, 248, контрольный байт: 90;

– значения на первых трех дисках: 255, 0, 150, контрольный байт 96;

– значения на первых трех дисках: 137, 232, 23, контрольный байт 212.

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

пробелом.

Битовые операции Вывод формулы

✓ 0✗ 11 000средняяВойти и решать

Экзамен#27308

Ведущий разработчик тильда-омега-лямбда-исчисления, сэр Чарльз, в интервью рассказывал, что интерес к этой проблеме у него появился давным-давно.
Когда он был ребёнком, Чарльз очень любил общаться в социальных сетях. Свои эмоции (грусть и веселье) он обычно выражал последовательностью из открывающих и закрывающих скобок, поскольку эмоджи и, тем более, стикеров тогда не было. Но дело, которому он в будущем посвятил всю свою жизнь, сэр Чарльз любил уже тогда, поэтому из его сообщений за день гарантированно можно было составить хотя бы одну правильную скобочную последовательность.
По крайней мере, так он сказал. Однако недавно анонимные хакеры взломали его старую страничку в той самой соцсети и выложили историю сообщений. Увы, приватных фото и других интересностей там не нашлось, но скандал всё равно разразился. Наблюдательные люди заметили, что сообщения за некоторые из дней ну никак не складываются в ПСП.
Чарльз вскоре выпустил видеообращение, в котором объяснил, что по личным причинам ему приходилось удалять некоторые сообщения, но больше одного сообщения в день он не удалял никогда, и длина таких сообщений не превышала 5 символов.
Вам стало интересно, не врёт ли сэр Чарльз на этот раз, и вы решили написать программу, чтобы это проверить.

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

В первой строке подаётся N (\(1 <= N <= 6\)) - количество сообщений Чарльза в подозрительный день. В следующих N строках находятся скобочные последовательности суммарной длины не больше \(10^6\). Обратите внимание, что способ составить из них ПСП может всё-таки существовать - Вы могли его просто не заметить.

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

Выведите "True", если Чарльз не соврал, и есть способ собрать правильную скобочную последовательность, добавив ещё одно сообщение. Выведите "Liar", если это не так.

Примеры

№	Входные данные	Выходные данные
1	2 ((()()) ))))))	True

Разбор случаев Строки

✓ 53✗ 747900средняяВойти и решать

The Lost Cow#27223

Фермер Джон потерял свою корову Беси и хочет её найти.

К счастью через ферму ведёт только одна длинная дорога и и ФД знает, что Беси находится в некоторой точке на этой дороге. Если мы рассмотрим эту дорогу как числовую прямую, ФД сейчас находится в точке x, а Беси сейчас находится в точке y (неизвестной ФД). Если бы ФД знал, где Беси, то бы мог идти прямо к ней, пройдя расстояние |x−y|. К несчастью, сейчас темно, и ФД ничего не видит. Единственный способ, которым он может найти Беси - ходить вперёд и назад, пока не наткнётся на Беси.

Пытаясь найти наилучшую стратегию поиска ФД проштудировал компьютерную литературу и выяснил, что эта проблема ещё не решена и носит название "Проблема потерянной коровы".

Рекомендуемая стратегия такова: двинуться в позицию x+1, затем изменить направление движения на противоположное и перейти в позицию x−2, затем в позицию x+4 и т.д., двигаясь "большим зигзагом", каждый раз двигаясь в два раза дальше от своей первоначальной позиции, чем в прошлый раз. Такой подход гарантирует, что он пройдёт в худшем случае 9 раз прямое расстояние от себя до Беси |x−y|. И это - наименьшее число, гарантируемое в худшем случае.

ФД хочет проверить это утверждение. Вам даны x и y, вычислите общее расстояние пройденное в поиске по описанному выше алгоритму "большой зиг-заг", пройденное до момента находки Беси.

ФОРМАТ ВВОДА :

Единственная строка ввода содержит два различных разделённых одним пробелом целых числа x и y. Оба числа в интервале 0…1,000.

ФОРМАТ ВЫВОДА:

Выведите одну строку, содержащую расстояние пройденное ФД до достижения Беси.

Ввод	Вывод
3 6	9

Вычисление по заданной формуле Задача на реализацию

✓ 27✗ 91900средняяВойти и решать

Bovine Genomics#27218

У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.

За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:

Позиция : 1 2 3 4 5 6 7 8

Пятнистая корова 1: A A T C C C A T

Пятнистая корова 2: A C T T G C A A

Пятнистая корова 3: G G T C G C A A

Корова без пятен 1: A C T C C C A G

Корова без пятен 2: A C T C G C A T

Корова без пятен 3: A C T T C C A T

Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.

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

ФОРМАТ ВВОДА:

Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.

ФОРМАТ ВЫВОДА:

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

Ввод	Вывод
3 8 AATCCCAT ACTTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	4

Множества Строки Хеш

✓ 5✗ 2900средняяВойти и решать