|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
12.11.2012, 22:50 | #1 |
Регистрация: 12.11.2012
Сообщений: 3
|
Задача с Тимуса
Здравствуйте! Никак не могу решить задачу. Пожалуйста помогите!
Ограничение времени: 1.0 секунды Ограничение памяти: 16 МБ Новый русский Колян любит две вещи: деньги и порядок. У Коляна много денег, но в них нет порядка. Одним прекрасным утром Колян понял, что он больше не может это переносить, и решил навести порядок в своих деньгах. Он приказал своим верным помощникам извлечь деньги из подземного хранилища, и скоро его большая комната была заполнена красными, зелёными и синими банкнотами. Колян смотрел с отвращением на этот ужасный беспорядок. Сейчас он хочет оставить в своём хранилище банкноты только одного достоинства, а остальные деньги раздать бедным. Он точно знает, что более половины банкнот имеют одинаковое достоинство. Но в беспорядке невозможно понять, какая банкнота встречается чаще всего. Исходные данные Первая строка содержит количество банкнот Коляна N (1 ≤ N ≤ 500 000). В следующих N строках даны достоинства K этих банкнот (0 ≤ K ≤ 109). Более половины из этих значений одинаковы. Результат Выведите наиболее часто встречающееся достоинство банкнот. http://acm.timus.ru/problem.aspx?space=1&num=1510 Написал на JAVA и C# работает медленно поэтому не засчитывается. Можно ли как нибудь заставить работать побыстрей мою прогу или может я в корне не так делаю. Код:
Код:
Код:
|
12.11.2012, 23:16 | #2 |
Форумчанин
Регистрация: 26.01.2009
Сообщений: 360
|
На C++ скорее всего из-за того, что не может внести туда исходные данные.
Например я когда был на олимпиаде, то нам заранее говорили как должны называться классы, переменные и т.д., т.к. программа компилировалась уже непосредственно на удаленной машине |
13.11.2012, 10:06 | #3 |
Регистрация: 12.11.2012
Сообщений: 3
|
Нет... если бы так было то другие задачи так же не работали бы, плюс там бы тоже заранее было бы написано что использовать.
|
13.11.2012, 10:22 | #4 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Я бы побаловался с порядком условий. То есть в цикле наверняка какие-то события наступают чаще, чем другие.
Код:
ЗЫ. На месте Коляна я бы завел бухгалтера и оставил его жить в хранилище с деньгами .
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
13.11.2012, 11:00 | #5 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
я бы вообще по другому эту задачу решал!
определил бы массив от 1 до 109 читал каждую строчку с номиналом и увеличивал на 1 соответствующую строчку массива. одновременно с увеличением обеспечивал поиск максимального. и вся задача. на абстрактном языке это выглядит так: Код:
ОТБОЙ!! Алгоритм мой не годится! я сходил по ссылке. достоинства банкнот K от нуля до 10 в 9 степени. массив на миллиард, конечно, создавать не стоит! Последний раз редактировалось Serge_Bliznykov; 13.11.2012 в 11:05. |
13.11.2012, 11:14 | #6 | |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
0) Приводите ключевые моменты условия нормально, пожалуйста.
Цитата:
Зачем во всей этой истории двойной цикл? Решение "в лоб" - отсортировать массив и взять средний элемент (если N чётное - любой из средних), занимает O(N*lnN) по времени, O(N) по памяти. Можно поискать решения не столь лобовые. Например, использовать самобалансирующееся дерево для хранения пар "номинал - найденное количество купюр". Или попытаться ещё более художественно поиграть с условием "одинаковых элементов больше половины". В любом случае, сомневаюсь, что возможно решение быстрее O(N*lnN), так что Код:
|
|
13.11.2012, 11:27 | #7 | ||
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
в обсуждении на Timus
предложено решение с помощью A Linear Time Majority Vote Algorithm цитирую: Цитата:
или тут (pdf) в пользу этого алгоритма говорит то, что в условии задачи Цитата:
|
||
13.11.2012, 11:36 | #8 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
А. Красивый фокус.
Код:
|
13.11.2012, 11:41 | #9 |
Регистрация: 12.11.2012
Сообщений: 3
|
|
03.04.2014, 00:11 | #10 |
- Дорогой, а ты ку
Форумчанин
Регистрация: 06.10.2012
Сообщений: 181
|
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача на структуру(struct)/задача на работу с файлом | SevenArth | Помощь студентам | 0 | 26.04.2012 19:06 |
Задача о стрелках (задача Майхелла) | Silly Student | Помощь студентам | 0 | 14.12.2011 22:20 |
Задача на оптимальный расчет маршрута (задача в презентации) в табличном процессоре Excel | Toofed | Помощь студентам | 0 | 30.11.2011 01:12 |
Задача минимизации дисбаланса на линии сборки (задача минимакса) | LenZab | Microsoft Office Excel | 13 | 13.03.2011 22:51 |