LINUX.ORG.RU
решено ФорумTalks

Мини-олимпиада по программированию — всякие забавные задачки и их решение.


0

3

Олимпиада проводится прямо в этом треде, продолжается пока он не уйдёт с первой страницы.

Правила таковы:
1) Начинающий даёт задачу по информатике и своё к ней решение на каком-либо языке программирования
2) Следующий участник должен решить задачу одного из предыдущих участников на таком языке программирования. который ещё не использовался в треде. Разрешается любой язык программирования, для которого есть публично доступный компилятор/интерпретатор с открытыми исходными кодами и свободной лицензией, который можно запустить на GNU/Linux без применения несвободных компонентов.
3) Решивший хотя бы одну задачу имеет право задать свою задачу

При желании можно решать и уже решенные задачи, но если язык программирования уже был в треде, задача уже была решена похожим способом, или тем более тот же язык программирования был применен для той же задачи и решение было похожее — баллов начисляется меньше.

В общем, чем более оригинален язык (например если уже был C, а решение на C++ — это ценится меньше чем решение на каком-нибудь lisp), чем более оригинален алгоритм, чем более интересная задачка — тем лучше.

Итак, первая задача:

Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов. (Всего, таким образом, для задания прямоугольника понадобятся 4 числа). Заданы два прямоугольника, Пр1 и Пр2. Определите площадь той части Пр1, которая не входит в Пр2. (Алгоритм должен быть пригоден для любого расположения Пр1 и Пр2)
(Задача с всесоюзной олимпиады по информатике 1988)

Решение на bash:
http://paste.org.ru/?dg0mja
Решение на C++ (не моё, в олимпиаде не участвует):
http://pastebin.com/6CfwEjmd

В общем, решите эту задачу на любом языке, какого ещё не было и запостите свою.

★★★★★

по мотивам анекдотика:
«заходишь в толксы, а там - алгоритмы/программы, алгоритмы/программы...»

вам что, работы мало?

dib2 ★★★★★ ()

>2) Следующий участник должен решить задачу одного из предыдущих участников на таком языке программирования. который ещё не использовался в треде. Разрешается любой язык программирования, для которого есть публично доступный компилятор/интерпретатор с открытыми исходными кодами и свободной лицензией, который можно запустить на GNU/Linux без применения несвободных компонентов.

Уж лучше б сразу сказал писать на Brainfuck'e.

Zak ★★ ()

Первая задача на питоне.

python -c "from itertools import product as p; from sys import argv as a; p1 = set(p(range(int(a[1]), int(a[3])), range(int(a[2]), int(a[4])))); p2 = set(p(range(int(a[5]), int(a[7])), range(int(a[6]), int(a[8])))); print len(p1-p2)" 0 0 5 5  3 3 6 6
baverman ★★★ ()
Ответ на: комментарий от baverman

Как не старайся, но как на перле не получится.

Bad_ptr ★★★★ ()
Ответ на: комментарий от Bad_ptr

Что поделать, язык не предназначен для создания однострочных увлекательнейших игр.

baverman ★★★ ()

тебя не смущает, что второе решение, которое якобы на C, написано на самом деле на C++?

grouzen ★★ ()

Я, помнится, по истории провести пытался :-)

r_asian ☆☆☆ ()
Ответ на: комментарий от grouzen

> тебя не смущает, что второе решение, которое якобы на C, написано на самом деле на C++?
Поправил

Xenius ★★★★★ ()
Ответ на: комментарий от baverman

> Первая задача на питоне.

python -c «from itertools import product as p; from sys import argv as a; p1 = set(p(range(int(a[1]), int(a[3])), range(int(a[2]), int(a[4])))); p2 = set(p(range(int(a[5]), int(a[7])), range(int(a[6]), int(a[8])))); print len(p1-p2)» 0 0 5 5 3 3 6 6


На 2 4 6 2 3 6 2 3 не работает, показывает 0, хотя моё даёт 7

Xenius ★★★★★ ()

>Решение на C (не моё, в олимпиаде не участвует)

4.2. Это же Си++!

luke ★★★ ()
Ответ на: комментарий от baverman

> Первая задача на питоне.

И да, с тебя следущая задачка, если поправишь. И желательно ещё объяснение для тех кто питоном не владеет.

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

На 2 4 6 2 3 6 2 3 не работает, показывает 0, хотя моё даёт 7

Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов

baverman ★★★ ()
Ответ на: комментарий от baverman

> Прямоугольник, стороны которого параллельны осям координат, будем задавать координатами его левого нижнего и правого верхнего углов

А кто сказал, что оси координат слева направо и снизу вверх, а не как-то иначе? И даже если это принять, программа должна выдать ошибку, а не заведомо неверный ответ.

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

А кто сказал, что оси координат слева направо и снизу вверх, а не как-то иначе?

Здравый смысл. Верх он и в африке верх, туда числа растут. Собственно как и вправо.

И с каких пор на олимпиадных задачках дают невалидные входные данные?

baverman ★★★ ()
Ответ на: комментарий от baverman

>И с каких пор на олимпиадных задачках дают невалидные входные данные?

Данные, в случае которых нет решения, частенько дают.

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

