Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.64/47: Рейтинг темы: голосов - 47, средняя оценка - 4.64
0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
1

Что необходимо сделать

20.02.2016, 00:43. Показов 9374. Ответов 34
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Диего увлекается коллекционированием наклеек. На каждой из них написано число, и каждый коллекционер мечтает собрать наклейки со всеми встречающимися числами.
Диего собрал N наклеек, некоторые из которых, возможно, совпадают. Как-то раз к нему пришли K коллекционеров. i-й из них собрал все наклейки с номерами не меньшими, чем pi. Напишите программу, которая поможет каждому из коллекционеров определить, сколько недостающих ему наклеек есть у Диего. Разумеется, гостей Диего не интересуют повторные экземпляры наклеек.

Формат ввода

В первой строке содержится единственное число N (0 ≤ N ≤ 100 000) — количество наклеек у Диего.
В следующей строке содержатся N целых неотрицательных чисел (не обязательно различных) — номера наклеек Диего. Все номера наклеек не превосходят 109.
В следующей строке содержится число K (0 ≤ K ≤ 100 000) — количество коллекционеров, пришедших к Диего. В следующей строке содержатся K целых чисел pi (0 ≤ pi ≤ 109), где pi — наименьший номер наклейки, не интересующий i-го коллекционера.

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

Для каждого коллекционера в отдельной строке выведите количество различных чисел на наклейках, которые есть у Диего, но нет у этого коллекционера.

Пример 1

Ввод 1
5
2
4 6
Вывод
0
1

Пример 2

Ввод
3
100 1 50
3
300 0 75
Вывод
3
0
2
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
20.02.2016, 00:43
Ответы с готовыми решениями:

Что необходимо сделать, чтобы улучшить навыки программирования на PHP?
Всем привет! У меня такой вопрос. Я хочу заниматься веб-программированием. У меня есть опыт работы верстальщиком, там я использовал...

HTML Forms. Что необходимо сделать для выполнения кода?
Объясните, пожалуйста, что необходимо сделать для выполнения кода? If you’d like to see this work right away, type this code into a...

Что необходимо сделать - когда полностью скопирован текст сайта?
С моего сайта http://kovorking-tsentr-gol.uaprom.net/ полностью скопирован текст, практически на 100%. Я связалась с администрацией...

34
0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
20.02.2016, 01:59  [ТС] 21
Author24 — интернет-сервис помощи студентам
Ну в смсле у меня не видно какие тесты подаются на вход, только номера тестов видны и все

Добавлено через 7 минут
Поможете, ребят?
0
 Аватар для avgoor
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.02.2016, 02:05 22
Дже, Ошибки компиляции?

Добавлено через 2 минуты
Дже, Попробуй так. Здесь без фишек с++11
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
int main()
{
    int n;
    std::cin >> n;
    std::vector<int> v(n);
 
    for (int i = 0; i < n; i++)
        std::cin >> v[i];
 
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
 
    int k;
    std::cin >> k;
    for (int i = 0; i < k; i++) {
        int itmp;
        std::cin >> itmp;
        std::cout << std::distance(std::upper_bound(v.begin(), v.end(), itmp), v.end()) << std::endl;
    }
}
0
 Аватар для _Valera_
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
20.02.2016, 02:07 23
Цитата Сообщение от avgoor Посмотреть сообщение
Если дерево заполняется один раз, а поиск производится многократно - по скорости set проиграет вектору.
а нам и не надо поиск проводить. он отсортирован уже, мы найдем ответ за сложность сета, и не надо каждый элемент проверять.

При этом сортировка в программе - уже плохо.


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


Покажите на фактах, и я поверю.


Так то конечно вектор быстрей, но в том случае, если нам не нужны упорядоченные данные.
0
 Аватар для avgoor
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.02.2016, 02:12 24
_Valera_, По вашему set заполняется волшебным образом? При каждом добавлении элемента в set производится поиск, причем не по бинарному дереву, а по черно-красному, что хуже. Заполнение сета - не лучше, а хуже, чем сортировка вставками. сложность помните?
0
0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
20.02.2016, 02:29  [ТС] 25
avgoor. wrong answer
Входные данные
1
5
2
4 6
Должно выйти 0 1
А выходит 1 0

