ibash.org.ru - Новый цитатник Рунета | Цитаты: По дате По рейтингу Случайно Добавить Поиск RSS |
Форум: Олимпиада по информатике — всякие забавные задачки и их решение. 1 > [RSS] | Форум: Вход Регистрация Участники Поиск RSS |
Xenius 27.09.2011 - 14:10 | Итак. Правила таковы: 1) Начинающий даёт задачу по информатике и своё к ней решение на каком-либо языке программирования 2) Следующий участник должен решить задачу одного из предыдущих участников на таком языке программирования. который ещё не использовался в треде. Разрешается любой язык программирования, для которого есть публично доступный компилятор/интерпретатор с открытыми исходными кодами и свободной лицензией, который можно запустить на GNU/Linux без применения несвободных компонентов. 3) Решивший хотя бы одну задачу имеет право задать свою задачу При желании можно решать и уже решенные задачи, но если язык программирования уже был в треде, задача уже была решена похожим способом, или тем более тот же язык программирования был применен для той же задачи и решение было похожее — баллов начисляется меньше. Итоги подводятся когда в треде будет хотя бы 10-20 решений. Итак, первая задача: Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов. Заданы два прямоугольника, Пр1 и Пр2. (Всего, таким образом, для задания прямоугольника понадобятся 4 числа). Определите площадь той части Пр1, которая не входит в Пр2. (Алгоритм должен быть пригоден для любого расположения Пр1 и Пр2) (Задача с всесоюзной олимпиады по информатике 1988) Решение на bash: http://paste.org.ru/?dg0mja Решение на C (не моё, в олимпиаде не участвует): http://pastebin.com/6CfwEjmd В общем, решите эту задачу на любом языке, какого ещё не было и запостите свою. |
VovanZ #23 - 16.10.2011 - 16:10 | #17 Моё собственное слегка быдлокодерское решение на яваскрипте http://jsfiddle.net/c8Zaw/ Кстати, jsfiddle удобная штука, позволяет писать прямо в браузере и сразу тестить любой код на html, css и javascript #22 +1, алгоритм вроде правильный и все сходу придуманные тесты проходит. Ждём вашей задачи =) |
Кто-то #24 - 16.10.2011 - 18:54 | Ну вот такая задачка, которая имеет весьма хитрое решение :) Все знают, что билет называется счастливым если сумма цифр левой части номера билета равняется сумме цифр правой части номера билета. Девочка Олечка очень часто пользуется трамваем и каждый раз проверяет свой билет на свойство «счастливости», а что бы повысить свои шансы она проверяет номер билета на счастливость не только в десятичной системе исчисления, но и в системах исчисления с другим основанием, естественно не доходя до случая, когда номер билета вырождается в одну единственную цифру. Поскольку перевод чисел в другую систему исчисления является явно непосильной задачей для девочки Олечки, помогите ей и составьте программу, которая будет определять, является ли номер билета счастливым. Входные данные Каждый тестовый набор содержит номер билета A. 100 000 <= A <= 999 999 Выходные данные Для каждого тестового набора необходимо вывести YES если номер билета является счастливым хотя бы в одной системе исчисления и NO если он таковым не является. Пример входных данных 699050 222222 Пример выходных данных YES YES |
VovanZ #25 - 16.10.2011 - 19:07 | Хмм, интересно... Во первых, что делать если число получается из нечетного числа символов? Например xyz. Считать, что xyz = 0xyz ? Навскидку - решение брутфорсом, т. е. перебором систем счисления от 2х до A-1 пишется относительно несложно, но работает охрененно долго. На каком-нибудь соревновании оно бы не зашло по тайм лимиту. Возможно существует более оптимальное решение.... |
VovanZ #26 - 16.10.2011 - 19:10 | Кажется я понял фишку =) Буду дома, напишу. Просьба не занимать C++ :) |
Кто-то #27 - 16.10.2011 - 19:30 | Входные данные подразумевают гарантировано 6 цифр в числе. |
VovanZ #28 - 16.10.2011 - 20:26 | #27 - после перевода числа в другую систему может появиться нечётное число разрядов. Пример: 100000(10-чная система, 6 разрядов) = 2050544 (6-чная система, 7 разрядов) |
VovanZ #29 - 16.10.2011 - 20:46 | http://pastebin.com/LStTaL1k - моё решение на C++ Не запускал, возможны синтаксические ошибки. Не уверен в правильности, но контр-пример придумать не могу. Просьба отписаться о том правильно ли я понял условие и правильно ли моё решение. Те кто не решал задачу - не открывайте, вам будет неинтересно) |
Кто-то #30 - 16.10.2011 - 21:03 | Да, всё правильно, это самое эффективное решение :) |
VovanZ #31 - 16.10.2011 - 21:33 | Красивая задачка, мне понравилось =)) |
VovanZ #32 - 16.10.2011 - 22:00 | Не уверен, что правильно понял пункт 3 правил, которые предложил топикстартер "Решивший хотя бы одну задачу имеет право задать свою задачу". Думаю, что решив вторую задачу я могу предложить ещё одну свою. Я решил, что брать задачи из архивов типа Тимуса не очень интересно, но ничего своего интересного придумать не могу. Пусть будет задача без особой фишечки, но технически сложная, так что за***шься писать. Дано n (n<100) выпуклых многоугольников на плоскости заданных координатами точек. Координаты всех точек целые и не превосходят по модулю 100000. Найдите площадь их пересечения. Формат ввода: В первой строке записано единственное число n - количество многоугольников. В следующей строке число m_1 - количество вершин первого многоугольника, в каждой из следующих m_1 (m_1 > 2) строк записана пара целых чисел - координаты вершины многоугольника. Вершины даны в порядке обхода в произвольном направлении. Далее следует второй многоугольник заданный в таком же формате и т. д. Формат вывода: Единственное вещественное число с точностью не менее 10^5. Пример ввода: 2 4 0 0 1 0 1 2 0 2 4 0 0 2 0 2 1 0 1 Пример вывода: 1 |
VovanZ #33 - 16.10.2011 - 22:02 | P. S. Задача является в некоторой степени троллингом, ибо я осознаю, что задача решаема, даже примерно представляю как её решать, но мне самому понадобится очень много времени для её написания =) |
| К списку вопросов | Страницы: 1 > |
| «ibash.org.ru — Новый цитатник Рунета» | Почта вебмастера: imail@ibash.org.ru |