Мутанты

@Pavlin234 · Регистрация: 12.03.2017

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

Уже долгое время в Институте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Для удобства каждый цвет обозначен своим номером, всего цветов не более 10⁹. В один из прекрасных дней в питомнике случилось чудо: все зверюшки выстроились в ряд в порядке возрастания цветов. Пользуясь случаем, лаборанты решили посчитать, сколько зверюшек разных цветов живет в питомнике, и, по закону жанра, попросили вас написать программу, которая поможет им в решении этой нелегкой задачи.

Формат входных данных
В первой строке входного файла содержится единственное число N (0≤N≤10⁵) — количество зверюшек в Институте. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10⁹ и разделенных пробелами — их цвета. В третьей строке файла записано число M (1≤M≤100000) — количество запросов вашей программе, в следующей строке через пробел записаны M целых неотрицательных чисел (не превышающих 10⁹+1).

Формат выходных данных
Выходной файл должен содержать M строчек. Для каждого запроса выведите число зверюшек заданного цвета в питомнике.

Примеры
входные данные
10
1 1 3 3 5 7 9 18 18 57
5
57 3 9 1 179
выходные данные
1
2
1
2
0

Nishen · 31.10.2017, 11:29

Наработки уже есть какие-то? Что сами сделали?

@mat_for_c · 31.10.2017, 11:40

C++

ifstream inFile("data");
ofstream outFile("result");
map<int, int> animals;
 
int n, m, i, x;
 
inFile >> n;
for(i(0); i < n; ++i) {
   inFile >> color;
   ++animals[color];
}
 
inFile >> m;
for(i(0); i < m; ++i) {
   inFile >> x;
   outFile << animals[x] << "\n";
}

@woldemas · 31.10.2017, 11:45

mat_for_c, это же расточительно с точки зрения памяти, 10^9 цветов может быть.
В отсортированном массиве - можно просчитать за один пробег как в поиске максимума, считая длины подпоследовательностей с одинаковыми элементами.
Лучше - использовать бинарный поиск с двумя разными сравнениями.

@mat_for_c · 31.10.2017, 11:47

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

mat_for_c, это же расточительно с точки зрения памяти, 10^9 цветов может быть.

начнем с того, что элементов всего 10^5

@woldemas · 31.10.2017, 11:50

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

начнем с того, что элементов всего 10^5

Тоже много, если все разноцветные.

@mat_for_c · 31.10.2017, 11:50

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

Лучше - использовать бинарный поиск с двумя разными сравнениями.

вставка в словарь как раз использует бинарный поиск

@woldemas · 31.10.2017, 11:52

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

вставка в словарь как раз использует бинарный поиск

Да, но для каждого элемента массива, то есть сложность вашего алгоритма будет n log(n).
А если бинарным поиском найти начала и конец интервала цвета - сложность 2 log(n)

@mat_for_c · 31.10.2017, 11:55

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

это же расточительно с точки зрения памяти

давай подсчитаем. 10000 элементов в словаре, т.е. 20000*4 байт = 80000 Б = 781,25 КБ = 0,762940 MБ.
если вы уж не найдете 1 мб оперативки, мне жаль вас...

Добавлено через 1 минуту

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

Да, но для каждого элемента массива, то есть сложность вашего алгоритма будет n log(n).
А если бинарным поиском найти начала и конец интервала цвета - сложность 2 log(n)

т.е. вопрос уже не в памяти)

@woldemas · 31.10.2017, 11:57

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

вопрос уже не в памяти)

И в памяти, и во времени выполнения.
Если можно реализовать лучше по обоим критериям, почему бы это не сделать?

@mat_for_c · 31.10.2017, 11:58

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

Если можно реализовать лучше по обоим критериям, почему бы это не сделать?

так предлагайте свое решение

@Pavlin234 · 31.10.2017, 12:22 **[ТС]**

Мне нужна целая работающая программа.

