Олимпиадные задания по информатике

Задачи школьных олимпиад по информатике.

Задачи школьных олимпиад по информатике (БГУ). Часть 1.

Задачи школьных олимпиад по информатике (БГУ). Часть 2.

Задачи школьных олимпиад по информатике (БГУ). Часть 3.

 

2019/2020 учебный год

• I  этап республиканской олимпиады по учебному предмету «Информатика».
• II   этап республиканской олимпиады по учебному предмету «Информатика».
• III   этап республиканской олимпиады по учебному предмету «Информатика».

1 день

2 день

                    2020/2021 учебный год

• I  этап республиканской олимпиады по учебному предмету «Информатика».
• II   этап республиканской олимпиады по учебному предмету «Информатика».
• 
• 
  
  
  
  
  
  
  
  
  
  2022/2023 учебный год
  • I  этап республиканской олимпиады по учебному предмету «Информатика».

  УТВЕРЖДАЮ

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

                                                 М.Б.  Семёнчик

  19 октября 2022 г.

  Задания

  первого тура областной олимпиады по информатике

  2022/2023 учебный год

  1. Монетки (100 баллов). (Время: 1 сек)

  На столе лежат N монеток. Некоторые из них лежат вверх решкой, а некоторые – гербом. Определите минимальное число монеток, которые нужно перевернуть, чтобы все монетки были повернуты вверх одной и той же стороной.

  

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

  В первой строке записано натуральное число N (1 ≤ N ≤ 100) – число монеток. Во второй строке N целых чисел через пробел: 1, если монетка лежит решкой вверх,  и 0, если вверх гербом.

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

  Число - количество монет, которые следует перевернуть

  Пример ввода	Пример вывода
  5 1 0 1 1 0	2

  2. Сумма (100 баллов). (Время: 1 сек)

  Требуется посчитать сумму целых чисел, расположенных между числами 1 и N включительно.

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

  Единственное целое число N, не превышающее по абсолютной величине 10⁴.

  (-10⁴<=N<=10⁴)

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

   Одно целое число — сумма чисел, расположенных между 1 и N включительно.

  Пример ввода	Пример вывода
  5	15

  Примечание к задаче: если время выполнения теста превышает 2с, то за соответствующий тест выставляется не более 5 БАЛЛОВ (50% от его “стоимости”)

  3. Билеты на метро (100 баллов).  Билет на одну поездку в метро стоит 15 рублей, билет на 10 поездок стоит 125 рублей, билет на 60 поездок стоит 440 рублей. Пассажир планирует совершить N поездок.

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

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

  Дано одно число N - количество поездок. 1<=N<=10¹²

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

  Выведите через пробел три целых числа k1,k2,k3, равные соответственно необходимому количеству билетов на 1, на 10, на 60 поездок.

  Пример ввода	Пример вывода
  311	1 1 5
  129	0 1 2
  123	3 0 2

  4. Простое число.  (Время: 2 сек)

  Задано число  N. Найдите ближайшее к N простое число.

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

  Дано одно число N, 1<=N<=10⁹

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

  Программа должна вывести одно число - ближайшее к N простое число. Если чисел два, то вывести наименьшее из них.

  Пример ввода	Пример вывода
  3	3
  6	5
  27	29

  5. Гонки.

  В гонках "Формула 1" участвовало 4 машины. Они проехали 4 круга за одну гонку. Средняя скорость каждой машины на одном круге: a[i,j] км/ч. Нужно узнать номер машины, которая быстрее всех проехала N-ый круг. Если таких машин несколько вывести все их номера.

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

  1 -ый	2 -ой	3 –ий	4 -ый	круги
  a[1,1]	a[1,2]	a[1,3]	a[1,4]	1-ая машина
  a[2,1]	a[2,2]	a[2,3]	a[2,4]	- ...	(a[i,j]<=109)
  a[3,1]	a[3,2]	a[3,3]	a[3,4]		N (1<=N<=4)
  a[4,1]	a[4,2]	a[4,3]	a[4,4]	4-ая машина
  N				круг

  Выходные данные  Номер машины /номера машин

  Пример ввода	Пример вывода
  1 4 7 5 0 3 7 5 2 3 2 1 6 7 8 9 1	4
  1 4 7 5 0 3 8 5 2 3 2 1 6 7 8 9 3	24

   УТВЕРЖДАЮ

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

                                      П.Е. Красько

  23.02.2023 г.

   

   

  Задания

  I этапа районной олимпиады по информатике

  среди учащихся второй ступени общего среднего образования

  в 2022/202З учебном году

   

   

  1. Дележ яблок (100 баллов). (Время: 1 сек)

  n школьников делят k яблок “поровну”, то есть так, чтобы количество яблок, доставшихся любым двум школьникам, отличалось бы не более, чем на 1.

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

  Программа получает на вход числа n и k.

  (1<=N<=10⁹)

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

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

  Пример ввода	Пример вывода
  7 30	5
  7 28	0

   

  2. Шоколадка  (100 баллов). (Время: 1 сек)

  Требуется определить, можно ли от шоколадки размером n × m долек отломить k долек, если разрешается сделать один разлом по прямой между дольками (то есть разломить шоколадку на два прямоугольника).

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

  Вводятся 3 числа: n, m и k; k не равно n × m. Гарантируется, что количество долек в шоколадке не превосходит 30000.

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

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

  Пример ввода	Пример вывода
  3 2 4	YES
  3 2 1	NO

   

  3. Олимпиада (100 баллов). (Время: 1 сек)

  На олимпиаде по математике Пете надо было решить задачу  “Даны три двузначных числа. Склеить их таким образом, чтобы получилось максимально возможное число”. Помоги Пете решить эту задачу.

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

  a, b, с (натуральные  числа, 10<=a, b, с<=99 )

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

  Х -  искомое число

  Пример ввода	Пример вывода
  21 34 78	783421
  30 50 15	503015

   

  4. Контроперация (100 баллов). (Время: 1 сек)

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

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

  Первая строка содержит натуральное число N – количество оценок в журнале. Во второй строке записаны N целых чисел Ai – оценки Василия. Все числа во входных данных не превышают 1000 по абсолютной величине.

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

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

  Пример ввода	Пример вывода
  5 1 3 3 3 4	1 3 3 3 1
  8 5 4 2 2 4 2 2 5	2 4 2 2 4 2 2 2

   

  5. Дипломы (100 баллов). (Время: 4 сек)

  К окончанию школы у Пети накопилось n дипломов за участие в олимпиадах, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится университете и живёт в общежитии со своими одногруппниками. Чтобы украсить свою комнату, он решил повесить на одну из стен свои дипломы за школьные олимпиады. Петя решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов. Входные данные Входной файл содержит три целых числа: w, h, n (1≤w, h, n≤109). Выходные данные число - ответ на поставленную задачу. Пример ввода Пример вывода 2 3 10 9 1 1 1 1

  рис. к примеру

   

                                 2023/2024 учебный год

