Комментарии 51
Вспомнил своего учителя информатики.
Он нам постоянно давал похожие задачки. Которые даже на олимпиадах не решали.
Cам их потом и решал )
Он нам постоянно давал похожие задачки. Которые даже на олимпиадах не решали.
Cам их потом и решал )
Сейчас изучаю Питон. Он, мягко говоря, не самый быстрый, но мне будет интересно поставить свой личный рекорд именно на нем :) Уверен, что для победы в этом конкурсе надо выбрать язык пошустрее.
Спасибо за задание.
пс: Буду благодарен, если кто-то подскажет, как можно замерить скорость выполнения кода на питоне.
Спасибо за задание.
пс: Буду благодарен, если кто-то подскажет, как можно замерить скорость выполнения кода на питоне.
import time
start = time.time()
…
print «Time: » + str(time.time() — start)
start = time.time()
…
print «Time: » + str(time.time() — start)
Ну и «промышленным» методом замера скорости работы участков кода все-же являются профайлер docs.python.org/library/profile.html и иногда timeit для маленьких участков кода docs.python.org/library/timeit.html
Ну и вообще вот этот раздел документации не лишним будет посмотреть docs.python.org/library/debug.html
Ну и вообще вот этот раздел документации не лишним будет посмотреть docs.python.org/library/debug.html
По олимпиадам скажу, что лучшие решения не всегда получаются у участников, кто на «шустрых» языках пишет. Все зависит от вас, дерзайте
Правильной дорогой идем, товарищи:)
отличненько, будет чем заняться в свободное время)
Похоже на ТопКодеровские марафоны
Решение первой задачи (перебор, Perl)
# perl -Mbigint -E '$n=7;while(3**$i++!~/0{$n}/){}say--$i//0'
Не думаю, что в этой задаче подразумевается переборное решение. Уж больно долго оно будет работать для больших n (та даже относительно больших).
Если смотреть на уже решенные задачи, то там используется именно перебор. Так как эффективного алгоритма нет.
oeis.org/A006889
oeis.org/A131544
Результаты пока такие
n = 0; k = 0; t = 0.068s
n = 1; k = 10; t = 0.069s
n = 2; k = 35; t = 0.071s
n = 3; k = 148; t = 0.086s
n = 4; k = 332; t = 0.123s
n = 5; k = 540; t = 0.191s
n = 6; k = 540; t = 0.193s
n = 7; k = 7722; t = 1m45.413s;
oeis.org/A006889
oeis.org/A131544
Результаты пока такие
n = 0; k = 0; t = 0.068s
n = 1; k = 10; t = 0.069s
n = 2; k = 35; t = 0.071s
n = 3; k = 148; t = 0.086s
n = 4; k = 332; t = 0.123s
n = 5; k = 540; t = 0.191s
n = 6; k = 540; t = 0.193s
n = 7; k = 7722; t = 1m45.413s;
Все правильно. Кто дальше сможет?
$ php test.php
Started on 06:14:07
n = 1; k = 10; time = 7.6055526733398E-5 s
n = 2; k = 35; time = 8.2969665527344E-5 s
n = 3; k = 148; time = 0.00039792060852051 s
n = 4; k = 332; time = 0.001060962677002 s
n = 5; k = 540; time = 0.0094020366668701 s
n = 6; k = 540; time = 0.0021681785583496 s
n = 7; k = 7722; time = 0.37158298492432 s
n = 8; k = 22793; time = 4.0056979656219 s
End on 06:14:12
Как-то так…
Started on 06:14:07
n = 1; k = 10; time = 7.6055526733398E-5 s
n = 2; k = 35; time = 8.2969665527344E-5 s
n = 3; k = 148; time = 0.00039792060852051 s
n = 4; k = 332; time = 0.001060962677002 s
n = 5; k = 540; time = 0.0094020366668701 s
n = 6; k = 540; time = 0.0021681785583496 s
n = 7; k = 7722; time = 0.37158298492432 s
n = 8; k = 22793; time = 4.0056979656219 s
End on 06:14:12
Как-то так…
Все правильно, но эти ответы уже получил другой участник. См. на странице конкурса, там до n=12. По-видимому, автор написал бинарный код на каком-то из компилируемых языков.
Интерес был именно посмотреть результаты языка РНР ;)
Я абсолютно не сомневаюсь, что компилируемый язык справится с задачей гораздо быстрее.
Хотя я сейчас запустил на работу n в бесконечность. Остановится тогда, когда кончится память моего ноута. Тогда я и успокоюсь.
А пока могу привести отчеты по первым 10 результатам, если кому интересно.
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
Когда будут новые результаты — отчитаюсь ;)
Я абсолютно не сомневаюсь, что компилируемый язык справится с задачей гораздо быстрее.
Хотя я сейчас запустил на работу n в бесконечность. Остановится тогда, когда кончится память моего ноута. Тогда я и успокоюсь.
А пока могу привести отчеты по первым 10 результатам, если кому интересно.
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10
Когда будут новые результаты — отчитаюсь ;)
Понятно. Сомнение в ваших результатах вызывает только наличие десяти знаков после точки в оценке времени работы программы. Из этих 10 цифр правильных, самое большее 2-3. Или у вас «квантовый хнорометр» на основе атомов стронция установлен?: )
Если честно, то доли секунды не нужны, если речь идёт о минутах, а скоро будет о часах счёта.
Если честно, то доли секунды не нужны, если речь идёт о минутах, а скоро будет о часах счёта.
Это функция microtime уж не знаю как конкретно она работает, но результаты вроде как сходятся с засекаемым временем. Т.е.
Started on 06:14:07
… отброшу, т.к. в сумме меньше секунды…
n = 8; k = 22793; time = 4.0056979656219 s //Примерно, 4 секунды.
End on 06:14:12
Т.е. 06:14:12 — 06:14:07 = 5 секунд
Погрешность 1 секунда. Вроде, всё совпадает.
Если, все таки еще есть сомнения, то я смогу по личной просьбе предоставить исходник программы тестирования. Запустите на своей машине, чтобы убедиться, что я не с потолка беру время.
Да, забыл упомянуть, конфигурация на которой я запускаю: 1 ядро 2.2Гц. Параллельно работает гуглохром с 7 вкладками, Rythmbox и Transmission.
Started on 06:14:07
… отброшу, т.к. в сумме меньше секунды…
n = 8; k = 22793; time = 4.0056979656219 s //Примерно, 4 секунды.
End on 06:14:12
Т.е. 06:14:12 — 06:14:07 = 5 секунд
Погрешность 1 секунда. Вроде, всё совпадает.
Если, все таки еще есть сомнения, то я смогу по личной просьбе предоставить исходник программы тестирования. Запустите на своей машине, чтобы убедиться, что я не с потолка беру время.
Да, забыл упомянуть, конфигурация на которой я запускаю: 1 ядро 2.2Гц. Параллельно работает гуглохром с 7 вкладками, Rythmbox и Transmission.
Да нет, я имел в виду, что 10 знаков после десятичной точки в секундах — это неправильно. Если вы пишите 4.0056979656219, то из этих цифр поверить можно только в 4.01 (если округлить). Остальные цифры — это лапша. Если вы не по нейронному пульсару измеряли.: )
Я просто привел вывод в необработанном виде. Так, как мне выдала программа. И, честно говоря, принципиально не знаю какая точность у внутренних компьютерных часов.
Но, как Вы уже сказали, это не важно. Хотя наблюдение интересное, откуда же РНР берет лишние знаки, заведомо не измеряемые (ну или измеряемые только по нейронному пульсару).
Но, как Вы уже сказали, это не важно. Хотя наблюдение интересное, откуда же РНР берет лишние знаки, заведомо не измеряемые (ну или измеряемые только по нейронному пульсару).
Я не знаю, откуда это время берёт PHP, но самое точное, что мне когда-либо удавалось получить давало погрешность в 32 миллисекунды. То есть 3 знака после точки, плюс минус 0.032 с. Остальные цифры можете считать случайными.
Договорились ;)
Это виндовый GetTickCount. Сейчас есть более точные функции — QueryPerformanceCounter/QueryPerformanceFrequency которые постепенно проникают в другие языки программирования. Так что в будущем эти 0.032c уйдут как страшный сон.
В принципе, даже более древний метод через timeGetTime, может дать погрешность всего в 1 мс. А так, да, QueryPerformanceCounter хорош, единственный минус: для надёжности надо привязывать поток к конкретному ядру.
Не знаю, что вы хотели этим сказать, но там задачи другого плана. Ещё не забывайте про acm.sgu.ru
В своё время я много тренировался на этих двух серверах.
В своё время я много тренировался на этих двух серверах.
Во второй задаче есть ещё 3 «вертикальных» разбиения (наподобие тех «горизонтальных», что есть у Вас в блоге). Итого, получается 8.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Нет, в моём случае граф планарный, так как склеиваем только «лево» и «право». Вы знаете формулу для этого случая? В энциклопедии её нет, поэтому я смею надеяться, что эффективного решения задача не допускает. В противном случае это будет «жестокая лажа»…
про нули была задачка на школьной олимпиаде
Вполне возможно, это вообще классическая задача, просто именно для 3^n я не нашёл ответов в Интернете, поэтому можно соревноваться.
Конкурс завершён. Можно ознакомиться с итогами.
Всем спасибо за явное и неявное участие.
Всем спасибо за явное и неявное участие.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Конкурс по труднорешаемым задачам для программистов