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

Bovine Genomics №2#27221

У Фермера Джона есть N коров с пятнами и N коров без пятен. Как генетик, ФД уверен, что пятна на его коровах вызваны мутацией коровьего генома.

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

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

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

Пятнистая корова 2: G A 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 G T T G C A ... T

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

Посмотрев внимательно на эту таблицу он предположил, что позиции 2 и 4 могут отвечать за пятнистость. Поскольку, глядя на символы в этих позициях, ФД может предсказать, какая из его коров пятнистая, а какая - нет (например, если он видит G и С - значит, корова не пятнистая).

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

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

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

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

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

Ввод	Вывод
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	22

Вывод формулы Перебор

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

COWBASIC#27217

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

COWBASIC - это простой, элегантный язык. У него две основные черты: сложение и циклы. Для решения проблемы переполнения, Беси выполняет все операции сложения по модулю 10⁹+7. MOO-цикл исполняет блок кода фиксированное количество раз. Циклы и сложения могут быть вложенными.

Вам дана COWBASIC-программа, определите результат её выполнения - число, которое она вернёт.

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

Вам дана COWBASIC-программа длиной не более 100 строк, каждая строка длиной не более 350 символов. COWBASIC-программа это список операторов.

Имеется три типа операторов:

<переменная> = <выражение>

<литерал> MOO {

<список операторов>

}

RETURN <переменная>

Имеется три типа выражений:

<литерал>

<перменная>

( <выражение> ) + ( <выражение> )

Литерал - это положительное целое число не более 100,000.

Переменная - это строка не более 10 маленьких латинских букв.

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

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

Выведите одно положительное целое число - значение переменной, возвращённой оператором RETURN.

ОЦЕНИВАНИЕ

в 20% тестов MOO-циклы не вложены.

В других 20% всех тестов программу будет иметь только одну переменную. MOO-циклы могут быть вложенными

В остальных тестах нет никаких ограничений.

Ввод	Вывод	Примечание
x = 1 10 MOO { x = ( x ) + ( x ) } RETURN x	1024	Эта COWBASIC-программа вычисляет 2¹⁰
n = 1 nsq = 1 100000 MOO { 100000 MOO { nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) ) n = ( n ) + ( 1 ) } } RETURN nsq	4761	Эта программа вычисляет (10⁵∗10⁵+1)² (по модулю 10⁹+7).

"Длинная" арифметика Задача на реализацию

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

ПТИЦЫ#27173

Всеволод Юрьевич устроился работать охранником на склад. Работа монотонная, и от скуки Всеволод Юрьевич считает ворон и других птиц, пролетающих мимо будки охраны. За годы работы он обнаружил следующую закономерность. Вороны летают поодиночке, начиная с 8:00 утра с периодичностью P1 минут, а после 8:00 вечера летать перестают. Утки пролетают стайками по N штук, начиная с 10:00 утра, с периодичностью P2 минут и перестают летать после 5:00 вечера. Голуби летают поодиночке с 7:00 утра до 8:00 вечера с периодичностью P3 минут. Три раза в день Всеволоду Юрьевичу приходится отвлечься от своего занятия ровно на полтора часа, чтобы принять на склад товар. Приемка начинается ровно в 11:00, 15:00 и 17:00. Сколько птиц (M) Всеволод Юрьевич насчитает за смену, если смена начинается в 6:00 утра и заканчивается в 6:00 утра на следующий день?

Во всех временных интервалах левый конец входит в него, а правый - нет. Например, одна из приемок начинается в 11:00 и Всеволод Юрьевич не считает птиц пролетающих в моменты с 11:00 до 12:29 включительно, а птиц, пролетающих в 12:30 - считает.

Формат входных данных
В строке указываются 4 целых положительных числа не превышающих 10000 каждое: P1, P2, N, P3, разделенные пробелом.
Формат выходных данных
В единственной строке указывается целое число M – количество птиц, которых Всеволод Юрьевич насчитает за смену при указанных условиях входа.

Ввод	Вывод
P1 P2 N P3	M
23 57 5 7	123

Разбор случаев

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

Площадь невырожденного треугольника#27172

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

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

язык программирования и его версию.

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

В первой строке задаётся N – количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа – координаты очередной точки.

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

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

Ввод	Вывод
3 6 6 -8 8 9 7	48

ЕГЭ - вычислительные задачи

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

