Задача Мутанты

@TheDoomKarT · Регистрация: 17.02.2017

Author24 — интернет-сервис помощи студентам

Добый день, решите задачу пожалуйста!
На pascal

magirus · 28.11.2017, 10:01

условие перепечатываем в тему руками. Читаем правила форума.

@TheDoomKarT · 28.11.2017, 10:11 **[ТС]**

Уже долгое время в Институте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Для удобства каждый цвет обозначен своим номером, всего цветов не более 109. В один из прекрасных дней в питомнике случилось чудо: все зверюшки выстроились в ряд в порядке возрастания цветов. Пользуясь случаем, лаборанты решили посчитать, сколько зверюшек разных цветов живет в питомнике, и, по закону жанра, попросили вас написать программу, которая поможет им в решении этой нелегкой задачи.
Исходные данные
В первой строке входного файла содержится единственное число N (0 ≤ N ≤ 105) — количество зверюшек в Институте. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 109 и разделенных пробелами — их цвета. В третьей строке файла записано число M (1 ≤ M ≤ 100 000) — количество запросов вашей программе, в следующей строке через пробел записаны M целых неотрицательных чисел (не превышающих 109+1).
Результат
Выходной файл должен содержать M строчек. Для каждого запроса выведите число зверюшек заданного цвета в питомнике.
Исходные данные: Результат:
10 1
1 1 3 3 5 7 9 18 18 57 2
5 1
57 3 9 1 179 2
0
Я не нашел как редактировать свою тему(((

@eaa · 28.11.2017, 11:03

Входные данные не корректные в примере.
И ограничения не понятные, то ли это 105, то ли 10^5.
109 или 10^9.
А по задаче: Дерево Фенвика и вперед.

@JuriiMW · 28.11.2017, 11:38

Сообщение от eaa

109 или 10^9

В паскале нет операции над числами обозначаемой символом «^».
Внизу есть редактор формул, где можно легко набрать, если уж не помните LaTeX, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{9}$ …

Новичок · 28.11.2017, 18:11

Сообщение от TheDoomKarT

В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел

Не надо никакого Фенвика, левый и правый бинарный поиск.

@Fedor11 · 09.08.2020, 13:21

тут просто находим самое левое и самое правое вхождение элемента и вычитаем из индекса правого индекс левого (Это делается бинарным поиск в библиотеке bisect, методами bisect_left и bisect_right, которые находят левое и правое вхождение соответственно)

Вот код:

Python

from bisect import bisect_left, bisect_right
 
 
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))
 
for i in b:
    print(bisect_right(a, i) - bisect_left(a, i))

@Cyborg Drone · 09.08.2020, 17:17

Fedor11, Вы ум один. Но.

С какой целью Вы подняли тему трёхлетней давности?

И ещё. Специально для таких, как Вы, наверху страницы написано: "PascalABC.NET". Как у Вас с логикой? Вы что, всерьёз надеетесь, что кто-то из хомо сапиенс сапиенс полезет на паскалевскую ветку за вашим питоном? Почему не привели решение на PascalABC.NET? Это же наследник C#, и в нём методы работы с последовательностями побогаче, будут, чем в Python. Или... Вы что, кроме Python, ничего не знаете, что ли?

@Fedor11 · 09.08.2020, 22:15

Я привёл пример кода сам ход мысли, а если человеку надо он сам делает на каком ему надо языке. На Пайтон это легко изобразить, так-как код Пайтон поймут все, а c# не все. Вот и всё! Не бомбите)))

@Cyborg Drone · 12.08.2020, 03:48

Fedor11, в основном сюда приходят те, которые только начали изучать паскаль, они и паскаля-то не знают, а питона - и подавно. Решение на языке, отличном от паскаля, для них совершенно бесполезно.

А те люди, которые "сами делают на каком им надо языке" не просят помощи в решении тривиальных задач.

@Fedor11 · 12.08.2020, 09:47

Ну в принципе вы правы...

@TheDoomKarT 0 / 0 / 0 Регистрация: 17.02.2017 Сообщений: 3
		1
	Задача Мутанты 28.11.2017, 09:57. Показов 2954. Ответов 10 Метки задача (Все метки) Добый день, решите задачу пожалуйста! На pascal Миниатюры 0

magirus Почетный модератор 28045 / 15778 / 982 Регистрация: 15.09.2009 Сообщений: 67,752 Записей в блоге: 78
	28.11.2017, 10:01	2
	условие перепечатываем в тему руками. Читаем правила форума. 0

@TheDoomKarT 0 / 0 / 0 Регистрация: 17.02.2017 Сообщений: 3
	28.11.2017, 10:11 [ТС]	3
	Уже долгое время в Институте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Для удобства каждый цвет обозначен своим номером, всего цветов не более 109. В один из прекрасных дней в питомнике случилось чудо: все зверюшки выстроились в ряд в порядке возрастания цветов. Пользуясь случаем, лаборанты решили посчитать, сколько зверюшек разных цветов живет в питомнике, и, по закону жанра, попросили вас написать программу, которая поможет им в решении этой нелегкой задачи. Исходные данные В первой строке входного файла содержится единственное число N (0 ≤ N ≤ 105) — количество зверюшек в Институте. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 109 и разделенных пробелами — их цвета. В третьей строке файла записано число M (1 ≤ M ≤ 100 000) — количество запросов вашей программе, в следующей строке через пробел записаны M целых неотрицательных чисел (не превышающих 109+1). Результат Выходной файл должен содержать M строчек. Для каждого запроса выведите число зверюшек заданного цвета в питомнике. Исходные данные: Результат: 10 1 1 1 3 3 5 7 9 18 18 57 2 5 1 57 3 9 1 179 2 0 Я не нашел как редактировать свою тему((( 0

@eaa Status 418 4577 / 2344 / 602 Регистрация: 26.11.2017 Сообщений: 5,265 Записей в блоге: 3
	28.11.2017, 11:03	4
	Входные данные не корректные в примере. И ограничения не понятные, то ли это 105, то ли 10^5. 109 или 10^9. А по задаче: Дерево Фенвика и вперед. 0

@JuriiMW 5079 / 2651 / 2349 Регистрация: 10.12.2014 Сообщений: 10,028
	28.11.2017, 11:38	5
	Сообщение от eaa 109 или 10^9 В паскале нет операции над числами обозначаемой символом «^». Внизу есть редактор формул, где можно легко набрать, если уж не помните LaTeX, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{9}$ … 0

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	28.11.2017, 18:11	6
	Сообщение от TheDoomKarT В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел Не надо никакого Фенвика, левый и правый бинарный поиск. 1

@Cyborg Drone Модератор 9867 / 5235 / 3306 Регистрация: 17.08.2012 Сообщений: 16,006
	09.08.2020, 17:17	8
	Fedor11, Вы ум один. Но. С какой целью Вы подняли тему трёхлетней давности? И ещё. Специально для таких, как Вы, наверху страницы написано: "PascalABC.NET". Как у Вас с логикой? Вы что, всерьёз надеетесь, что кто-то из хомо сапиенс сапиенс полезет на паскалевскую ветку за вашим питоном? Почему не привели решение на PascalABC.NET? Это же наследник C#, и в нём методы работы с последовательностями побогаче, будут, чем в Python. Или... Вы что, кроме Python, ничего не знаете, что ли? 0

@Fedor11 3 / 3 / 0 Регистрация: 15.06.2020 Сообщений: 44
	09.08.2020, 22:15	9
	Я привёл пример кода сам ход мысли, а если человеку надо он сам делает на каком ему надо языке. На Пайтон это легко изобразить, так-как код Пайтон поймут все, а c# не все. Вот и всё! Не бомбите))) 0

@Cyborg Drone Модератор 9867 / 5235 / 3306 Регистрация: 17.08.2012 Сообщений: 16,006
	12.08.2020, 03:48	10
	Fedor11, в основном сюда приходят те, которые только начали изучать паскаль, они и паскаля-то не знают, а питона - и подавно. Решение на языке, отличном от паскаля, для них совершенно бесполезно. А те люди, которые "сами делают на каком им надо языке" не просят помощи в решении тривиальных задач. 0

@Fedor11 3 / 3 / 0 Регистрация: 15.06.2020 Сообщений: 44
	12.08.2020, 09:47	11
	Ну в принципе вы правы... 0