УТВЕРЖДАЮ

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

                                   М.Б.  Семёнчик

20.10. 2023 г.

 

Задания

первого (школьного) этапа республиканской олимпиады по информатике

2023/2024 учебный год

 

1.  Мышка (100 баллов). (Время: 1 сек. Память: 16 Мб Сложность: 9%)

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

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

Первая строка содержит три натуральных числа через пробел: a, b и r, где a и b - ширина и высота прямоугольного коврика, а R – радиус запасного коврика. Все числа не превосходят значения 10⁹.

(1<=a, b, r<=10⁹)

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

Выведите «YES», если новый коврик можно спрятать под старым, и слово «NO», если этого сделать нельзя.

 

Пример ввода	Пример вывода
4 7 2	YES
4 7 3	NO

 

2. Гадание  (100 баллов). (Время: 1 сек. Память: 16 Мб Сложность: 13%)

Как и многие другие девочки, Маша любит разные гадания. Некоторое время назад Маша узнала новый способ гадать на числах – для какого-нибудь интересующего ее натурального числа n надо посчитать сумму всех чисел, на которые n делится без остатка. Маша не очень любит арифметику, и попросила вас написать программу, которая автоматизирует процесс гадания.

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

В единственной строке записано натуральное число n (n ≤ 1000), которое Маша была вынуждена сообщить.

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

