20.06.2019, 05:17 [+3 UTC]
в нашей команде: 3 713 чел. | участники онлайн: 3 (рекорд: 21)

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

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

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

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

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

Форум:
18.06.2019, 08:32

Последний вопрос:
19.06.2019, 16:52
Всего: 149829

Последний ответ:
19.06.2019, 16:44
Всего: 258622

Последняя рассылка:
19.06.2019, 19:45

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

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

Наша кнопка:

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

Отзывы о нас:
17.09.2009, 16:35 »
Рощин Вадим Юрьевич
Спасибо за подробную инструкцию! [вопрос № 172140, ответ № 254217]
01.12.2010, 16:06 »
Botsman
Спасибо! То, что нужно. А главное - оперативно. [вопрос № 181012, ответ № 264466]
21.11.2010, 01:52 »
Мироненко Николай Николаевич
Огромное Вам спасибо за такой хороший ответ smile [вопрос № 180815, ответ № 264206]

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

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

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

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

solowey
Статус: Практикант
Рейтинг: 362
Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 311
Зенченко Константин Николаевич
Статус: Старший модератор
Рейтинг: 238

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

Консультация онлайн # 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.13712 сек.

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