Тогда в условии должен оговариваться вывод, сигнализирующий об отсутствии решения.

baverman ★★★ ()
Ответ на: комментарий от baverman

> Верх он и в африке верх, туда числа растут. Собственно как и вправо.

Числа растут не вверх, а в большую сторону. А координаты могут начинаться с любого угла.

Впрочем, не проще ли тебе исправить решение, чем спорить?

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

Впрочем, не проще ли тебе исправить решение, чем спорить?

Ты должен понимать, что условие про порядок углов, важная часть, на которую опирается решение, поэтому нет, не проще.

P.S. Привет гуманоидам с другой системой координат.

baverman ★★★ ()
Ответ на: комментарий от baverman

> Привет гуманоидам с другой системой координат.
У монитора координаты обычно начинаются с левого-верхнего угла.

Ты должен понимать, что условие про порядок углов, важная часть, на которую опирается решение, поэтому нет, не проще.

Ну моё не опирается — любые два противоположных угла принимает. Однако объяснить решение ты можешь или нет?

И да, хорошо, решение принимается.

Xenius ★★★★★ ()

GNU Smalltalk 3.x

Rectangle class extend [
    fromArgs: aBaseNum [
        ^self left: (Smalltalk getArgv: aBaseNum) asInteger
               top: (Smalltalk getArgv: aBaseNum + 1) asInteger
             right: (Smalltalk getArgv: aBaseNum + 2) asInteger
            bottom: (Smalltalk getArgv: aBaseNum + 3) asInteger
    ]
]

Eval [
    | rectA rectB intersection result |
    rectA := Rectangle fromArgs: 1.
    rectB := Rectangle fromArgs: 5.
    intersection := rectA intersect: rectB.
    result := intersection
        ifNil: [#Nope]
        ifNotNil: [rectA area abs - intersection area abs].
    Transcript << result; nl
]
[dmatveev@web148 ~]$ gst -f lor.st 0 5 5 0 1 4 4 1
16
yoghurt ★★★★★ ()
Ответ на: комментарий от Xenius

Исправленное, малой кровью, решение.

python -c "from itertools import product as p; from sys import argv as a; p1 = set(p(range(*sorted((int(a[1]), int(a[3])))), range(*sorted((int(a[2]), int(a[4])))))); p2 = set(p(range(*sorted((int(a[5]), int(a[7])))), range(*sorted((int(a[6]), int(a[8])))))); print len(p1-p2)" 2 4 6 2 3 6 2 3

Определяет два множества точек (x,y), принадлежащих прямоугольникам. Результат: число элементов в их разности.

baverman ★★★ ()
Ответ на: комментарий от yoghurt

О, кажется я не учёл в своём алгоритме что прямоугольники могут быть и вложенными.

Но вообще, решение задачи на языке, где есть специальная функция для этого ­— немного читерство.

Xenius ★★★★★ ()
Ответ на: комментарий от Xenius

Так уж повелось, что в смолтоке, родоначальнике GUI, класс для прямоугольника был в стандартном образе с незапамятных времён :}

Вообще, я изначально писал вариант на Emacs Lisp, но под конец редактор напрочь завис, и, т.к. я не сохранялся, пришлось сделать проще.

yoghurt ★★★★★ ()

Вот тогда задача от меня, немного смежного рода.

Имеем плоскость и N прямоугольников с одинаковыми размерами.

Координаты в плоскости задаются в условных единицах и являются целочисленными (аки сетка). Размеры прямоугольников тоже задаются в условных единицах и являются целочисленными.

N прямоугольников раскладываются на плоскости в заданном порядке. Каждый прямоугольник может лежать как альбомно, так и портретно.

Прямоугольники частично накладываются друг на друга, образуя вместе единую фигуру. Надо найти координаты каждого угла получившейся фигуры.

Задача с районной школьной олимпиады по информатике г. Нижнего Новгорода за какой-то там код в первой половине нулевых :)

yoghurt ★★★★★ ()
Ответ на: комментарий от yoghurt

входные данные: 1. длина и ширина прямоугольника 2. набор координат левых верхних углов прямоугольника (в декартовой системе) и указание расположения (портретное/альбомное) для каждого.

выходные - набор координат углов.

максимальные размеры поля, на котором оно всё происходит, скажем, 1024x1024

yoghurt ★★★★★ ()

http://pastebin.com/cVdhnPah

Увы, на пастебине только NASM, а не GNU Assembler. Вроде иногда правильные результаты выдаёт, лень было писать скрипт проверки.

luke ★★★ ()
Ответ на: комментарий от luke

Неплохо бы ещё говорить или писать в комментарии, какую из задач ты решаешь. Хотя наверное всё-таки первую.

Xenius ★★★★★ ()

К сожалению, одной задачки маловато для того что бы что-то оценивать, видимо организовывать олимпиаду надо как-то по-другому.

Впрочем, получены довольно интересные решения для первой задачки и выяснено, что решение на баше не учитывает возможность расположения одного прямоугольника внутри другого.

Xenius ★★★★★ ()

Исправил ошибку в алгоритме — теперь должен работать даже если один прямоугольник внутри другого.

http://paste.org.ru/?1izebz

Xenius ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.