Есеп А. Қуанышты сандар (100 балл)

жүктеу/скачать 65,05 Kb.

бет	3/3
Дата	31.12.2021
өлшемі	65,05 Kb.
	#22942

1 2 3

Шығару файлының форматы

Бiр санды — жақсы iшкi кестелердiң санын шығарыңыз.

Бағалау жyйесi

Есеп 6 бөлiмнен тұрады:

Есептiң шартында берiлген тесттер. 0 ұпайrа баrаланады.
N, M ≤ 2. 15 ұпайға бағаланады.
N, M ≤ 100. 17 ұпайrа бағаланады.
N, M ≤ 500. 24 ұпайrа бағаланады.
N, M ≤ 1500 және кестенiң элементтерi бiрге тең. 15 ұпайға бағаланады.
Есептiң бастапқы шектеулерi. 29 ұпайға бағаланады.

Мысалдар

standard input						standard output
3	3	12			12
1	2	3
5	2	5
3	2	4
6	6	30			71
4	4	4 1	1	1
2	5	5 3	2	3
3	2	2 4	1	3
1	1	4 4	4	5
1	3	3 4	5	5
2	5	5 4	3	4

Есеп С. AB (100 балл)

Енгiзу файлының аты: standard input Шыrару файлының аты: standard output Уақыт шектеу: 1 second

Жадыға шектеу: 256 megabytes

Сiзге ’a’ және ’b’ әрiптерiнен тұратын s және t екi сөзi берiлген. s сөзiнде көршi бiрдей әрiптер жоқ. Сiз s-ке тең t-ныц ең күп қиылыспайтын iшкi тiзбектерiн таңдағыңыз келедi. Iшкi тiзбек -

- - бұл сөзден бiрнеше (мүмкiн нөл) элементтерiн алып тастау арқылы алуға болатын сөз тiзбегi. Тацдауrа болатын ец к&п iшкi тiзбектердiц санын табыцыз.

Енгiзу файлының форматы

≤ | | ≤
Бiрiншi жолда s сөзi берiлген (1 s 4). s cөзiнде көршi бiрдей әрiптер жоқ екенiне кепiлдiк берiледi.

Екiншi жолда t сөзi берiлген (1 ≤ |t| ≤ 10⁵).

Шығару файлының форматы

Бiр бүтiн санды — сiз таңдай алатын iшкi тiзбектердiң ең көп санын шығарыңыз.

Бағалау жұйесi

Есеп 7 бөлiмнен тұрады:

Есептiң шартында берiлген тесттер. 0 ұпайға бағаланады.
|s| = 1. 11 ұпайға бағаланады.
|s| = 2. 14 ұпайға бағаланады.
|s| = 3. 20 ұпайға бағаланады.
|s| = 4, |t| ≤ 50. 18 ұпайға бағаланады..
|s| = 4, |t| ≤ 300. 12 ұпайға бағаланады.
|s| = 4, |t| ≤ 10⁵. 25 ұпайға бағаланады.
Мысалдар

standard input	standard output
ab abbaba	2
aba ababaa	2

Тyсiнiктеме

Екiншi мысалда 1, 2, 5 және 3, 4, 6 индекстерiмен қиылыспайтын екi тiзбектi таңдауға болады.

9 сынып 2021, 2 сағат

Мысал

standard input	standard		output
2	2	423
1 123 345
300 301 301

1-й этап Республиканской олимпиады по информатике

Длительность 2 часа

Задача А. Радостные числа

Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт

Натуральное число считается радостным, если оно оканчивается на 25 и является полным квад- ратом. Число считается полным квадратом, если является квадратом какого-то целого числа. На- пример, 25,225,625 радостные, а 125,49, 325 - нет.

Вам дано число k. Найдите k-е радостное число.

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

В единственной строке задано одно целое число k (1 ≤ k ≤ 10⁸).

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

Выведите одно целое число — k-е радостное число.

Система оценки

Это задача состоит из 4 подзадач и 10 тестов, каждый тест оценивается в 10 баллов:

1. 1 ≤ k ≤ 10. Тесты 1 – 4

2. 1 ≤ k ≤ 100. Тесты 5 – 6 3. 1 ≤ k ≤ 5000. Тесты 7 – 8 4. 1 ≤ k ≤ 10⁸. Тесты 9 – 10

Пример

стандартный ввод	стандартный вывод
2	225

1-й этап Республиканской олимпиады по информатике

Длительность 2 часа
Задача В. Матрицы

×
Вам дана матрица размера N M , состоящая из целых положительных чисел, а также целое число K. Назовем подматрицу хорошей, если она является квадратом и сумма этой подматрицы не больше K. Посчитайте количество хороших подматриц.

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

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

В первой строке заданы 3 целых числа N , M , K — размеры матрицы. (1 ≤ N, M ≤ 1500, 0 ≤ K ≤ 10⁹)

В следующих N строках содержится по M целых положительных чисел — содержимое матрицы

(числа по значению от 1 до 1000).

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

Выведите одно число — количество подходящих подматриц.

Система оценки

Данная задача содержит 6 подзадач, в которых выполняются следующие ограничения:

Тесты из условия. Оценивается в 0 баллов.
N, M ≤ 2. Оценивается в 15 баллов.
N, M ≤ 100. Оценивается в 17 баллов.
N, M ≤ 500. Оценивается в 24 балла.
N, M ≤ 1500 и матрица состоит только из единичек. Оценивается в 15 баллов.
Исходные ограничения. Оценивается в 29 баллов.

Примеры

стандартный ввод						стандартный вывод
3	3	12			12
1	2	3
5	2	5
3	2	4
6	6	30			71
4	4	4 1	1	1
2	5	5 3	2	3
3	2	2 4	1	3
1	1	4 4	4	5
1	3	3 4	5	5
2	5	5 4	3	4

1-й этап Республиканской олимпиады по информатике

Длительность 2 часа
Задача С. AB

Вам даны две строки s и t, которые состоят из букв ’a’ и ’b’. В строке s нет соседних одина- ковых букв. Вы хотите выбрать наибольшее количество непересекающихся подпоследователь- ностей t, которые равны s. Подпоследовательность — это такая последовательность строки, которая может быть получена удалением нескольких (возможно ноль) элементов из этой строки. Найдите максимальное количество подпоследовательностей, которое вы сможете выбрать.

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

| |
Первая строка входных данных содержит одну строку s (1 ≤ s ≤ 4). Гарантируется, что в строке s нет соседних одинаковых букв.

Вторая строка входных данных содержит одну строку t (1 ≤ |t| ≤ 10⁵).

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

Выведите одно целое число — максимальное количество подпоследовательностей, которое вы сможете выбрать.

Система оценки

Данная задача содержит 7 подзадач, в которых выполняются следующие ограничения:

Тесты из условия. Оценивается в 0 баллов.
|s| = 1. Оценивается в 11 баллов.
|s| = 2. Оценивается в 14 баллов.
|s| = 3. Оценивается в 20 баллов.
|s| = 4, |t| ≤ 50. Оценивается в 18 баллов.
|s| = 4, |t| ≤ 300. Оценивается в 12 баллов.
|s| = 4, |t| ≤ 10⁵. Оценивается в 25 баллов.

Примеры

стандартный ввод	стандартный вывод
ab abbaba	2
aba ababaa	2

Замечание

Во втором примере можно выбрать две непересекающихся последовательности c индексами 1, 2, 5 и 3, 4, 6.

жүктеу/скачать 65,05 Kb.

Достарыңызбен бөлісу:

1 2 3