Добавлено через 1 минуту
Спасибо, Вам всем, что помогаете мне, но видимо мне суждено получить 2. Ведь срок сдачи завтра(
0
 Аватар для avgoor
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.02.2016, 02:31 26
Цитата Сообщение от Дже Посмотреть сообщение
Входные данные
1
5
2
4 6
Должно выйти 0 1
А выходит 1 0
У Диего 1 наклейка с номером 5.
К нему пришли двое.
Одного не интересует 4 и меньше - ответ 1
Другого не интересует все что меньше 6. У Диего только 5 - ответ 0.
Что я не так понял?
0
 Аватар для _Valera_
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
20.02.2016, 02:40 27
Цитата Сообщение от avgoor Посмотреть сообщение
Заполнение сета - не лучше, а хуже, чем сортировка вставками. сложность помните?
я помню. На цифрах покажешь? Хотел найти графики сравнения, но что то гугл на них не богат...
0
 Аватар для avgoor
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.02.2016, 02:42 28
Тьфу, блин, позор на мои седые яйца. Перечитал условие внимательно. Должно быть так:
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
int main()
{
    int n;
    std::cin >> n;
    std::vector<int> v(n);
 
    for (int i = 0; i < n; i++)
        std::cin >> v[i];
 
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
 
    int k;
    std::cin >> k;
    for (int i = 0; i < k; i++) {
        int itmp;
        std::cin >> itmp;
        std::cout << std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), itmp)) << std::endl;
    }
}
1
 Аватар для _Valera_
495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
20.02.2016, 02:42 29
Кстати, в твоем коде необходимость сортировки отпадает.
0
 Аватар для Nosey
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
20.02.2016, 02:48 30
Цитата Сообщение от avgoor Посмотреть сообщение
причем не по бинарному дереву, а по черно-красному, что хуже
Красно-чёрное дерево это и есть бинарное дерево. С достаточно простой балансировкой. Так сказать золотая середина.
0
 Аватар для avgoor
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
20.02.2016, 02:59 31
_Valera_, Nosey, Вот тест:
C++ Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    auto t1 = std::chrono::high_resolution_clock::now();
 
    std::set<int> s;
    for (int i = 0; i < 1000000; i++)
        s.insert(100.0*rand() / RAND_MAX);
 
    auto t2 = std::chrono::high_resolution_clock::now();
 
    std::vector<int> v(1000000);
    for (int i = 0; i < 1000000; i++)
        v[i]=(100.0*rand() / RAND_MAX);
    v.erase(std::unique(v.begin(), v.end()), v.end());
 
    auto t3 = std::chrono::high_resolution_clock::now();
 
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() << " "
        << std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count() << std::endl;
}
Вывод: 4772 381
Еще вопросы есть?

Добавлено через 1 минуту
Вектор с сортировкой более чем в 10 раз быстрее!

Добавлено через 4 минуты
Тьфу, сорт забыл вставить. Всего лишь в 2 раза быстрее.
0
20.02.2016, 03:17 32

Не по теме:

Цитата Сообщение от avgoor Посмотреть сообщение
Еще вопросы есть?
У матроса нет вопросов, только поправка насчёт бинарного дерева и красно-чёрного.

0
20.02.2016, 03:19 33

Не по теме:

Nosey, про вопросы это не вам, а про бинарное дерево - имелось ввиду обычное сбаллансированное бинарное дерево, без дополнительных атрибутов вершин.

0
20.02.2016, 03:24 34

Не по теме:

Цитата Сообщение от avgoor Посмотреть сообщение
а про бинарное дерево - имелось ввиду обычное бинарное дерево, без дополнительных атрибутов вершин.
Т.е. либо совсем несбалансированное, либо изменение дерева будет адским адом в производительности -> красно-чёрное дерево выходит победителем с огромным отрывом :)

0
20.02.2016, 03:33 35

Не по теме:

Nosey, Ну у RB в 50% случаев - адский труд. Просто оно нужно только тогда, когда в перемешку идут вставки и удаления. Там можно получить выигрыш. А вот там, где только вставки - вектор рулит.

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
20.02.2016, 03:33
Помогаю со студенческими работами здесь