Выведите сумму всех натуральных делителей числа n.

 

Пример ввода	Пример вывода
6	12
10	18

 

3. Мешки золота (100 баллов). (Время: 1 сек. Память: 16 Мб Сложность: 30%)

Главный вождь племени Мамба не умеет считать. В обмен на одну из его земель вождь другого племени предложил ему выбрать один из трех мешков с золотыми монетами. Но вождю племени Мамба хочется получить наибольшее количество золотых монет. Помогите вождю сделать правильный выбор!

 

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

В одной строке записаны три натуральных числа через пробел (n1 n2 n3). Каждое из чисел не превышает 10¹⁰⁰ (0<=n1, .n2 , n3<=10¹⁰⁰). Числа записаны без ведущих нулей (т.е числа 001 быть не может).

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

Нужно вывести одно целое число — максимальное количество монет, которые может взять вождь.

 

 

Пример ввода	Пример вывода
5 7 3	7
987531 234 86364	987531
189285 283 4958439238923098349024	4958439238923098349024

 

4. Сила драконьей стаи (100 баллов). (Время: 1 сек. Память: 16 Мб Сложность: 40%)

Известно, что у дракона может быть несколько голов и его сила определяется числом голов. Но как определить силу драконьей стаи, в которой несколько драконов и у каждого из них определенное число голов? Вероятно, вы считаете, что это значение вычисляется как сумма всех голов? Это далеко не так, иначе было бы слишком просто вычислить силу драконьей стаи. Оказывается, что искомое значение равно произведению значений числа голов каждого из драконов. Например, если в стае 3 дракона, у которых 3, 4 и 5 голов соответственно, то сила равна 3*4*5 = 60. Предположим, что нам известно суммарное количество голов драконьей стаи, как нам вычислить максимально возможное значение силы этого логова драконов? Именно эту задачу Вам и предстоит решить.

 

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

В единственной строке записано натуральное число N (0 < N <= 100) – количество голов драконьей стаи.

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

В единственную строку нужно вывести максимально возможное значение силы, которая может быть у стаи драконов из N голов.

 

Пример ввода	Пример вывода
6	9
8	18
13	108

 

5. Урожай черники (100б).  (Время: 1 сек. Память: 16 Мб Сложность: 17%)

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

Эти кусты обладают разной урожайностью, поэтому ко времени сбора на них выросло различное число ягод – на i-ом кусте выросло a[i] ягод.

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

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

 

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

Первая строка содержит целое число N (3 ≤ N ≤ 1000) – количество кустов черники.

Вторая строка содержит N целых положительных чисел a₁, a₂, ..., a_N – число ягод черники, растущее на соответствующем кусте. Все a_i не превосходят 1000.

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

Число - ответ на задачу

 

Пример ввода	Пример вывода
4 1 2 3 4	9
3 1 2 3	6

 

 

 

ОБЛАСТНАЯ ОЛИМПИАДА ПО информатике

13 апреля 2024 года

 

Задача_1 Великие бомбардиры

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Однажды три великих футболиста Бампе, Риштиану Боналдо и Лэсси поспорили кто из них самый великий бомбардир. Проверить это они решили в финальной части чемпионата мира на который отобрались команды этих великих игроков. В результате Бампе забил а мячей, Риштиану Боналдо в 2 раза больше чем Бампе, а Лэсси на 2 мяча больше чем Риштиану Боналдо. Определите, сколько мячей забил каждый из этих игроков.

Формат ввода:

