20.10.2019, 10:26 [+3 UTC]
в нашей команде: 3 888 чел. | участники онлайн: 5 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.77 (31.05.2019)
JS-v.1.34 | CSS-v.3.35

Общие новости:
28.04.2019, 09:13

Форум:
11.10.2019, 14:47

Последний вопрос:
20.10.2019, 09:44
Всего: 150646

Последний ответ:
20.10.2019, 09:33
Всего: 259248

Последняя рассылка:
20.10.2019, 08:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

zdwork
Статус: 6-й класс
Рейтинг: 868
Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 443
solowey
Статус: Бакалавр
Рейтинг: 308

Перейти к консультации №:
 

Консультация онлайн # 195695
Раздел: • С / С++
Автор вопроса: solowey (Бакалавр)
Отправлена: 22.05.2019, 14:19
Поступило ответов: 0

Добрый день, уважаемые эксперты!
Нашел тут на страничке яндекса задачку:

Уникальные запросы

С++
Ограничение времени2 секунды
Ограничение памяти500Kb
Вводстандартный ввод
Выводстандартный ввод



Пользователи задают в Яндекс.Поиске десятки тысяч запросов в секунду. Часть запросов задают сотни раз в час, другая часть запросов повторяется несколько раз в день, третью часть запросов пользователи спрашивают у Яндекса впервые.
Необходимо оценить количество уникальных запросов, при условии наличия 500 KB оперативной памяти. Гарантируется, что правильный ответ не превосходит 100000 и не меньше, чем 50000.
Решение засчитывается, если ответ отличается от правильного не более, чем на 5%.

Формат ввода
В первой строке указано число n<=500000 — количество запросов, среди которых нужно найти число уникальных. В каждой из n последующих строк содержится по одному запросу. Длина каждого запроса не превосходит 1000 символов.

Формат вывода
Необходимо вывести одно число — оценку количества уникальных запросов. Оценка не обязана быть целой.

Пример
ВводВывод
8
вк
рефераты
вк
ок
одноклассники
яндекс
вконтакте
ок
6


Примечания
Этот пример лишь иллюстрирует формат входных данных. Он намеренно нарушает обещание, что ответ не меньше, чем 50000.

Задачу решил, но не могу уложится в 500Kb. Прокомментируйте и расскажите как улучшить.

#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string, bool> GetSet()
{
	map<string, bool> requests;

	int num = 0;
	cin >> num;

	while (num-- > 0)
	{
		string temp;
		cin >> temp;

    	if (requests.at(requests) == 0)
        {
        	requests[requests] = false;
        }
    	else
        {
        	requests[requests] = true;
        }
	}

	return requests;
}

int main()
{
	map<string, bool> requests = GetSet();
	cout << requests.size();

	return 0;
}

Последнее редактирование 22.05.2019, 21:04 Сергей Фрост (Управляющий)

Состояние: Консультация закрыта

Oтветов пока не поступило.

Мини-форум консультации № 195695

solowey
Бакалавр

ID: 400484

# 1

= общий = | 22.05.2019, 16:59 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Немного поехала разметка в вопросе... Следует читать так:

Уникальные запросы

С++
Ограничение времени2 секунды
Ограничение памяти500Kb
Вводстандартный ввод
Выводстандартный ввод


Формат ввода
В первой строке указано число n<=500000...

Пример
ВводВывод
8
вк
рефераты
вк
ок
одноклассники
яндекс
вконтакте
ок
6


P.S. Прокачал скил по оформлению таблиц smile

-----
Последнее редактирование 22.05.2019, 17:09 solowey (Бакалавр)

solowey
Бакалавр

ID: 400484

# 2

= общий = | 24.05.2019, 10:48 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Сделал такой вариант:

#include <bits/stdc++.h>
 
int main()
{
    std::set<std::size_t> Mass;
    std::string slovo;
    std::hash<std::string> hash_fn;
 
    int n;
    std::cin >> n; //количество запросов
    for (int i = 0; i < n; i++)
    {
        std::cin >> slovo; //сам запрос
        Mass.insert(hash_fn(slovo));
    }
 
    std::cout << Mass.size() << std::endl;
}

1 тест проходит, а 2 с большим числом данных проваливает по памяти.
Время посылкиКомпиляторВердиктВремяПамятьТест
24 май 2019, 10:39:11GNU c++ 11 4.9ML2ms380.00Kb1
24 май 2019, 10:39:11GNU c++ 11 4.9ML93ms1.29Mb2

solowey
Бакалавр

ID: 400484

# 3

= общий = | 24.05.2019, 11:23 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

Дошел до этого:

#include <iostream>
#include <set>
#include <string>
#include <cstring>

using namespace std;

unsigned short Crc16(char *buf, short len)
{
   short crc = 0xFFFF;//переменная 16 бит = 2 байта
   char i; //переменная 8 бит = 1 байт
   while (len--)// проверка условия продолжения
   {
      crc ^= *buf++ << 8;
      for (i = 0; i < 8; i++)//цикл перебора полинома
         crc = crc & 0x8000 ? (crc << 1) ^ 0x1021 : crc << 1;
   }
   return crc;//конец функции расчёта Crc16
}
 
int main()
{
    set<short> Mass;
    char slovo[1000];
 
    int n;
    std::cin >> n; //количество запросов
    for (int i = 0; i < n; i++)
    {
        std::cin >> slovo; //сам запрос
        Mass.insert(Crc16(slovo, strlen(slovo)));
    }
 
    std::cout << Mass.size() << std::endl;
}

Результат на 2 тесте: 95ms и 688.00Kb

Куда дальше можно капнуть? Мысли закончились...

 

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.20944 сек.

© 2001-2019, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.77 от 31.05.2019
Версия JS: 1.34 | Версия CSS: 3.35