Через что лучше сделать плеер, необходимо открытие только avi файлов?
Уже заезженный вопрос через что лучше сделать плеер, необходимо открытие только avi файлов?

Что необходимо сделать, чтобы при массив можно было вводить в виде таблицы
а не как у меня-только в столбик

Что необходимо сделать, чтобы программа, написанная в Embarcadero RAD Studio Berlin 10.1 запустилась на другом
Что необходимо сделать, чтобы программа, написанная в Embarcadero RAD Studio Berlin 10.1 запустилась на другом компьютере

Что необходимо сделать, если нужно перенести источник ЭДС из какой-либо ветви электрической цепи в другую?
Что необходимо сделать, если нужно перенести источник ЭДС из какой-либо ветви электрической цепи в другую ветвь? Привести схему переноса

Необходимо сделать вставку <b></b> по краям выделенного текста в Memo1, к примеру, что бы получился такой результат: <b>01</b>. Кто сможет помочь?
Имеется кнопка и текстовое поле: void __fastcall TForm1::Button7Click(TObject *Sender) { Memo1-&gt;SelText =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Новые блоги и статьи
Простая нейросеть на КуМир: Создание и обучение
EggHead 16.03.2025
Искусственные нейронные сети — удивительная технология, позволяющая компьютерам имитировать работу человеческого мозга. Если вы хотя бы немного интересуетесь современными технологиями, то наверняка. . .
Исполнитель Кузнечик в КуМир: Решение задач
EggHead 16.03.2025
Среди множества исполнителей в системе КуМир особое место занимает Кузнечик — простой, но невероятно полезный виртуальный персонаж, который перемещается по числовой прямой, выполняя ваши команды. На. . .
Исполнитель Водолей в КуМир: Решение задач
EggHead 16.03.2025
Разработка алгоритмического мышления — одна из ключевых задач для начинающих программистов, и система КуМир предлагает отличный способ погрузиться в этот процесс. Среди множества исполнителей в этой. . .
Исполнитель Чертежник в КуМир: Решение задач
EggHead 16.03.2025
Представьте, что вы можете рисовать на бесконечной координатной плоскости, перемещая точку, которая оставляет след. По вашей команде она может поднять перо и двигаться, не оставляя следа, или. . .
Исполнитель Робот в КуМир: Решение задач
EggHead 16.03.2025
КуМир (Комплект Учебных МИРов) — это учебная среда программирования, разработанная специально для обучения базовым концепциям алгоритмизации. Её главная фишка — использование русскоязычного. . .
Исполнитель Черепаха в КуМир: Решение задач
EggHead 16.03.2025
Представьте, что вы впервые учитесь программировать, а перед вами стоит задача заставить маленькую виртуальную черепашку рисовать на экране. Звучит забавно? Эта идея зародилась ещё в 1967 году, когда. . .
Конвейеры данных с Apache Kafka
Javaican 16.03.2025
В мире, где данные стали новой нефтью, Apache Kafka зарекомендовал себя как мощный инструмент для построения надежных и масштабируемых конвейеров данных. Созданный изначально командой LinkedIn в 2011. . .
Deno против Node.js: Будущее JavaScript рантайма
run.dev 16.03.2025
За последнее десятилетие Node. js стал абсолютным лидером среди JavaScript-рантаймов и фактическим стандартом для серверной разработки на JavaScript. Но в 2018 году тот же разработчик, который создал. . .
SwiftUI или UIKit - что выбрать для нового приложения iOS?
mobDevWorks 16.03.2025
Когда Apple представила SwiftUI на WWDC 2019, многим показалось, что дни UIKit сочтены. Новый декларативный фреймворк предлагал радикально иной подход к разработке интерфейсов. Вместо кропотливого. . .
Docker: Руководство для начинающих по созданию первого приложения
Mr. Docker 16.03.2025
Docker — это платформа, которая упаковывает ваше приложение и все его зависимости в стандартизированные блоки, называемые контейнерами. Эти контейнеры изолированы друг от друга и от основной системы,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru
Выделить код Копировать код Сохранить код Нормальный размер Увеличенный размер