Конкурс в fpprog#3

[metaclass]

На лоре феерический срач по третьем номеру журнала и заданиям на конкурсе в нем.

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

Да, кстати, я понял, что деградировал окончательно - мне хотелось бы сделать решение тамошних задач, но я этого сделать не смогу - ибо туп, ленив, занят на двух работах, а интереса, который бы меня заставил это все преодолеть уже того нет.
Видимо, придется в итоге все таки идти работать в НИИ Говна и Торфа, администрировать убунты у научных сотрудников, программировать "через силу" - это невозможно, быдлокодерское говнище получается.

PS: Фак мой мозг. Анонимусы с лора пишут, что все задачи предложены людьми, которые у меня во френдах - rssh и jek_hor. (Чорт, и авторы статей в журнале, в общем-то тоже). "Объединенная секта функциональщиков, линуксоидов и гуру-программистов".

Comments

[theiced.livejournal.com]

ну и таки да - задачи (исключая уёбищные форматы данных) - вполне себе на уровне лимпиадных.

ну, по памяти - республика 98ого года. Н точек на плоскости (Н большое), направленный граф на базе данных точек, приехать из точки А в точку Б совершив минимальное кол-во правых поворотов (ну типа на машине едешь, ага). сложность задачи ВЫШЕ чем предложенная обрезка карты (ещё раз - исключая уёбищные форматы данных) - предлагалась как одна из трёх задач (в сумме на 4 или 5 часов) школьникам. привет.

[theiced.livejournal.com]

http://projecteuler.net/index.php?section=problems&id=202

а это насчёт идиотизмов `олимпиадных`. слабо? ;]

[antilamer.livejournal.com]

Тупая задачка, уже почти решил, но пора домой - завтра доделаю :)

[antilamer.livejournal.com]

Сдал. Но покряхтел; противная задачка, не люблю такие :(

module Main where

import Control.Monad

answer alpha ps = sum [(if even (length s) then 1 else -1) * f (product s) | s <- filterM (const [True,False]) ps]
  where m = case (alpha`mod`3) of 0->0; 1->2; 2->1
        f p = (alpha-1-first)`div`(3*p) where first = head [x | x <- [p,2*p..], x`mod`3 == m]

main = putStrLn . show $ answer ((12017639147+3)`div`2) [5,11,17,23,29,41,47]

[metaclass.livejournal.com]

Хех, очередной ад, который lionet расшифровывать придется, а zabivator очередной пост на 1500 комментов напишет.
Ну а я просто посыплю голову пеплом - связь между задачей и ответом для меня сильно смутная :)

[antilamer.livejournal.com]

Ненене, Дэвид Блейн, в жопу расшифровку - я ее еще загольфил из любви к искусству, после того как написал :)

По сути там просто надо найти count {x in 1..N-1: coprime(x,N) AND (x+N)`mod`3 == 0}, где N=(K+3)/2, где K - число в условии.

Для этого я разложил руками N на простые множители (coprime(x,N) <-> x не делится ни на один из них), и с помощью стандартной формулы про диаграммы Венна посчитал этот count более или менее влоб.

[lionet.livejournal.com]

Для начала, рассмотрим что мы имеем в последней строке:

main = putStrLn . show $ answer ((12017639147+3)`div`2) [5,11,17,23,29,41,47]

Показываем результат работы функции answer, которая запускается с двумя магическими аргументами.

Затем идёт вот что:

answer alpha ps = sum [(if even (length s) then 1 else -1) * f (product s) | s <- filterM (const [True,False]) ps]
where m = case (alpha`mod`3) of 0->0; 1->2; 2->1
f p = (alpha-1-first)`div`(3*p) where first = head [x | x <- [p,2*p..], x`mod`3 == m]


пипец какой-то...

[antilamer.livejournal.com]

At least you did your best :)

[lionet.livejournal.com]

Да не говори, самому стыдно! :)

[metaclass.livejournal.com]

Я таки скажу, что тут уебищные форматы данных - неотъемлимая часть задачи. Собственно алгоритмы это конечно хорошо, но впихнуть их в объебос входного-выходного XML - ад редчайший.
Я сегодня на этом xml осмовском успешно заебал в голову два event-based парсера(на дельфи и дотнете). У первого производительность близка к нулю, у второго все настолько заабстрагировано, что либо "ты читаешь атрибуты" либо "ты читаешь ноду целиком".

[theiced.livejournal.com]

и возникает вопрос - на какой хуй они там хымыыль использовали? ведь дичайше неудобный формат для таких объёмов.

а вообще - решается просто. тупо пишется за 2 часа свой однопроходный-не-запоминающий-парсер для данного конкретного случая.

[metaclass.livejournal.com]

Ты уверен, что для однопроходного парсера хватит памяти?
Я думал в первом проходе сделать два индекса нод - мап по id всех нод и мап по id попадающих в полигон. А потом во втором анализировать, какие из ways и relations нам нужны, и сохранять в выходной файл только их ноды и их самих.
Это я исхожу из предположения, что психи обязательно сделают файл, у которого ноды будут после того, как на них сошлются по id, хотя там в файле такого не заметно.

[metaclass.livejournal.com]

Думаешь, если бы там был JSON или YAML было бы сильно проще?:)

[theiced.livejournal.com]

Ребе. Тама сама предметная область проста шо пиздец.

нода: id la lo хуета_сопутствующая
путь: id_ноды1 ... id_ноды_n хуета сопутстсвующая
объект: аналогично

эти гении вместо вменямого плэйн текст файлика состряпали монстроидальный говнохымыыль с жабами и червями но БЕЗ ФОРМАЛЬНОГО ОПИСАНИЯ ФОРМАТА. нет его. тока `мы думаем что хымыыль будет примерно такой`. зато хымыыль, да. универсальный формат бля.

[metaclass.livejournal.com]

Если соблюсти все краевые случаи типа "в имени юзера \r\n" то формат получится не сильно проще.
Хотя шо мне говорить, я тут сам каждый день от нехрен делать и нежелания использовать xml деревообразные CSV делаю :)

[theiced.livejournal.com]

краевые случаи вида `в имени юзера \r\n` обходятся просто: `имя юзера - строка из латинских букев и арабских цифирей` в доке.