Златопольский 12.5#27171

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M(1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.
Далее идет число k (1<=k<=N)

Формат выходных данных
Вывести на экран k-ю строку (считая, что нумерация элементов массива начинается с 1, т.е. для первой строки k=1).
Все элементы выводить в одну строку через 1 пробел между элементами

Двумерные массивы

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

Златопольский 12.3#27170

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.
Далее, через пробел, идут два числа k и h (1<=k<=N, 1<=h<=M)

Формат выходных данных
Вывести на экран элемент, расположенный на позиции h в строке k (считая, что нумерация элементов массива начинается с 1, т.е. для левого верхнего элемента массива считается, что k=1 и h=1).

Двумерные массивы

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

Златопольский 12.2б#27169

Двумерные массивы

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

Златопольский 12.2а#27168

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (1<=N<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.

Формат выходных данных
Вывести на экран элемент, расположенный в правом нижнем углу.

Двумерные массивы

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

Златопольский 12.1б#27167

Двумерные массивы

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

Златопольский 12.1а#27166

Формат входных данных
В первой строке вводятся через пробел количество строк N (1<=N<=20) и количество столбцов M (M 1<=M<=20) двумерного массива.
Далее идет N строк по M элементов в строке - элементы двумерного массива. Все элементы двумерного массива по модулю не превышают 50.

Формат выходных данных
Вывести на экран элемент, расположенный в правом верхнем углу.

Двумерные массивы

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

Вычислитель#27121

Дана блок-схема алгоритма. Какое целое положительное число w необходимо подать на вход, чтобы после завершения алгоритма получилось значение s ? В ответе укажите целое число. Примечание. Операция mod вычисляет остаток от деления первого аргумента на второй. Операция div вычисляет частное от целочисленного деления первого аргумента на второй.

Задача на реализацию Задачи на моделирование

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

Intelligence in Perpendicularia#27118

There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.
The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter.

Write a program that calculates the total secured perimeter for the given plan of the secret service facility.

Input
The plan of the secret service facility is specified as a polygon. The first line of the input contains one integer n — the number of vertices of the polygon (4 ≤ n ≤ 1000). Each of the following n lines contains two integers xi and yi – the coordinates of the i-th vertex (−10⁶ ≤ x_i , y_i ≤ 10⁶ ). Vertices are listed in the consecutive order. All polygon vertices are distinct and none of them lie at the polygon’s edge. All polygon edges are either vertical (x_i = x_i+1) or horizontal (y_i = y_i+1) and none of them intersect each other.

Output
Output a single integer — the total secured perimeter of the secret service facility.

Input	Output
10 1 1 6 1 6 4 3 4 3 3 5 3 5 2 2 2 2 3 1 3	6

Вывод формулы

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

Consonant Fencity#27117

There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and o are used to express vowel sounds, while letters b and p are the consonants (e.g. bad, pot).

Some letters can be used to express both vowel and consonant sounds: for example, y may be used as a vowel (e.g. silly) or as a consonant (e.g. yellow). The letter w, usually used as a consonant (e.g. wet) could produce a vowel after another vowel (e.g. growth) in English, and in some languages (e.g. Welsh) it could be even the only vowel in a word.
In this task, we consider y and w as vowels, so there are seven vowels in English alphabet: a, e, i, o, u, w and y, all other letters are consonants.

Let’s define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is 2, the consonant fencity of a string dEsTrUcTiOn is 3 and the consonant fencity of string StRenGtH is 5.

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

Input
The only line of the input contains non-empty original string consisting of no more than 10⁶ lowercase English letters.

Output
Output the only line: the input string changed to have maximum consonant fencity.

Input	Output
consonants	CoNsoNaNts
destruction	dEsTrUcTiOn
strength	StRenGtH

Конструктив Строки

1 300средняяВойти и решать

КОЛОНИЗАЦИЯ МАРСА#27072

Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки. Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.

Формат входных данных
Задается одно число N ( 1<= N <= 10⁹ ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.

Ввод	Вывод
2	3

Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

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

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

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

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

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

Тяжелая, вариант-2#27065

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

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

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

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

Задача на реализацию Задачи на моделирование

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

Легкая, вариант-2#27063

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

Формат входного файла

На вход программе подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

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

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

Ввод	Вывод
12:55:00	13:00:00
00:00:00	00:00:00
18:30:03	19:00:00

Дата и время Задачи на моделирование

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

Легкая, вариант-1#27062

Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же было последнее резервное копирование на момент его заступления на смену.

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

Формат входного файла

На вход программы подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

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

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

Ввод	Вывод
12:55:00	12:30:00
00:00:00	23:30:00
18:30:03	18:30:00

Дата и время Задачи на моделирование

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

Числовая последовательность - 5#27050

Вычислить

\(P = (1 + \sin 0.1 ) \cdot (1 + \sin 0.2 ) \cdot ...\cdot (1 + \sin 1 )\)

Входные данные
Нет.

Выходные данные
Вывести число P.

Циклы

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

Числовая последовательность - 4#27049

Дано вещественное число х. Вычислить

\(s = {{(x-1)\cdot(x-3)\cdot(x-7)\cdot...\cdot(x-63)}\over{(x-2)\cdot(x-4)\cdot(x-8)\cdot...\cdot(x-64)}}\)

Входные данные
Вводится вещественное число х (-50 <= х <= 50). Гарантируется, что для заданного х решение существует.

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

Циклы

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