@COKPOWEHEU · 31.10.2017, 13:12

C

FILE *pf = fopen("in.txt", "rt");
  fscanf(pf, "%u%*c", &N);
  
  {
    char buf[100];
    do{
      buf[98]=0;
      fgets(buf, 100, pf);
    }while(buf[98]!=0);
  }
  
  fscanf(pf, "%u", &M);
  color = malloc(sizeof(*color)*M);
  num = calloc(sizeof(*num), M);
  for(i=0; i<M; i++)fscanf(pf, "%u", &color[i]);
  rewind(pf);
  fscanf(pf, "%*u");
  for(i=0; i<N; i++){
    fscanf(pf, "%u", &cur_color);
    for(j=0; j<M; j++)if(cur_color == color[j])num[j]++; //я бы сделал break, но цвета могут повторяться
  }
  fclose(pf);
  pf = fopen("out.txt", "wt");
  for(i=0; i<M; i++)fprintf(pf, "%u\n", num[i]);
  fclose(pf);
  free(color);
  free(num);
  return 0;

@Pavlin234 · 01.11.2017, 12:01 **[ТС]**

Мне нужно на С++. И только. Я язык С не изучал.

Добавлено через 17 часов 32 минуты
Пожалуйста, сделайте программу на С++

@COKPOWEHEU · 01.11.2017, 12:58

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

@Pavlin234 · 01.11.2017, 17:56 **[ТС]**

Мне нужна целая программа

zer0mail · 02.11.2017, 20:50

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

Мне нужна целая программа

А зачем нужна, да еще целая?

Добавлено через 15 секунд

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

Мне нужна целая программа

А зачем нужна, да еще целая?

@COKPOWEHEU · 02.11.2017, 22:36

Чтобы обмануть учителя будто это он ее сделал, очевидно же

@ISergey · 03.11.2017, 03:09

Не по теме:

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

Чтобы обмануть учителя будто это он ее сделал, очевидно же

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

@COKPOWEHEU · 03.11.2017, 06:04

Не по теме:

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

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514
	01.11.2017, 12:01 [ТС]	14
	Мне нужно на С++. И только. Я язык С не изучал. Добавлено через 17 часов 32 минуты Пожалуйста, сделайте программу на С++ 0

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514
	01.11.2017, 17:56 [ТС]	16
	Мне нужна целая программа 0

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514
		1
	Мутанты 31.10.2017, 11:22. Показов 6167. Ответов 26 Метки нет (Все метки) Уже долгое время в Институте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Для удобства каждый цвет обозначен своим номером, всего цветов не более 10⁹. В один из прекрасных дней в питомнике случилось чудо: все зверюшки выстроились в ряд в порядке возрастания цветов. Пользуясь случаем, лаборанты решили посчитать, сколько зверюшек разных цветов живет в питомнике, и, по закону жанра, попросили вас написать программу, которая поможет им в решении этой нелегкой задачи. Формат входных данных В первой строке входного файла содержится единственное число N (0≤N≤10⁵) — количество зверюшек в Институте. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10⁹ и разделенных пробелами — их цвета. В третьей строке файла записано число M (1≤M≤100000) — количество запросов вашей программе, в следующей строке через пробел записаны M целых неотрицательных чисел (не превышающих 10⁹+1). Формат выходных данных Выходной файл должен содержать M строчек. Для каждого запроса выведите число зверюшек заданного цвета в питомнике. Примеры входные данные 10 1 1 3 3 5 7 9 18 18 57 5 57 3 9 1 179 выходные данные 1 2 1 2 0 0

