Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Скины Как можно создавать скини на свои проги в Borland C++ Builder 6, как на Скриншоти Скриншот https://www.cyberforum.ru/ cpp/ thread83690.html C++ Квадратная страна
http://acm.timus.ru/problem.aspx?space=1&num=1073&locale=ru В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума...
C++ Препроцессорные директивы в C/C++ (#include, #define и прочее) https://www.cyberforum.ru/ cpp/ thread83659.html
Статья переехала сюда
C++ Игра Пуговицы. http://acm.timus.ru/problem.aspx?space=1&num=1023&locale=ru Правила игры очень просты. Перед двумя играющими находится кучка из K пуговиц. Играющие по очереди берут пуговицы из кучки, причем за... https://www.cyberforum.ru/ cpp/ thread83658.html
C++ Ассемблерная вставка
Товарищи!! кто знает, подскажите как сделать ассемблерную вставку в cи-проекте в среде Turbo C?? я пытался скормить ему asm...,но никак..ошибка( может быть надо тот кусок проги на асм отдельным...
C++ Step 1: Specify the working directory from which doxygen will run У меня есть файлы написанные на С++ (cpp и h). Все эти файлы я разместила на диске D в одной папке. Нужно получить документацию по каждому файлу. А у меня в результате получается пустой документ. ... https://www.cyberforum.ru/ cpp/ thread83586.html
C++ Подскажите https://www.cyberforum.ru/ cpp/ thread83203.html
Как с помощью 0 канала системного таймера подсчитать время выполнения определенных действий?Может у кого код есть с подобным примером?Спасибо всем ответившим?(среда bc 3.1)
Где используется Tini C Compiler? C++
Здравствуйте! Если знаете, напишите пожалуйста примеры использования TCC (или другого интерпретатора си) как интерпретатора? Если не практические, то хотя-бы теоретически, где можно использовать...
C++ Как искать файлы которые создал пользователь? https://www.cyberforum.ru/ cpp/ thread83081.html
Каким методом можно искать файлы которые создал пользователь?
C++ Ошибка генерации CodeBlocks проекта CMake`ом Пожалуйста, подскажите как правильно сгенерировать CodeBlocks проект с CMake`ом. Опишу по шагам что я делал. 1) В одной папке создал три файла: CMakeLists.txt add_executable(proga main.cpp) ... https://www.cyberforum.ru/ cpp/ thread83068.html
C++ Судоку!
Почти написал программу для генерирования судоку. Компилируется, работает, однако в 50% случаях генерирует только 3-8 строк и зависает. В остальных случаях генерирует полность, но в квадратах числа...
C++ Что за программа Есть видио уроки по C++, и там используется непонятно какая среда программирования. Подскажите если знаете как эта программа называется. И еще сразу вопрос: какая среда программирования самая... https://www.cyberforum.ru/ cpp/ thread82592.html
║XLR8║
1209 / 911 / 270
Регистрация: 25.07.2009
Сообщений: 4,370
Записей в блоге: 5
09.01.2010, 01:31  [ТС] 0

Алгоритм с константной асимптотикой - C++ - Ответ 467429

09.01.2010, 01:31. Показов 1642. Ответов 2
Метки (Все метки)

Ответ

http://acm.timus.ru/problem.aspx?space=1&num=1439

Добавлено через 2 минуты
Несмотря на свои неординарные способности, волшебники любят использовать высшую математику. А именно, они любят находить нужную комнату по ее номеру! Но, конечно же, и тут не обошлось без магии.
В Министерстве Магии на двери комнат наложены чары, которые автоматически нумеруют комнаты: стоит ввести в эксплуатацию новую комнату, как на её двери тут же появляется табличка с номером. Новый номер вычисляется как число, на единицу большее максимального существующего на данный момент номера комнаты. Естественно, ранее существовавшие номера при этом не меняются. Первая созданная комната, разумеется, получила номер 1. Если же комната больше не нужна, то её дематериализуют, и все номера комнат, большие номера уничтожаемой комнаты, уменьшаются на единицу. Благодаря этому нумерация комнат всегда остается сплошной.
Гарри Поттеру удалось узнать номера комнат в министерстве, где могут находиться артефакты, обеспечивающие Сами-Знаете-Кому бессмертие. Казалось бы, теперь найти их и уничтожить не составит труда. Но не тут-то было. Благодаря своей связи с Гарри, Волан-де-Морт сразу же узнал про открытие Гарри. Поэтому он перенесся в министерство и стал уничтожать комнату за комнатой. Теперь Гарри, видя номер на двери, не знает, какой у этой комнаты был номер раньше. Но зато он знает, какие номера были на дверях комнат, которые уничтожал и уничтожает его враг (ведь Гарри тоже чувствует все, к чему причастен Волан-де-Морт). Вы должны помочь Гарри! Конечно, никто не просит вас сражаться с Вы-Догадываетесь-Кем, но ведь вы можете помочь Гарри быстрее определить настоящий номер комнаты, около которой он находится.
Исходные данные
В первой строке входа указаны число N - количество комнат в министерстве N (1 ≤ N ≤ 109) и число M (1 ≤ M ≤ 105). Каждая из последующих M строк имеет следующий формат:
<letter> <number>
где <letter> - одна из букв 'D' (Destroy) или 'L' (Look at), а <number> - номер на двери комнаты, которая оказывается уничтоженной в данный момент, или на которую в данный момент смотрит Гарри. Известно, что в процессе битвы будет уничтожено не более 104 комнат.
Результат
Выход должен содержать для каждой строки
L <number>
входных данных настоящий номер (который был до начала всего этого безобразия) комнаты, на которую смотрит Гарри. Числа должны располагаться по одному в строке.
Пример
исходные данные результат
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
результат
5
4
6
4
7

Добавлено через 49 минут
я думаю что можно использовать сет, елементы в нем упорядочены, добавление происходит за logN, что для даной задачи = 16 - максимум, т.е., примерно, 10.

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

Вернуться к обсуждению:
Алгоритм с константной асимптотикой C++
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.01.2010, 01:31
Готовые ответы и решения:

Eigen - инициализация константной комлексной матрицы
Здравствуйте. Хочу в программе использовать комлексную матрицу, значения которой были бы известны...

Передача по константной ссылке
void print(const std::string strs, const char c); void print(const std::vector&lt;std::string&gt;&amp;...

Константная функция с константной ссылкой
Есть следующая строка const std::vector&lt;Point&gt; extract(const std::vector&lt;Point&gt; &amp;points)...

Возврат константной ссылки из функции
Можно ли из функции возвращать константную ссылку? Есть след. классы: class A { /*чтото тяжёлое,...

2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.01.2010, 01:31

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Инициализация длинной константной строки
Нужно офомить строку в несколько строк с переводом на новую строку. char string =...

Почему меняется значение константной переменной?
Доброго времени суток! Возникла такая проблема. Вовремя выполнения функции меняется значение...

Как из константной функции вызвать неконстантную?
Здравствуйте. Появилась необходимость сделать такой вот трюк. Например: class B { public:...

Передача параметра по константной ссылке - что это?
объясните мне пожалуйста что такое передача параметра в функцию по константной ссылке? я просто...

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.