Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 195695
22.05.2019, 14:19
0.00 руб.
22.05.2019, 21:04
0 3 0
Компьютеры Программирование
Добрый день, уважаемые эксперты!
Нашел тут на страничке яндекса задачку:

Уникальные запросы
[table]
[row][col] [/col][col]С++[/col][/row]
[row][col]Ограничение времени[/col][col]2 секунды[/col][/row]
[row][col]Ограничение памяти[/col][col]500Kb[/col][/row]
[row][col]Ввод[/col][col]стандартный ввод[/col][/row]
[row][col]Вывод[/col][col]стандартный ввод[/col][/row]
[/table]


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

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

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

Пример
[table]
[row][col]Ввод[/col][col]Вывод[/col][/row]
[row][col]8
вк
рефераты
вк
ок
одноклассники
яндекс
вконтакте
ок[/col][col]6[/col][/row]
[/table]

Примечания
Этот пример лишь иллюстрирует формат входных данных. Он намеренно нарушает обещание, что ответ не меньше, чем 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;
}

Обсуждение

давно
solowey
Советник
400484
472
22.05.2019, 16:59
общий
22.05.2019, 17:09
Немного поехала разметка в вопросе... Следует читать так:

Уникальные запросы
[table]
[row][col] [/col][col]С++[/col][/row]
[row][col]Ограничение времени[/col][col]2 секунды[/col][/row]
[row][col]Ограничение памяти[/col][col]500Kb[/col][/row]
[row][col]Ввод[/col][col]стандартный ввод[/col][/row]
[row][col]Вывод[/col][col]стандартный ввод[/col][/row]
[/table]

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

Пример
[table]
[row][col]Ввод[/col][col]Вывод[/col][/row]
[row][col]8
вк
рефераты
вк
ок
одноклассники
яндекс
вконтакте
ок[/col][col]6[/col][/row]
[/table]

P.S. Прокачал скил по оформлению таблиц
давно
solowey
Советник
400484
472
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 с большим числом данных проваливает по памяти.
[table]
[row][col]Время посылки[/col][col]Компилятор[/col][col]Вердикт[/col][col]Время[/col][col]Память[/col][col]Тест[/col][/row]
[row][col]24 май 2019, 10:39:11[/col][col]GNU c++ 11 4.9[/col][col]ML[/col][col]2ms[/col][col]380.00Kb[/col][col]1[/col][/row]
[row][col]24 май 2019, 10:39:11[/col][col]GNU c++ 11 4.9[/col][col]ML[/col][col]93ms[/col][col]1.29Mb[/col][col]2[/col][/row]
[/table]
давно
solowey
Советник
400484
472
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

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