Nishen 1352 / 851 / 365 Регистрация: 26.02.2015 Сообщений: 3,799
	31.10.2017, 11:29	2
	Наработки уже есть какие-то? Что сами сделали? 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	31.10.2017, 11:45	4
	mat_for_c, это же расточительно с точки зрения памяти, 10^9 цветов может быть. В отсортированном массиве - можно просчитать за один пробег как в поиске максимума, считая длины подпоследовательностей с одинаковыми элементами. Лучше - использовать бинарный поиск с двумя разными сравнениями. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.10.2017, 11:47	5
	Сообщение от woldemas mat_for_c, это же расточительно с точки зрения памяти, 10^9 цветов может быть. начнем с того, что элементов всего 10^5 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	31.10.2017, 11:50	6
	Сообщение от mat_for_c начнем с того, что элементов всего 10^5 Тоже много, если все разноцветные. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.10.2017, 11:50	7
	Сообщение от woldemas Лучше - использовать бинарный поиск с двумя разными сравнениями. вставка в словарь как раз использует бинарный поиск 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	31.10.2017, 11:52	8
	Сообщение от mat_for_c вставка в словарь как раз использует бинарный поиск Да, но для каждого элемента массива, то есть сложность вашего алгоритма будет n log(n). А если бинарным поиском найти начала и конец интервала цвета - сложность 2 log(n) 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.10.2017, 11:55	9
	Сообщение от woldemas это же расточительно с точки зрения памяти давай подсчитаем. 10000 элементов в словаре, т.е. 200004 байт = 80000 Б = 781,25 КБ = 0,762940 MБ. если вы уж не найдете 1 мб оперативки, мне жаль вас... Добавлено через 1 минуту* Сообщение от woldemas Да, но для каждого элемента массива, то есть сложность вашего алгоритма будет n log(n). А если бинарным поиском найти начала и конец интервала цвета - сложность 2 log(n) т.е. вопрос уже не в памяти) 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	31.10.2017, 11:57	10
	Сообщение от mat_for_c вопрос уже не в памяти) И в памяти, и во времени выполнения. Если можно реализовать лучше по обоим критериям, почему бы это не сделать? 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	31.10.2017, 11:58	11
	Сообщение от woldemas Если можно реализовать лучше по обоим критериям, почему бы это не сделать? так предлагайте свое решение 0

@Pavlin234 10 / 59 / 21 Регистрация: 12.03.2017 Сообщений: 514
	31.10.2017, 12:22 [ТС]	12
	Мне нужна целая работающая программа. 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,884
	01.11.2017, 12:58	15
	Тебе уже привели два варианта. Если ты не в состоянии их понять, надо не ныть и спамить, а почитать литературу. Основную работу - алгоритм - за тебя уже сделали, осталось дописать пару строк. 1

zer0mail 2664 / 2239 / 240 Регистрация: 03.07.2012 Сообщений: 8,141 Записей в блоге: 1
	02.11.2017, 20:50	17
	Сообщение от Pavlin234 Мне нужна целая программа А зачем нужна, да еще целая? Добавлено через 15 секунд Сообщение от Pavlin234 Мне нужна целая программа А зачем нужна, да еще целая? 0

@COKPOWEHEU 3881 / 2479 / 418 Регистрация: 09.09.2017 Сообщений: 10,884
	02.11.2017, 22:36	18
	Чтобы обмануть учителя будто это он ее сделал, очевидно же 0

@ISergey
	03.11.2017, 03:09 #19
	Не по теме: Сообщение от COKPOWEHEU Чтобы обмануть учителя будто это он ее сделал, очевидно же Когда то очень давно (сам учился), я старался решать как можно больше задач на форуме с одной мыслей - чем больше сделаю, тем больше опыта и меньше конкурентов.)) (но видимо ошибался... всем не помочь)) ) 0

@COKPOWEHEU
	03.11.2017, 06:04 Мутанты #20
	Не по теме: Странная мотивация. Те, кто задают подобные вопросы по форумам, вряд ли пойдут работать по специальности - им это не интересно, либо просто не удержатся на работе. А вот получение опыта для себя - другое дело. Выбираем интересную задачу, решаем, сравниваем с чужими решениями. 0