В единственной строке вводится натуральное число а. (1<=a<=10)

Формат вывода:

В единственной строке через одиночные пробелы выведите количество мячей, которые забили Бампе, Риштиону Боналдо и Лэсси соответственно.

Пример ввода:

2

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

2 4 6

 

Задача_2 Товарищеский турнир

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

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

Формат ввода:

В первой строке вводится натуральное число n – количество команд.

Во второй строке вводится n целых неотрицательных чисел – количество голов, которые забила каждая команда на турнире. Каждое число не превышает 100.

Формат вывода:

В единственной строке выведите число - ответ на задачу.

Пример ввода:

7

12 4 17 2 0 5 14

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

17

 

Задача_3 Групповая стадия

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

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

Формат ввода:

В первой  строке вводится натуральное число n – количество результативных действий (1<=n<=100)

Каждая из следующих n строк содержит по два числа m и c, разделенных одиночными пробелами, где m – это натуральное число (1<=m<=90), которое отвечает за номер минуты, на которую пришлось результативное действие, а с – это номер команды, которая  совершила результативное действие. Если с равно 1, то забила команда Бампе, а если с равно 2, то забила команда Риштиану Боналдо.

Формат вывода:

В единственной строке выведите один символ.

Если победила команда Бампе, то выведите символ B.

Если победила команда Риштиану Боналдо, то выведите символ R.

Если матч закончился вничью, то выведите символ =

Пример ввода:

7

5 1

19 2

38 2

41 1

72 1

87 1

90 1

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

B

Задача_4 Поддержка команды

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

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

Формат ввода:

В первой строке вводится натуральное число n – количество участников флэш-моба (1<=n<=100 000).

Во второй строке вводится последовательность символов ‘N’, ‘S’, ‘W’, ‘E’ – направление очередного участника.

Формат вывода:

В единственной строке выведите ответ на задачу.

Пример ввода:

7

NSNEWNN

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

3

 

Задача_5 Группа смерти

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

В одну из отборочных групп к чемпионату мира попали команды, приблизительно равные по силам. Такие группы обычно называют группами смерти. Определите, сколько очков набрала команда-победитель.

Формат ввода:

В первой  строке вводится натуральное число n – количество команд в группе (1<=n<=10)

Дальше водится таблица n строк по n чисел в строке. Числа разделяются одиночными пробелами. Каждое число – это результат игры между командами с номерами i и j. Если число равно 1, то победила команда i; если число равно 2, то победила команда j; если число равно 3, то в матче была зафиксирована ничья.

На главной диагонали в таблице стоят нули. (Напомним, что в футболе за победу начисляются 3 очка, за ничью – 1 очко, за поражение – 0 очков)

Формат вывода:

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

Пример ввода1:

4

0 1 2 1

2 0 1 2

1 2 0 3

2 1 3 0

Пример вывода1:

6

Пример ввода2:

5

0 1 3 2 1

2 0 2 1 1

3 1 0 1 2

1 2 2 0 3

2 2 1 3 0

Пример вывода2:

7

Задача_6 Расселение журналистов

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

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

Формат ввода:

В первой строке вводится натуральное число n – количество зданий (1<=n<=20).

Во второй строке вводится n чисел – количество жильцов, которое можно разместить в очередном здании (каждое из чисел не превышает 100).

В третьей строке вводится число х – количество журналистов, которые необходимо разместить (1<=x<=2000).

Гарантируется, что всех журналистов можно разместить в построенных зданиях.

Формат вывода:

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

Пример ввода1:

3

11 52 34

75

Пример вывода1:

2

Пример ввода2:

5

100 200 100 150 170

138

Пример вывода2:

1

Пример ввода3:

3

234 123 200

500

Пример вывода3:

3

