| Автор | Сложные и красивые задачи по программированию |
|---|
для Daemonic:
Да, вот это правильно
Линейная сложность по времени, единичная по памяти
Нули вставлять уже не надо
Итого два пробега)
Два пробега эквивалентны одному же
Думаю, имелся ввиду вложенный квадратичный, как для простейших сортировок |
чтобы совсем уж определиться, то:
1. Сразу считаем сумму и по циклы вычитаем.
2. Дели сдвигом (на старых платформах деление долговато).
На плюсах будет:
unsigned func(const vector<unsigned>& data_)
{
unsigned rez=((data_.size()*(data_.size()+1))>>1);
for(const_iterator it=data_.begin();it!=data_.end();++it)
rez-=(*it);
return rez;
}
|
для Daemonic:
Крутое решение. |
| Интересно, что скажет автор задачи - SirReal |
| ТС ты жестокий человек. Люди планируют бухать, а ты задачками топишь |
я далеко не автор задачи :)
12 лет назад мне ее рассказал бывший одноклассник в ресторане Тинькофф в Петербурге. он тогда работал в Гугле, а я в аналогичной конторе. он программистом, а я техписом. было нам лет по 25.
как бывший математик-олимпиадник, я подумал примерно полуминуты и сказал: а почему бы тупо бы не перемножить все числа в исходном массиве, перемножить все числа в новом массиве, и не разделить первое на второе?
он сказал, ну ты даешь! все наши кандидаты что-то пишут, считают, а ты вот в уме так взял и решил. круть!
что сказать -- было приятно. только потом я понял, что в том или ином языке может не быть поддержки длинных чисел, или обработки числе может быть медленнее сортировки (в зависимости от N). но мысль все-таки была правильной (для 2008 года). |
для SirReal:
А что насчёт решения Daemonic? |
для Daemonic:
19. Вот именно! |
| Делал брату курсач. Там в одном прямоугольнике амбаре, должны случайным образом генерироваться другие прямоугольники комнаты, а в самих комнатах и амбаре различные объекты, часть из них обыскиваемые на предмет ключа для выхода из амбара. Приходилось учитывать, чтобы все помещения и объекты были доступны для прохода человечка, амбар не выгладил пустым и комнаты иногда соприкасались друг с другом по общей стене, так красивее. |
для FireSwarm:
Крутое решение
Вот это тот самый случай, о котором я говорил про собеседование. Типичная задачка на несколько строк простейшего кода на чистом языке. |
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
Сама задача, простая. Но ничего эффективней придумать не могу, кроме как, с начало отсортировать оставшиеся элементы. Потом вычев из второго первый понять длину шага. Затем перебором от первого до последнего сравнивать ожидаемый с текущим элементом, если не равны, значит это то пропащее число. |
| кладезь проггеров) |
| капец у вас сложные и интересные задачи. Как написали выше,просто складываем все числа и вычитаем n(n+1)/2 получаем минус удаленный элемент. А чтобы работало для очень n и быстрее вычитаем не n(n+1)/2 в конце, а каждый шаг 1,2,3 и так далее n. Очевидно быстрее нельзя. Задачка слишком тупая даже для школьной олимпиады по проганью |
для Ути-Пути2:
Как написали выше,просто складываем все числа и вычитаем n(n+1)/2 получаем минус удаленный элемент.
Ну видишь, ты хороший математик, а для меня формула n(n+1)/2 совсем не очевидна. |
для AndruxaX:
поздравляю тебя, это называется формула суммы арифметической прогрессии и проходится в 9 классе средней общеобразовательной школы |
для Ути-Пути2:
поздравляю тебя, это называется формула суммы арифметической прогрессии и проходится в 9 классе средней общеобразовательной школы
Ну проходится, а после 9 лет, как закончил 9 класс легко забывается, если её не применять. |
Потом вычев из второго первый понять длину шага.
Тут надо ещё только учесть, что второй и может оказаться пропащим. Поэтому нужно 3 элемента подряд пере вычитать, чтоб понять длину шага. |
В моем решении есть ошибка:
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
Не указано, что это натуральный ряд.
Поэтому решение немного усложняется:
1. проходим по первой последовательности и складываем все элементы последовательности.
2. вычитаем из получившейся суммы элементы второй последовательности:
uint64 func(const vector<unsigned>& data1_,const vector<unsigned>& data2_)
{
uint64 rez(0);
const vector<unsigned>::const_iterator it;
for(it=data1_.begin();it!=data1_.end();++it)
rez+=(*it)
for(it=data2_.begin();it!=data2_.end();++it)
rez-=(*it);
return rez;
}
|
для Daemonic:
Поэтому решение немного усложняется:
1. проходим по первой последовательности и складываем все элементы последовательности.
2. вычитаем из получившейся суммы элементы второй последовательности
А что мешает при таком подходе за один проход прибавлять i-й элемент первой последовательности и тут же вычитать соответствующий элемент второй последовательности?
Разная длина последовательностей легко разрешается поправкой индекса. |
begin
writeln "hellow world"
readln
end |
