Информатика

Квадрат разлинован на N × N клеток (1 < N < 25). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из трех команд: вправо, вверх или диагональ. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вверх – в соседнюю верхнюю, по команде диагональ – на одну ячейку правее и выше по диагонали. При попытке выхода за границу квадрата Робот разрушается. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может. Перед каждым запуском Робота в каждой клетке квадрата указана плата за посещение в размере от 1 до 100. Посетив клетку, Робот платит за её посещение; это также относится к начальной и конечной клеткам маршрута Робота.

 

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

 

Исходные данные представляют собой электронную таблицу размером N × N, каждая ячейка которой соответствует клетке квадрата.

 

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

Для указанных входных данных ответом должна быть пара чисел: 22 42

Скачать файл

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1 при нечетных n,

F(n) = 2 * F(n — 1) при n четных, но не кратных 4,

F(n) = 3 * F(n — 3) + 2 при n кратных 4.

Чему равна сумма значений функции для n от 1 до 1000 включительно.

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 3 при n ≤ 2,
F(n) = 3 * F(n — 1) — 2 * F(n — 2) при n кратных 3,
F(n) = F(n — 3) + F(n - 1) при n не кратных 3.
Чему равно значение функции F(34)?

Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 5 при n ≤ 0,
F(n) = 3 * F(n — 2) / 2 при четных положительных n,
F(n) = 3 + F(n — 1) / F(n - 2) при нечетных положительных n.
Чему равно значение функции F(46)?
Примечание. При вычислении значения F(n) используется операция целочисленного деления.

Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 2 при n = 1,
\(F( n) = {2 F(n - 1) \over F(n - 2)} + 1\) при нечетных положительных n,
\(F( n) = {F(n - 1) + 2 \over 3 }\) при четных положительных n.
Чему равно значение функции F(49)?
Примечание. При вычислении значения F(n) используется операция целочисленного деления.

Алгоритмы вычисления значения функций F(n) и G(n), где n – целое число, заданы следующими соотношениями:
F(1) = 1,
F(n) = 2 * F(n – 1) + G(n) при n > 1.
G(1) = 2, G(2) = 2,
G(n) = 3 * G(n – 1) – F(n – 1)
Чему равно значение функции F(15)?

Алгоритмы вычисления значения функций F(n) и G(n), где n – целое число, заданы следующими соотношениями:
\(F(1) = 2\),
\( F( n) = { 2\cdot G(n - 1) + F(n - 1) \over 2 }\)при n > 1.
\(G(1) = 1\)
\(G(n) = {2 \cdot F(n- 1) \over 3 - G(n - 1)}\)при n > 1
Чему равно значение функции G(35)?

Примечание. При вычислении значений F(n) и G(n) используется операция целочисленного деления.

Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10⁵) стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся K (1≤K≤2⋅10⁵) парами позиций (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Каждую минуту i=1…K танца коровы на позициях a_i и b_i меняются местами. Такие же K обменов делаются на минутах K+1…2K, затем опять на минутах 2K+1…3K, и т.д. Другими словами,

на минуте 1 меняются местами коровы на позициях a₁ и b₁.
на минуте 2 меняются местами коровы на позициях a₂ и b₂.
...
На минуте K меняются местами коровы на позициях a_K и b_K swap.
На минуте K+1, меняются местами коровы на позициях a₁ и b₁.
На минуте K+1, меняются местами коровы на позициях a₂ и b₂.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a₁,b₁)…(a_K,b_K) (1≤a_i<b_i≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 4 1 3 1 2 2 3 2 4	4 4 3 4 1	Корова 1 достигнет позиций {1,2,3,4}. Корова 2 достигнет позиций {1,2,3,4}. Корова 3 достигнет позиций {1,2,3}. Корова 4 достигнет позиций {1,2,3,4}. Корова 5 не будет двигаться, и не покинет позицию 5.

Беси недавно получила набор красок, и она хочет разрисовать длинную изгородь с одной стороны её пастбища. Изгородь состоит из N последовательных 1-метровых сегментов (1≤N≤10⁵). У Беси есть краски 26 различных цветов, которые она пометила буквами от 'A' до Z' в порядке возрастания темноты ('A' - самый светлый цвет, 'Z' - самый тёмный). Поэтому она может описывать раскраску изгороди как строку из N символов (где каждый символ один из - от 'A' до Z').
Изначально все сегменты изгороди не раскрашены. Беси может раскрасить любой непрерывный диапазон сегментов одним цветом за одно прикосновение кисти, также она никогда не красит более светлым поверх более темного (она может красить более темным поверх более светлого).

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

.... -> BBB. -> BBLL -> BQQL
Ограниченная во времени, Беси может оставить некоторые последовательные отрезки не покрашенными. Сейчас она рассматривает Q кандидатов отрезков (1≤Q≤10⁵), каждый задаётся двумя целыми числами (a,b) (1≤a≤b≤N), указывающих индексы конечных точек отрезка, которые должны остаться не раскрашенными.

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

Входные данные
Первая строка содержит N и Q.
Следующая строка содержит N, представляющих желаемый цвет каждого сегмента изгороди.

Каждая из следующих Q строк содержит два разделённых пробелом целых числа a и b представляющих диапазон сегментов, которые возможно останутся не раскрашенными.

Выходные данные
Для каждого из Q кандидатов выведите ответ на новой строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 2 ABBAABCB 3 6 1 4	4 3	В этом примере, исключение диапазона соответствует желаемому образцу В этом примере исключение диапазона BAAB требует четыре прикосновения для раскраски, а исключение диапазона ABBA - только три. .... -> AA.. -> ABBB -> ABCB

Юра Баранкин заполнял таблицу истинности функции \(\neg (z \rightarrow x)\wedge(w\rightarrow y)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
	0			1
		0	1	1
	1		0	1

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

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

Файл к заданию

Юра Баранкин заполнял таблицу истинности функции \((z \rightarrow (x \wedge w))\vee \bar w \wedge (x \rightarrow y)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
0		0		0
		1		0
0			0	0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

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

Файл к заданию

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

Файл к заданию

С помощью текстового редактора определите, сколько раз, не считая сносок, в тексте рассказа И. Ильфа и Е. Петрова «КЛООП» встречается слово «Зевака» (регистр букв не важен). Другие формы слова «Зевака» учитывать не следует. В ответе укажите только число.

Файл к заданию

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

Файл к заданию

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

Файл к заданию

С помощью текстового редактора определите, сколько раз, не считая сносок, в тексте рассказа И. Ильфа и Е. Петрова «КЛООП» встречается слово «Товарищ» (регистр букв не важен). Другие формы слова «Товарищ» учитывать не следует. В ответе укажите только число.

Файл к заданию

Юра Баранкин заполнял таблицу истинности функции \(w \rightarrow (x \wedge \bar y \vee (y \equiv z))\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
	1	0	1	0
	1	1	1	0
1			0	0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Юра Баранкин заполнял таблицу истинности функции \((y=z) \vee \bar y \wedge (x \vee w) \vee \neg (w \rightarrow \bar y)\). В тот момент когда его позвал гулять Костя, Юра успел заполнить лишь фрагмент из трёх различных строк таблицы. После прогулки Юра заметил, что не указал, к какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

?	?	?	?	F
	1	0		0
0	1	1	0	0
0			1	0

Помогите Юре восстановить столбцы таблицы. Укажите какому столбцу соответствует каждая из переменных w, x, y, z. 
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.