Задача_7 Финал и удлинители…

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Сегодня финальный матч чемпионата мира. Этот матч будет транслироваться на многие страны. Но случилась большая неприятность. В ложе, где работают комментаторы, вышли из строя все розетки, кроме одной. Каждому комментатору нужно подключить к сети компьютер. Организаторы не растерялись и решили эту проблему с помощью удлинителей. Каждый удлинитель имеет 5 розеток. Определите, какое минимальное количество удлинителей понадобится, чтобы подключить n компьютеров.

Формат ввода:

В единственной строке вводится натуральное число n – количество компьютеров (1<=n<=200)

Формат вывода:

В единственной строке выведите одно число – минимальное количество удлинителей, которые понадобятся, чтобы подключить n компьютеров.

Пример ввода1:

1

Пример вывода1:

0

Пример ввода2:

3

Пример вывода2:

1

Пример ввода3:

10

Пример вывода3:

3

 

Задача_8 Добраться до финала

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Финал чемпионата проходит в городе N-ске. Так как ожидается большой наплыв болельщиков, то организаторы пустили дополнительные поезда в город N-ск с плацкартными вагонами. В плацкартном вагоне 54 места, которые располагаются в 9 купе. Схема вагона имеет следующий вид:

Купе нумеруются слева направо. Таким образом например в первом купе находятся следующие места: 1, 2, 3, 4, 53, 54; а в девятом – 33, 34, 35, 36, 37, 38

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

Формат ввода:

В первой строке вводится число n - количество свободных мест в вагоне (0<=n<=54).

В следующих n строках вводятся n натуральных чисел – номера свободных мест в вагоне (каждое число не превышает 54).

Формат вывода:

В единственной строке выведите одно число – ответ на задачу.

Пример ввода:

14

13

15

11

9

6

47

16

49

50

10

48

29

14

12

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

2

Задача_9 Интернет-тарифы

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

На финальную часть чемпионата мира съехалось большое количество болельщиков. И конечно же каждый болельщик желает подключиться к сети Интернет, чтобы быть в курсе всех событий. На чемпионате мира местные операторы решили подзаработать и продают интернет-трафик только в виде двух пакетов: можно купить пакет трафика на А мегабайт и заплатить В рублей или купить пакет трафика на С мегабайт и заплатить D рублей. Также можно не покупать пакет трафика, а просто платить за каждый мегабайт 1 рубль. Определите, какую минимальную сумму придется заплатить болельщику, если в ходе чемпионата мира он израсходует трафик в размере Х мегабайт.

Формат ввода:

В первой строке вводится число Х.

Во второй строке вводится число А.

В третьей строке вводится число В.

В четвертой строке вводится число С.

В пятой строке вводится число D.

Все числа натуральные и не превосходят 500 000.

Формат вывода:

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

Пример ввода1:

35

10

9

20

17

Пример вывода1:

31

Пример ввода2:

55

30

20

20

16

Пример вывода2:

40

Задача_10 За день до финала

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Завтра финал чемпионата мира и главная звезда чемпионата Лэсси решил сегодня не идти на тренировку, а просто отдохнуть и поиграть в компьютерную игру.

Имеется прямоугольное поле, расчерченное на клетки. Игрок изначально находится в клетке с координатами (х1, у1). За один ход можно переместить игрока в соседнюю по вертикали или горизонтали клетку. Необходимо провести игрока из клетки с координатами (х1, у1) в клетку с координатами (х2, у2) за минимальное количество ходов. В некоторых клетках стоят фишки – на эти клетки наступать нельзя. Выходить за пределы поля нельзя. Гарантируется, что из клетки с координатами (х1, у1) всегда можно попасть в клетку с координатами (х2, у2).

Формат ввода:

В первой строке вводятся два натуральных числа n и m – размеры поля (1<=n, m <=300, n*m>1).

Каждая из следующих n строк содержит m чисел – 0 или 1 разделенных одиночными пробелами. Если число равно 1, то в клетке находится фишка; если число равно 0, то клетка свободна.

В следующей строке вводятся два числа x1, y1 – координаты начальной клетки.

В следующей строке вводятся два числа x2, y2 – координаты конечной клетки.

