Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

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

09.01.2010, 00:17. Просмотров 684. Ответов 2
Метки нет (Все метки)

Нужно за О(1) давать ответ сколько элементов элементов последовательности установлено в 1 (первоначально - все обнулены), до определенного члена последовательности, также за О(1) нужно устанавливать новый член в 1, и иметь возможность за О(1) узнавать сколько элементов до n-ого установлено в 1.

Как это реализовать?

Добавлено через 27 минут
В принцыпе О(logN) - канает..
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2010, 00:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм с константной асимптотикой (C++):

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

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Передача по константной ссылке - C++
void print(const std::string strs, const char c); void print(const std::vector<std::string>& vstrs, const char c); Нужно организовать...

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

Передача параметров по константной ссылке - Arduino
struct Color { // Color(byte red=0, byte green=0, byte blue=0) // :red(red),green(green),blue(blue) // { } byte...

Инициализация длинной константной строки - C++
Нужно офомить строку в несколько строк с переводом на новую строку. char string = "nznznznznznznz r\n\\ znznnznzznznznznzn...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
09.01.2010, 00:21 #2
Давай уж - полностью задача как звучит ?

А то что-то сомнительно мне что можно за O(1) можно узнать сколько элементов до n-того установлено в 1, разъве что при записи это вычислять и записывать в отдельный массив.
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
09.01.2010, 01:31  [ТС] #3
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.

что-бы узнать номер комнаты достаточно знать сколько комнат было удалено до нее, причем здесь сет? если узнать указатель на первый елемент, значение которого больше номера нашей текущей комнаты и отнять указатель на начало сета получим количество елементов, которые были удалены, т.к. мы имеем сет и умеем кодить бинарный поиск, можно реализовать, но бинарный поиск нужно вести по сету, как это реализовать?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2010, 01:31
Привет! Вот еще темы с ответами:

Можно ли сделать DataViewGrid константной? - C#
Можно ли сделать DataViewGrid константной? То есть чтобы строки не добавлялись сами по себе, а просто висела табличка 5х5

Как из константной функции вызвать неконстантную? - C++
Здравствуйте. Появилась необходимость сделать такой вот трюк. Например: class B { public: void f(); }; class A { B b;

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

Изменение константной ссылки в обычную или указатель - C++
Добрый день, вопрос в названии темы. Как из константной ссылки получить обычную или указатель , чтго бы можно было изменять объект?


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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