Pull to refresh

Новогоднее хабра-соревнование по программированию-2013 (C++)

Reading time 3 min
Views 47K
Все мы слышали поговорку: как новый год встретишь — так его и проведешь. Оливье в сторону!

Рассчитывать на 5 часов адского программирования в праздник было бы негуманно, потому задача всего одна и она весьма лапидарна:
Программа должна прочитать из стандартного потока ввода целое число N (от 1 до 230), и напечатать сумму простых чисел меньших либо равных N.
Побеждает тот, кто напишет самое быстрое решение, проходящее все тесты (хотя-бы один неправильный ответ — и решение отклоняется). Скорость решения оценивается на тестах в районе верхней границы допустимого диапазона N (но не ровно 230).

Победитель получает всеобщее признание, сотни кармы и приятное чувство что он порвал всех на Хабре. Долгие годы молодые поколения разработчиков будут восхищаться его кодом, а девушки — чепчики в воздух бросать. По меньшей мере первые 4 read-only пользователя будут приглашены на Хабр.

Ограничения:
  1. Размер файла с решением — не более 1024 байт без учета первой строки с комментарием
    (краткость — сестра таланта)
  2. Только один язык программирования — C++ в исполнении clang 3.2, только стандартные библиотеки (+pthreads). Если используете С++11 — указывайте свою версию libc++ на всякий случай. С OpenMP/TBB — не судьба, с clang они пока плохо уживаются.
    Много кода писать тут не придется, так что даже если С++ не ваш основной язык — в нем легко будет разобраться на уровне достаточном для решения задачи.
  3. Тесты будут проводиться на 64-х битном Linux-е.
    Можно использовать 4 ядра процессора (i7-3820) и не более 30 Гб памяти.
  4. Допустимое время работы на каждый тест — не более 60 секунд.

Оформление решения, сроки и куда слать
Решения принимаются до 23:59 (время Московское) 1-го Января 2013-го года по адресу contest@14.by, файл с решением должен быть прикреплен к письму — не нужно вставлять код в само письмо!

В первой строке решения должен быть комментарий вида:
//@BarsMonster
Где BarsMonster — имя вашего пользователя на HabraHabr (участвовать могут и read-only пользователи, регистрируйтесь)

Результаты и решения будут опубликованы на Хабре — по возможности не позднее 2-го Января.

Пример решения: (немного не успевает по времени, 242 байта)
//@BarsMonster
#include<iostream>
using namespace std;

int main()
{
  __int64_t n, sum=0;
  cin>>n;
  for(__int64_t i=2;i<=n;i++)
  {
    for(__int64_t j=2;j<i;j++)
      if(i%j==0)goto next;
    sum+=i;
next:;
  }
  cout << sum << endl;
}

Пример работы:
test@lbox2:~$ ./a.out
10
17

test@lbox2:~$ time ./a.out
100000
454396537

real    0m7.073s
user    0m4.693s
sys     0m0.000s


Update: 22 минуты после начала конкурса — и уже пришло первое решение:-)
Update: 3 часа после начала соревнования — 10 решений.
Update: Для уменьшения количества драмы убрал запрет на повторную отправку, но прошу не злоупотреблять.
Update: Для тех кто пишет в VisualStudio — простейшую проверку на компилируемость можно сделать тут: llvm.org/demo (не забываем выбирать C++)
Update: 3 часа до конца соревнования — количество решений перевалило за 160.
Update: 1 час до конца соревнования — 200 решений.
Update: 7 минут до конца — прилетает по 3-5 решений в минуту
Update: Прием решений закончен, получено 265 решений (с дубликатами). Таблица результатов, исходные коды победителей, анализ ошибок — все будет опубликовано 2-го Января (надеюсь успеть) в отдельной статье в этих же хабах.
Update: 183 решения без повторных отправок.
Update: Файл main.cpp прислали 42 участника
Update: 162 решения скомпилировались с первого раза, я ожидал намного худшего.
Update: 164 решения скомпилировались, 1 пало жертвой C++11, 18 — жертвой более более прозаических ошибок.
Update: Простые тесты (1, 10, 1000, 100000, 1000000) прошли 109 решений, 47 дали неправильные ответы (включая и креши), 8 не успели выдать ответ за минуту (пример решения из статьи тест на 1млн проходит за 5 минут 36 секунд).
Update: Сложные тесты завершены, 91 решение прошло все тесты в установленное время, 5 — с неправильными ответами, 13 — не уложились в минуту на тест. Время решения — измерялось с микросекундной точностью, и бралось среднее по результатам 4-х разных тестов. Формируется таблица результатов.
Update: Для top-3 тесты повторены 100 раз (время суммировалось для большей точности) — результат не изменился.
Tags:
Hubs:
+45
Comments 86
Comments Comments 86

Articles