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

Полные квадраты#33145

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0+ 1, 0+ 1+ 3, 0+ 1+ 3+ 5,

. . . , 0 + 1 + 3 + . . . + (2n − 1), . . ., составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, . . . , n², . . ..

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, . . . ,k+ 1+ 3+. . .+ (2n−1), . . .. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности,

либо выясняет, что в ней вообще не встречается полных квадратов.

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

В единственной строке содержится целое число k — начальное число в последовательности

(−10¹² <= k <= 10¹²).

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

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

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной

последовательности. Если в последовательности не встречается квадратов целых чисел, выведите

«none».

Ввод	Вывод
0	0
-5	2
2	none

✓ 0✗ 1—Войти и решать

Вирус#30719

В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из n × m ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через t секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.

Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.

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

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

Двумерные массивы Задача на реализацию Способы задания графа

✓ 1✗ 9—Войти и решать

Телефонные номера#30714

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

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

При отображении телефонного номера на экране телефона, части этого номера принято отделять друг от друга различными символами так, чтобы номер было проще прочитать и запомнить. Так, перед кодом страны обычно ставится символ «+», код региона или оператора берется в скобки, номер абонента разделяется символами «-» на несколько частей. При этом, то, на сколько частей он разбивается, напрямую зависит от количества цифр в нем:
• если номер абонента состоит из трех цифр, то он представляет собой одну часть, состоящую из трех цифр;
• если номер абонента состоит из четырех цифр, то он разбивается на две части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из пяти цифр, то он разбивается на две части, первая из которых состоит из трех цифр, а вторая — из двух;
• если номер абонента состоит из шести цифр, то он разбивается на три части, каждая из которых состоит из двух цифр;
• если номер абонента состоит из семи цифр, то он разбивается на три части, первая из которых состоит из трех цифр, а все остальные — из двух.

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

Формат входных данных
Первая строка файла содержит одно целое число n (1 ≤ n ≤ 100) — количество государств, информация про телефонные коды которых записана в память телефона. Далее следуют n описаний этих государств, разделенных переводами строк. Первая строка описания каждого государства содержит два целых числа c и k (1 ≤ c ≤ 999, 1 ≤ k ≤ 100) — телефонный код этого государства и количество операторов или регионов, существующих в этом государстве. Следующие k строк описания этого государства содержат целые числа, каждое из которых не меньше 100 и не больше 99999 — коды операторов или регионов, зарегистрированных в этом государстве.
Следующая строка входного файла содержит одно целое число m (1 ≤ m ≤ 10 000) — количество телефонных номеров, которые необходимо отформатировать. Следующие m строк содержат сами номера — строки, состоящие ровно из 11 цифр.
Гарантируется, что ни один данный вам номер невозможно разбить на код государства, код оператора или региона и номер абонента более, чем одним способом.

Формат выходных данных
Выведите номера, данные вам во входном файле, отформатированными по правилам, описанным в условии. Каждый номер необходимо вывести в отдельной строке. Номера необходимо выводить в том же порядке, в котором они были перечислены во входном файле. Вместо номеров, корректного разбиения которых на код государства, код оператора или региона и номер абонента не существует, необходимо вывести слово «Incorrect».

Ввод	Вывод
2 7 3 981 3517 812 351 3 34712 1234 963 8 79818266456 35196328463 78122472557 01234567890 73517960326 35134712239 35112342013 78120203040	+7(981)826-64-56 +351(963)284-63 +7(812)247-25-57 Incorrect +7(3517)96-03-26 +351(34712)239 +351(1234)20-13 Incorrect

Задача на реализацию Разбор случаев Строки

✓ 0✗ 2—Войти и решать

Гномы и Одинокая гора#30710

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

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

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

Формат входных данных
В первой строке число n (2 ≤ n ≤ 200 000) — число пещер в Одинокой горе. В следующих n−1 строках заданы переходы между пещерами. В каждой строке записаны номера двух пещер v и u, соединенных переходом (1 ≤ v, u ≤ n). В следующей строке заданы номера пещер v₀ и u₀, в которых исходно находятся два отряда гномов (1 ≤ v₀, u₀ ≤ n, v₀ != u₀).

Формат выходных данных
Выведите максимальное число минут, которое могут продолжаться поиски сокровищ.

Ввод	Вывод	Пояснение
6 1 2 2 3 3 4 4 5 5 6 4 5	2
8 1 2 2 3 3 4 2 5 5 6 3 7 7 8 1 8	4

Деревья Обход в глубину Применение обхода в глубину

✓ 1✗ 1—Войти и решать

Олег и двоичные последовательности#30708

Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s₁, . . . , s_n называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s₁ = s_i , s₂ = s_i+1, . . . , s_k = s_i+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 10⁹ + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 10⁹ + 7.

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

Пояснение
В первом примере подходят последовательности {0, 1, 0 } и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.

Обход в глубину Применение обхода в глубину Разбор случаев

✓ 1✗ 0—Войти и решать

Cow Curling#27300

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке

плоскости.

Подсчёт очков в коровьем кёрлинге ведётся следующим образом:

Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».

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

INPUT FORMAT:

* Строка 1: Целое число N.

* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).

* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).

OUTPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B

SAMPLE:

Ввод	Вывод
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3	1 2

INPUT DETAILS:

У каждой команды по 4 камня.

Команда A имеет камни (0,0), (0,2), (2,0), (2,2).

Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).

OUTPUT DETAILS:

Команда A захватила камень противника в точке (1,1).

Команда B захватила камни противника в точках (0,2) и (2,2).

Вычислительная геометрия Динамическое программирование Структуры данных

	A	B	C	D
1	номер участника	номер школы	класс	баллы
2	участник 1	38	8	55
3	участник 2	32	9	329
4	участник 3	30	8	252
5	участник 4	50	8	202

Запрос	Найдено страниц (в тысячах)
Диана & (Аврора \| Паллада)	800
Диана & Аврора & Паллада	220
Диана & Аврора	550

Алгоритмический язык	Паскаль
алг нач цел s, t, A ввод s ввод t ввод A если s > 10 или t > A то вывод "YES" иначе вывод "NO" все кон	var s, t, A: integer; begin readln(s); readln(t); readln(A); if (s > 10) or (t > A) then writeln('YES') else writeln('NO') end.
Бейсик	Python
DIM s, t, A AS INTEGER INPUT s INPUT t INPUT A IF s > 10 OR t > A THEN PRINT "YES" ELSE PRINT "NO" ENDIF	s = int(input()) t = int(input()) A = int(input()) if (s > 10) or (t > A): print("YES") else: print("NO")
С++
#include <iostream> using namespace std; int main(){ int s, t, A; cin >> s; cin >> t; cin >> A; if (s > 10 \|\| t > A) cout << "YES" << endl; else cout << "NO" << endl; return 0; }