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 В общем, решите эту задачу на любом языке, какого ещё не было и запостите свою. |
Xenius #1 - 27.09.2011 - 14:58 | Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов. (Всего, таким образом, для задания прямоугольника понадобятся 4 числа). Заданы два прямоугольника, Пр1 и Пр2. Определите площадь той части Пр1, которая не входит в Пр2. (Алгоритм должен быть пригоден для любого расположения Пр1 и Пр2) Кажется, опечатка в условии. Впрочем, на смысл она не влияет |
Кто-то #2 - 27.09.2011 - 16:28 | А C,C++,C# считать тремя разными языками? |
Zenitur #3 - 27.09.2011 - 16:36 | На компе стоит винда, как поставить окно поверх всех окон? |
gdulhr #4 - 27.09.2011 - 16:58 | #3 Поставить KDE для виндовс. Я как-то решился но забил на это ибо тогда по gprs это было нереально. :) |
fire #5 - 27.09.2011 - 17:24 | #3 http://img-fotki.yandex.ru/get/4102/pant-alexander.10/0_25c16_6b53bb2c_-1-L так? :D |
Xenius #6 - 28.09.2011 - 03:50 | Разными, если решение активно использует уникальные фичи того языка. То есть если решение на C++ отличается от решения на C только например cout вместо printf, то не канает |
Кто-то #7 - 29.09.2011 - 08:53 | >Всего, таким образом, для задания прямоугольника понадобятся 4 числа. А числа целые или вещественные? А если вещественные, то сколько знаков после запятой? А могут эти числа быть отрицательными? А могут быть прямоугольники вырожденными? А можно указать нижнюю и верхнюю границу для этих чисел? |
Xenius #8 - 30.09.2011 - 09:43 | Реши хоть как-нибудь. Эта задача алгоритмическая больше — то есть надо придумать алгоритм, а он вряд ли отличается для целых или нецелых чисел. |
Кто-то #9 - 30.09.2011 - 20:46 | Прошу считать меня ленивым извращенцем (язык C#) http://pastebin.com/t72nSTvC |
Кто-то #10 - 30.09.2011 - 20:50 | Oops! а моё решение не удовлетворяет пункту 2. |
Кто-то #11 - 30.09.2011 - 21:12 | Пофиксил версию под MonoDevelop http://pastebin.com/BVH0vCBx |
Xenius #12 - 01.10.2011 - 03:39 | Пофиксил неправильный алгоритм подсчёта — учёл что один прямоугольник может быть внутри другого: http://paste.org.ru/?1izebz #9 Решать оно наверное решает, но таки там алгоритма никакого нет, а только обёртка над библиотечным вызовом. |
Xenius #13 - 01.10.2011 - 03:43 | Забавно, в Шиндовшс даже C# кривее чем в моно? |
Кто-то #14 - 01.10.2011 - 10:27 | #13 да не сказал бы, просто в первом случае я взял Rect из пространства имён, которое я не нашёл в Mono, пришлось взять другое пространство имён и Rectangle вместо Rect. #12 что значит нет алгоритма? Я пишу другом языке и на 100% использую его возможности. Вот скажем, если стоит задача сложить два числа в которых по 100 значащих чисел я возьму Java и классы BigInteger или BigDecimal и решу эту задачу в одну строчку и буду прав, потому что нет никакого профита хвататься за C++ и реализовывать длинную арифметику. То же самое с НОД, можно реализовывать алгоритм Евклида, а можно взять библиотечную функцию Java. Или вот дана такая задача. Дано n от 1 до 100, необходимо посчитать сколько существует простых чисел <=n Я могу написать вот такое ленивое решение http://pastebin.com/fnuf41uw и буду прав, т.к. моё решение будет самым быстрым (т.е. и напишу я его быстрее чем остальные, и работать оно будет быстрее чем у остальных)! Я конечно понимаю, что нельзя брать функции из нестандартных библиотек, которые не поставляются со средой разработки. |
VovanZ #15 - 15.10.2011 - 17:28 | http://pastebin.com/tLK83USN - Scheme P. S. Юзайте acm.timus.ru =) |
VovanZ #16 - 15.10.2011 - 17:33 | P. P. S. Тестил в DrRacket, но должно работать в любом интерпретаторе Scheme. P. P. P. S. Scheme незначительно отличается от Lisp, чтобы работало в лиспе надо слегка изменить, но думаю можно считать, что Scheme и Lisp слишком блихки, так что не постите на лиспе, жду решения на хаскелле или прологе =)) |
VovanZ #17 - 15.10.2011 - 17:48 | Моя задача: Петя записал на бумажке натуральное число n в системе исчисления k. Вася нашёл эту бумажку и решил, что на ней записано число в системе исчисления l (k<=l), перевел его в десятичную систему и получил m. Ваша задача восстановить n. Программе на входе подается три числа k, l, m выведите n. Пример: k=2, l=3, m=10, на бумажке было записано "101", значит n=5. |
VovanZ #18 - 15.10.2011 - 17:50 | P. S. Задачу придумал сам. |
VovanZ #19 - 15.10.2011 - 17:52 | P. P. S. Если описанный случай невозможен выведите "WTF?". |
VovanZ #20 - 15.10.2011 - 18:13 | P. P. P. S. В тексте задачи конечно же имеется ввиду система счисления, а не "система исчисления", досадная опечатка. |
VovanZ #21 - 15.10.2011 - 18:14 | 2admins: просьба объединить мои последние посты в один |
Кто-то #22 - 15.10.2011 - 22:56 | #17 Пока никто не использовал мой любимый язык... http://pastebin.com/uCxCEQ2N Случай больших чисел не рассматривал P.S. Юзайте www.codeforces.ru |
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 |