| Автор | Сложные и красивые задачи по программированию |
|---|
В этом топике пишем НЕОБЫЧНЫЕ задачки по программированию с которыми вы встречались. Чем короче решение, тем лучше для топика, никто простыни кода читать тут не будет)
Писать решения можно на любом языке, но лучше просто на русском блок-схемами |
Первая задача от меня
Встретилась мне в 2003(вроде) в универе на олимпиаде.
На землю летит метеорит. Выживут ли динозавры?
Входные данные:
Масса метеорита, скорость метеорита, угол соприкосновения с Землей.
Выходные данные:
yes(если выживут)
no(если погибнут)
P.S.
Данные Земли указаны в задаче. |
На всякий случай, если кто на олимпиадах по программированию не был.
Входные данные - это то, что вводится при тесте программы. Они меняются и тестов может быть сколько угодно.
Выходные данные - это то, что должна ответить ваша программа на ввод входных данных |
Не буду мучить - ответ "no"
Т.е. в теле программы нужно было просто создать возможность запроса данных. Никак их не обрабатывать и вывести при любом вводе "no"
Типа логика в том, что раз сейчас нету динозавров, то они явно вымерли. И совсем не важно падал на Землю метеорит или пролетел мимо. |
| Ну вообще большие динозавры вроде как умерли не из-за метеорита, а из-за совокупности факторов, т.е. чисто метеор их не убил, только был одним из факторов. А мелкие динозавры и сейчас живы так-то.. |
для Мэйлин:
Поэтому и ответ "no". Они вымерли не зависимо от метеорита. |
| Ничего не понял, но интересно. |
| чувак, так ты слона не продашь :) |
| Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число. |
для SirReal:
двойным перебором? |
| подождем оптимального ответа |
Расставляешь все цифры по порядку взад, есть несколько общеизвестных способов. После этого пробегаешься по массиву ещё раз, выискивая пропуск
Вот сам написал и думаю, что есть и побыстрее решение наверняка. |
Типа логика в том, что раз сейчас нету динозавров, то они явно вымерли. И совсем не важно падал на Землю метеорит или пролетел мимо.
Ни красоты тут не вижу, ни программирования. Это как детская шутка, у кого борода длиннее - у Карла или Маркса. |
для FireSwarm:
На самом деле - да. Эту задачу придумывал второкурсник и мой паралелльноклассник. Не знаю почему её включили, но чел был в админах-организаторах, потому что на городской олимпиаде победил |
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
Я бы вставкой решал. |
двойным перебором?
А зачем двойным?
Известно же, что именно упорядоченных и от 1 до n
Можно просто расставлять нули/единицы (есть/нет) в массив фиксированной длины (ну со сдвигом на 1, понятно, тк с 0)
1 пробег перемешаннго массива, сложность n
Быстрее невозможно, потому что всегда, пока не обработали все n-1, среди необработанных чисел может быть число и которое есть, и которого нет
Затем 1 пробег до первого нуля – асимптотической сложности не добавляет
Итого n
По памяти можно попробовать чё-нить извернуться, чтобы всё не хранить, но ХЗ |
для Небылица:
Я не понял, можно кусок кода как ты выставляешь нули и еденицы |
А зачем двойным?
1 пробег перемешаннго массива
Затем 1 пробег до первого нуля
Итого два пробега) |
Ну можно сделать одним пробегом и без хранения - известно, что сумма всех натуральных чисел от 1 до N равно (1+N)*N/2.
Так что нужно сложить все числа и получившийся результат вычесть из (1+N)*N/2.
Разность будет равна неизвестному числу.
Один проход, учитывая, что мат операции быстрей, чем ветвления, то на многих платформах будет быстрей. |
Я не понял, можно кусок кода как ты выставляешь нули и еденицы
и, кстати, ты получается второй массив создаешь, а это уже память, раз мы про олимпиадные задачки говорим |