(1<=x1, x2<=n; 1<=y1, y2<=m)

Формат вывода:

В единственной строке выведите длину минимального пути из клетки с координатами (х1, у1) в клетку с координатами (х2, у2)

Пример ввода1:

5 6

0 1 0 1 0 0

0 1 1 0 1 0

0 1 0 0 0 0

0 0 0 1 0 1

0 1 0 1 0 1

5 1

2 6

Пример вывода1:

8

 

Задача_11 Памятная футболка

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Все мы знаем, что в финале чемпионата мира команда Лэсси победила команду Бампе. Лэсси решил провести лотерею и раздать футболки со своим автографом некоторым болельщикам. Суть лотереи такова: среди болельщиков купивших билеты на финальный матч случайным образом отбирается n человек, а так как у Лэсси три сына, то он решил, что футболку получат те болельщики, номер билета которых содержит ровно три делителя. Для каждого выбранного болельщика, определите получит ли он футболку с автографом Лэсси.

Формат ввода:

Первая строка содержит натуральное число n – количество случайным образом отобранных болельщиков (1<=n<=100).

Следующие n строк содержат по одному натуральному числу ai в строке  - номер билета очередного болельщика. (1<=ai<=10^16).

Формат вывода:

Выведите n строк. В каждой строке выведите сообщение “YES” или “NO” в зависимости от того получит ли болельщик футболку с автографом Лэсси.

Пример ввода:

5

1

4

7

16

2

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

NO

YES

NO

NO

NO

 

Задача_12 Академия Лэсси

Ограничение времени:	1 секунда
Ограничение памяти:	256 Мб
Ввод:	Стандартный ввод
Вывод:	Стандартный вывод

 

Чемпионат мира закончился. Лэсси наконец осуществил свою давнюю мечту – стал чемпионом мира и теперь спокойно может закончить карьеру. Но без футбола Лэсси жить не может, теперь он решил основать собственную академию и объявил просмотр игроков. На просмотр явилось огромное количество игроков. Каждый игрок имеет свой рейтинг. Прежде чем отобрать игроков Лэсси решил проверить их на сыгранность. Лэсси выстроил всех кандидатов в шеренгу. Затем Лэсси задумывает три числа left, right  и reit. Числа left  и right отвечают за границы отрезка на котором Лэсси будет проверять сыгранность отобранной команды, а reit отвечает за начальный рейтинг команды. Лэсси хочет узнать сколько игроков на выбранном отрезке будут иметь рейтинг reit, reit+1, reit+2, reit+3… Полученное количество игроков Лэсси и будет называть сыгранностью команды. Помогите Лэсси справиться с этой нелегкой задачей.

Формат ввода:

Первая строка содержит два натуральных числа n и m – количество игроков явившихся на просмотр и количество запросов Лэсси на сыгранность (1<=n, m <=10^5).

Вторая строка содержит n натуральных чисел – рейтинги игроков (каждое число не превышает 10^9).

Следующие m строк содержат по три натуральных числа в строке  - left, right и reit (1<=left<=right<=n; 1<=reit<=10^9).

Формат вывода:

Выведите m строк. В каждой строке выведите натуральное число – сыгранность отобранной команды.

Пояснение:

Рассмотрим первый запрос из условия:

13 3 2 4 11 8 5 2 7 8 6 10 14 15 18 7 8 13 14 11.

Игроки с 5 по 13 номер имеют рейтинги: 11 8 5 2 7 8 6 10 14.

Лэсси же хочет, чтобы рейтинги на этом отрезке были 3 4 5 6 7 8 9 10 11.

Под данные параметры подпадают игроки с номерами 7, 9, 10, 12.

У них рейтинги соответственно 5, 7, 8, 10.
Количество таких игроков равно 4.

Пример ввода:

20 2

13 3 2 4 11 8 5 2 7 8 6 10 14 15 18 7 8 13 14 11

5 13 3

1 5 2

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

4

1