Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

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

    Из 183 решений у 11 был превышен допустимый размер решения, в 19 случаях — не удалось скомпилировать (об этих ошибках подробнее ниже). Далее 47 дали неправильные ответы на простых тестах (1..1000000), 8 не успели посчитать ответ за минуту (образец решения из условия задачи для 1млн работал 5 минут 36 секунд).

    На сложных тестах — 5 решений выдали неверный ответ, и 12 — не уложились в одну минуту. 86 — успешно прошли все тесты.

    Если кто потерял, вот топик о старте соревнования с условиями задачи.


    О тестах и тестировании

    Тестировалось все банальными скриптами, самая трудоёмкая операция — сохранение руками решений из почты (и повторные имена файлов… 42 штуки main.cpp....). Это видимо один из тех случаев, когда написать web-приложение для приема решений быстрее, чем разгребать тонны почты.Результаты тестирования — складывались в MySQL, откуда строилась таблица результатов.

    Простые тесты:
    function do_test($input, $expected_output)
    {
    	global $task_id;
    	exec("echo '$input' | Solutions2/bin/$task_id &2>1", $output);
    	if(count($output)==0)return false;
    	return(strcmp($output[0], $expected_output)==0);
    }
    
    $result = do_test("10","17") && do_test("1","0") && do_test("1000","76127") && do_test("100000","454396537") && do_test("1000000","37550402023");
    


    Сложные тесты:
    Оценивалось усредненное время выполнения (т.е. время выполнения для 4-х разных входных значений, деленное на 4). 3 самых быстрых решения тестировались со 100-кратным повторением — чтобы получить более точное время работы (отличие от одиночного прогона в пределах 1%).
    $start_time = microtime (true);
    //for($i=0;$i<100;$i++)
    	$result = do_test("980000000","23783220704190493") && do_test("1051174931","27269025983026043") && do_test("891728152","19783994900202129") && do_test("761987760","14559966509022149");
    $end_time = microtime (true);
    


    Таблица результатов

    Коллеги, поднажмем на инвайты:
    Habraname Нужен ли инвайт Результат System ID
    1 @shadeware Уже нет 0.035053772330284 сек. 48
    2 @mikhaelkh Уже нет 0.039169362783432 сек. 41
    3 @Icemore Уже нет 0.068273649811745 сек. 129
    4 @ripatti
    Уже нет 0.11206769943237 сек. 8
    5 @kbxxi
    Уже нет 0.15401327610016 сек. 156
    6 @monoid Уже нет 0.22840601205826 сек. 69
    7 @Zver1992 0.23262423276901 сек. 133
    8 @Mrrl
    0.37099504470825 сек. 178
    9 @Staker Да 0.66007524728775 сек. 171
    10 @SyDr
    Да 0.93328875303268 сек. 78
    11 @vbarinov
    Да 3.2648342847824 сек. 108
    12 @vanla
    Да 3.3831697702408 сек. 19
    13 @MaSaK
    Да 3.4151287674904 сек. 20
    14 @dark1ight
    3.5476635098457 сек. 36
    15 @udalov Да 3.8905065059662 сек. 116
    16 @bklim
    4.3489827513695 сек. 149
    17 @cfighter
    4.4272682070732 сек. 11
    18 @VladVR
    4.7588297724724 сек. 89
    19 @borozdinKirill
    4.775633752346 сек. 109
    20 @ZhekSooN
    4.8941134810448 сек. 122
    21 @madkite 4.9126330018044 сек. 114
    22 @akazakow
    5.208831012249 сек. 45
    23 @mingrief 5.2523249983788 сек. 179
    24 @pasky
    5.9874464869499 сек. 5
    25 @ewnd9
    6.024626493454 сек. 183
    26 @gnhdnb
    6.0333037376404 сек. 158
    27 @through_horizon 6.2488570213318 сек. 21
    28 @kosmos89
    6.2885909676552 сек. 126
    29 @Nickel 6.36874127388 сек. 42
    30 @infsega
    6.4502172470093 сек. 33
    31 @shuternay 6.4606020450592 сек. 6
    32 @smyatkin_maxim 6.5664409995079 сек. 123
    33 @azhi 6.9450110197067 сек. 145
    34 @Valmount
    7.2953402400017 сек. 147
    35 @Alick09
    7.4088390469551 сек. 125
    36 @alexeibs 7.6391640305519 сек. 177
    37 @DoctorStein
    7.6435596942902 сек. 128
    38 @Kenny_HORROR
    7.8451775312424 сек. 77
    39 @Ratio2
    7.8529967665672 сек. 53
    40 @No username specified 8.0461687445641 сек. 80
    41 @mobi
    8.129643201828 сек. 64
    42 @Lonsdaleite
    8.2785065174103 сек. 92
    43 @tiirz 8.3757525086403 сек. 134
    44 @Goryn 8.3831282258034 сек. 167
    45 @Leronxp
    8.5381667613983 сек. 93
    46 @singstio Да 8.5835777521133 сек. 165
    47 @CTAKAH4uK
    8.7342492341995 сек. 173
    48 @XMypuK
    8.8221767544746 сек. 95
    49 @Edelweiss
    8.8413127660751 сек. 61
    50 @Jovfer
    9.6698319911957 сек. 174
    51 @crimaniak
    10.019654750824 сек. 113
    52 @luckman
    10.166677713394 сек. 46
    53 @ladilova
    10.607916533947 сек. 59
    54 @Gromilo
    11.256841778755 сек. 86
    55 @FreeCoder
    11.380919516087 сек. 44
    56 @awa
    11.482711791992 сек. 102
    57 @sprosin
    11.626729488373 сек. 76
    58 @BelerafonL
    11.740502238274 сек. 15
    59 @polar_winter
    11.798308491707 сек. 47
    60 @luckychess
    11.956114530563 сек. 143
    61 @darinflar 11.991075217724 сек. 105
    62 @kreep
    12.082272768021 сек. 170
    63 @iqmaker 12.346569001675 сек. 34
    64 @dima11221122 12.357870519161 сек. 54
    65 @kos66 12.412921786308 сек. 68
    66 @alex_r
    12.501110970974 сек. 31
    67 @dannk 12.711302280426 сек. 138
    68 @andreybotanic
    12.847037494183 сек. 40
    69 @realsugar 14.033301234245 сек. 10
    70 @kromych 14.101772785187 сек. 25
    71 @iamnp
    14.298875749111 сек. 32
    72 @skripkakos
    14.305522501469 сек. 96
    73 @OnScript
    14.555817246437 сек. 142
    74 @aserty 15.127694249153 сек. 175
    75 @ivanbl4
    15.24883300066 сек. 148
    76 @kinbote 16.56739872694 сек. 130
    77 @ryokuyou
    16.733837723732 сек. 106
    77.5 @MarvinPA 21.251857995987 сек. 186
    78 @quarck 21.369844019413 сек. 157
    79 @sultanko
    21.440900743008 сек. 172
    80 @Yura1111
    22.057671248913 сек. 30
    81 @Troyal
    22.184078454971 сек. 99
    82 @Izobara
    23.361551761627 сек. 16
    83 @PutPixel
    35.820213794708 сек. 180
    84 @CheshaNeko 53.085104465485 сек. 120
    85 @fromnull 53.490429997444 сек. 65
    86 @ronsenval
    Неверный ответ на сложных тестах 14
    87 @undiabler
    Неверный ответ на сложных тестах 26
    88 @MrDindows
    Неверный ответ на сложных тестах 52
    89 @kladov Неверный ответ на сложных тестах 66
    90 @Andrew146
    Неверный ответ на сложных тестах 127
    91 @vaux
    Превышено допустимое время на сложных тестах 22
    92 @marsencpp
    Превышено допустимое время на сложных тестах 27
    93 @phrk Превышено допустимое время на сложных тестах 43
    94 @burtsev Превышено допустимое время на сложных тестах 55
    95 @yooll
    Превышено допустимое время на сложных тестах 58
    96 @DarkContact
    Превышено допустимое время на сложных тестах 70
    97 @drongosar
    Превышено допустимое время на сложных тестах 87
    98 @alexvab
    Превышено допустимое время на сложных тестах 90
    99 @MrKonshyn
    Превышено допустимое время на сложных тестах 91
    100 @appplemac Превышено допустимое время на сложных тестах 112
    101 @msn92
    Превышено допустимое время на сложных тестах 136
    102 @ikalnitsky
    Превышено допустимое время на сложных тестах 152
    103 @0Chekhov0 Неверный ответ на простых тестах 1
    104 @savik1
    Неверный ответ на простых тестах 2
    105 @zenden2k
    Неверный ответ на простых тестах 12
    106 @alexaol Неверный ответ на простых тестах 17
    107 @Avitella Неверный ответ на простых тестах 18
    108 @yrik04
    Неверный ответ на простых тестах 24
    109 @topz
    Неверный ответ на простых тестах 35
    110 @drozdVadym
    Неверный ответ на простых тестах 37
    111 @anton280
    Неверный ответ на простых тестах 39
    112 @ehead01
    Неверный ответ на простых тестах 49
    113 @8086
    Неверный ответ на простых тестах 50
    114 @DIMKAAAAA
    Неверный ответ на простых тестах 57
    115 @mike_4d
    Неверный ответ на простых тестах 60
    116 @alineman Неверный ответ на простых тестах 74
    117 @pavor84 Неверный ответ на простых тестах 75
    118 @denzp
    Неверный ответ на простых тестах 79
    119 @RamTararam
    Неверный ответ на простых тестах 81
    120 @DezzK
    Неверный ответ на простых тестах 82
    121 @frozendog Неверный ответ на простых тестах 83
    122 @sasha237
    Неверный ответ на простых тестах 98
    123 @aX1v
    Неверный ответ на простых тестах 103
    124 @rutigl
    Неверный ответ на простых тестах 104
    125 @Joric Неверный ответ на простых тестах 107
    126 @LibertyPaul
    Неверный ответ на простых тестах 110
    127 @volokitinss
    Неверный ответ на простых тестах 111
    128 @Formicidae
    Неверный ответ на простых тестах 115
    129 @fao
    Неверный ответ на простых тестах 117
    130 @vkm
    Неверный ответ на простых тестах 124
    131 @kleninz Неверный ответ на простых тестах 131
    132 @knstqq Неверный ответ на простых тестах 135
    133 @ryokuyou
    Неверный ответ на простых тестах 139
    134 @morphing Неверный ответ на простых тестах 140
    135 @Vaddddd Неверный ответ на простых тестах 144
    136 @ancalled Неверный ответ на простых тестах 150
    137 @fasterthanlight Неверный ответ на простых тестах 154
    138 @sinc
    Неверный ответ на простых тестах 155
    139 @Satayev Неверный ответ на простых тестах 159
    140 @eversyt
    Неверный ответ на простых тестах 162
    141 @zyss
    Неверный ответ на простых тестах 163
    142 @smile616 Неверный ответ на простых тестах 166
    143 @Moress
    Неверный ответ на простых тестах 169
    144 @zzzeeerrr0
    Неверный ответ на простых тестах 176
    145 @kilotaras
    Неверный ответ на простых тестах 182
    146 @I_AM_FAKE
    Превышено допустимое время на простых тестах 7
    147 @Aksiom
    Превышено допустимое время на простых тестах 28
    148 @WarAngel_alk
    Превышено допустимое время на простых тестах 63
    149 @skovpen Превышено допустимое время на простых тестах 132
    150 @safinaskar Превышено допустимое время на простых тестах 160
    151 @No username specified Превышено допустимое время на простых тестах 168
    152 @jit_md
    Превышено допустимое время на простых тестах 181
    153 @mrigi Попытка работать с отсутствующей сетью 146
    154 @Tweekaz
    Ошибка компиляции 3
    155 @No username specified Ошибка компиляции 4
    156 @Thunderbird
    Ошибка компиляции 9
    157 @shock_one
    Ошибка компиляции 13
    158 @shy Ошибка компиляции 23
    159 @Dgut Ошибка компиляции 38
    160 @ShouldNotSeeMe
    Ошибка компиляции 56
    161 @therussianphysicist
    Ошибка компиляции 62
    162 @aamuvirkku
    Ошибка компиляции 84
    163 @IntegralUnderground
    Ошибка компиляции 85
    164 @0leksandr
    Ошибка компиляции 88
    165 @ipoder
    Ошибка компиляции 94
    166 @IharBury
    Ошибка компиляции 97
    167 @xtern
    Ошибка компиляции 100
    168 @KycokCo6aku
    Ошибка компиляции 101
    169 @gridem Ошибка компиляции 118
    170 @minc2319
    Ошибка компиляции 141
    171 @okneigres Ошибка компиляции 151
    172 @antidotcb
    Ошибка компиляции 164
    173 @merkius Превышен допустимый размер файла 71
    174 @iTwin
    Превышен допустимый размер файла 29
    175 @bstructure Превышен допустимый размер файла 153
    176 @fsv
    Превышен допустимый размер файла 51
    177 @411
    Превышен допустимый размер файла 72
    178 @pleha Превышен допустимый размер файла 67
    179 @staricam
    Превышен допустимый размер файла 73
    180 @chipa Превышен допустимый размер файла 119
    181 @dosefose Превышен допустимый размер файла 121
    182 @SergeySib
    Превышен допустимый размер файла 161
    183 @Ptax Превышен допустимый размер файла 137


    Вне конкурса

    Решения присланные после дедлайна:
    Habraname Нужен ли инвайт Результат System ID
    1 @bstructure 1.5542407631874 сек. 192
    2 @corsairnv
    12.768928468227 сек. 194
    3 @theirbaldness 15.648555219173 сек. 191
    4 @pavor84 Неверный ответ на простых тестах 189
    5 @Jamim
    Неверный ответ на простых тестах 193
    6 @1dash Ошибка компиляции 188


    Об ошибках

    Писали для MS VC: __int64 вместо long long или __int64_t, не подключен math.h, использование отсутствующего stdafx.h.
    Писали для Windows: Math.h<>math.h
    Bleeding-edge C++11 фичи: К сожалению, корректный код не всегда компилируется. У clang есть проблемы с C++11 многопоточностью (компилятор не может скомпилировать стандартную библиотеку, баг известен — я пробовал накатить патч — но не помогло). Если это не протестировать до отправки на целевом компиляторе — то проблему никак не обнаружить.
    Синтаксические ошибки: Банальная внимательность — подозреваю отправку не сохраненного файла.
    Непортируемый на 64-bit код: Попытки неявно привести указатель к int, и обратно.
    memset: undeclared identifier 'memset'; did you mean 'wmemset'? Находилось онлайн-тестом на сайте llvm. Самая популярная ошибка.
    C#: Один случай.
    Неверный формат комментария с именем пользователя: Решения все равно протестированы, чтобы мучились теперь где-чьё :-).
    Segmentation fault: Половина неверных ответов на коротких тестах — это segfault-ы и краши.

    Увидеть свои результаты компиляции можно тут (смотреть по System ID).
    Полный архив исходных текстов решений.

    Решения

    Изначально я хотел рассказать и об алгоритмах решения — но сейчас я вижу, что понятия не имею, как работают первые 2 места, потому лучше нам подождать авторов :-) Тем не менее, стоит заметить, что использование потоков не является необходимым условием для победы.

    Shadeware, победитель
    @shadeware У вас ничего не глючит, это компилируется.
    //@shadeware
    #include <cstdio>
    #include <vector>
    #include <cmath>
    unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
    "5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);} 
    Mikhaelkh, 2-е место
    @mikhaelkh Компилятор ругался на текстовую строку — но все скомпилировалось.
    //@mikhaelkh
    #include <cstdio>
    #include <bitset>
    unsigned char s[]=" 3ћfСЫБ b”Ђ)Cр —іЈ€Я $9шэD » $ѕ|Іш† %ЃЉЃмF &_яВГЕЕ 'Y¶FьВµ (nsџИp± )ќлznQ2 *иSР—ж) ,oшtе\\v -пW0BC† /«Ю#)ґ 1‚ьј”8P 3sю[Y6i 5.qЛ.“ 7¤zMЃшj 9г—‹XyЇ <_‰­XжЅ >ТOh«€Y AЃМ“«n DKr]µrЩ G.?“нU J*Ј»‚­Џ M@˜Eп†Ь PpYґпHј S№pvdјя W>дGpІш ZєQЦаЋ~ ^qяmty= bC†,щnт f.d“¤ ¤ j1Ж [|Ј nN№BўЮ: r…ЄG­рр vФiчwЁ{ {_Лз}Lh б*sЁЭ# „ћoї‹УE ‰to]¶е~ Ћd*4:иХ “kѕK8ћш ˜Њ~ќ˜QЄ ќЕЛ7д6« Ј;Ёл0ўь Ё§Iвc§б ObЗюЏP імЏxь>† №Е›»ЯPo ї·NцбЬ† ЕБ1ґgп& ЛгlъІcѓ ТAdЎ“[$ Ш–Й:ілЧ Я%юі±Ю1 е«_7бќЌ мlчnєСџ уF”ЭDРЭ ъ8ћуcћЖ $$CМжМMЕ $+gDbцPр $2ЎЧтУ‡E $9цАП†Ы ";
    enum{S=1<<14,N=1<<23};
    long long a[65],res;
    std::bitset<S> u;
    std::bitset<N> v;
    int n,r,x,i,j;
    int main() {
    	scanf("%d",&n);
    	for (i=1;i<65;++i)
    		for (++j;s[j]>32;++j)
    			a[i]=221*a[i]+s[j]-35;
    	*a=2,res=a[j=n/2/N],x=j*2*N,v[0]=!j;
    	for (i=3;i<S+S;i+=2)
    		if (!u[i/2]) {
    			for (j=i*i/2;j<S;j+=i)u[j]=1;
    			for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N;j+=i)v[j]=1;
    		}
    	for(i=1;i<=n-x;i+=2)
    		if(!v[i/2])res+=x+i;
    	printf("%lld\n", n>1?res:0);
    }
    Icemore, 3-е место, самое быстрое многопоточное решение
    @Icemore
    
    //@Icemore
    #include<iostream>
    #include<cmath>
    #include<memory.h>
    #include<pthread.h>
    #define lng long long
    const int T=4,Q=33000,S=100000;
    bool np[Q],b[T][S];
    int p[Q],c,B,s,e;
    lng A[T],R,P[]={0,1906816620981654LL,7357074544482779LL,16217881619242062LL,28422918403819825LL};
    void* f(void*_){
    	long id=(long)_;
    	int C=(e/S-B+1)/T,q,M,i,j,k;
    	M=(id==T-1)?(e/S+1):(id+1)*C+B;
    	for(k=id*C+B;k<M;++k){
    		memset(b[id],0,sizeof(bool)*S);q=k*S;
    		for(i=0;i<c;++i){
    			j=(q+p[i]-1)/p[i];j=(j>1?j:2)*p[i]-q;
    			for(;j<S;j+=p[i])b[id][j]=1;
    		}
    		if(!k)b[id][0]=b[id][1]=1;
    		for(i=std::max(0,s-q);i<S&&q+i<=e;++i)if(!b[id][i])A[id]+=q+i;
    	}
    	return 0;
    }
    int main(){
    	int n,i,q,j;
    	std::cin>>n;
    	i=(n-1)/(1<<28);s=i*(1<<28)+2;e=(i+1)*(1<<28);
    	if(n-s-1<e-n)R=P[i],e=n;else s=n+1,R=-P[i+1];
    	B=s/S;q=(int)sqrt(e+.0);p[c++]=2;
    	for(i=3;i<=q;i+=2)if(!np[i])for(j=i*i,p[c++]=i;j<=q;j+=i)np[j]=1;
     	pthread_t t[T];
    	for(i=0;i<T;++i)pthread_create(t+i,0,f,(void*)(i));
    	for(i=0;i<T;++i)pthread_join(t[i],0),R+=A[i];
    	std::cout<<(R>0?R:-R);
    } 
    
    ripatti, 4-е место
    @ripatti
    //@ripatti
    //идея - блочное решето с предпросчетом ответов для нескольких первых блоков
    #include <iostream>
    #include <memory.h>
    #define S 150000
    bool F[40000],B[S];
    int P[10000],p=0;
    long long pre[]={0,79835127420606,307011790722811,675490692294675,
    1182357709860117,1825666731904492,2603717273255596,3515373254256955,
    4559774703609068,5736228298250417,7043215380181465,8481171232603598,
    10049045128993920,11745741297705187,13571569117886223,15525668198679060,
    17608378509778587,19817357312226874,22154562782502270,24618987306923167,
    27209541722648039};
    int main(){
    	int a,b,c,n,Z=(1<<15),Q=S*350;
    	std::cin >> n;
    	long long ans=pre[n/Q];
    	for(a=2;a*a<Z;a++)if(!F[a])for(b=a*a;b<Z;b+=a)F[b]=true;
    	for(a=2;a<Z;a++)if(!F[a])P[p++]=a;
    	for(a=(n/Q)*Q;a<=n;a+=S){
    		memset(B,0,sizeof B);
    		for(b=0;b<p;b++)for(c=std::max(2,(a+P[b]-1)/P[b])*P[b]-a;c<S;c+=P[b])B[c]=true;
    		if(a==0)B[0]=B[1]=true;
    		for(b=0;b<S&&a+b<=n;b++)if(!B[b])ans+=a+b;
    	}
    	std::cout << ans;
    	return 0;
    }
    kbxxi, 5-е место
    @kbxxi
    //@kbxxi
    #include <iostream>
    long long A[]={0,72619548630277,279209790387276,614333144695291,1075207199997334,1660170771905893,2367646772295462,
    3196703482711201,4146437503168147,5215984059716389,6404774487532576,7711724083073573,9137303389808024,
    10680189372387880,12340337443955708,14116726304047228,16010026481858292,18019518580817005,20143329357815162,
    22383876593236984,24739512092254535,27209541722648039};
    char S[50000100];
    int p[50100],C,i,j,B=50000000,l,r;
    long long R=0;   
    
    int main(){    
    	std::cin >> r;   
        for (i=2;i<=100000;i++)
        if (!S[i]){
            p[C++]=i;        
            for (j=2*i;j<=100000;j+=i)
                S[j]=1;
        } else S[i]=0;    
    	l=r/B*B+1;
    	for (i=1;p[i]*p[i]<=r;i++){
            int v=p[i],P=l/v*v;        
            if (P<l) P+=v;
    		if (P==v) P+=v;
    		if (!(P&1)) P+=v;
    		v*=2;
            while (P<=r) S[P-l]=1,P+=v;        
        }
        for (i=l;i<=r;i+=2) if (!S[i-l] && i!=1) R+=i;
    	if (l==1 && r>1) R+=2;
        std::cout<<A[r/B]+R;	
    	return 0;
    }

    Singstio, самое короткое решение проходящее все тесты
    @singstio 304 байта, никакого «сжатия»
    //@singstio
    #include<iostream>
    #include<vector>
    #include<math.h>
    using namespace std;
    int main()
    {
      __int64_t n,sum=0,i,j,sn;
      cin>>n;
      sn=int(sqrt(n))+1;
      vector<bool> s(n+1,true);
      for(i=2;i<=sn;i++)
        if(s[i]){
          for(j=i*i;j<=n;j+=i)s[j]=false;}
      for(i=2;i<=n;i++)if(s[i])sum+=i;
      cout<<sum<<endl;
    } 


    Мораль

    • Сначала правильный алгоритм, потом многопоточность.
    • Перенос C++ программ на другую ОС, разрядность, компилятор — сложный и тернистый путь, тестировать на целевой платформе нужно обязательно. Вдвойне это касается bleeding-edge фич.


    О моих ошибках

    Вам кажется что у вас все работает, а в таблице — что-то неправильное?
    Рекомендую взять отправленное вами решение _из архива с решениями_, и скомпилировать на clang 3.2 64bit — и если заработает — тогда писать мне. Уже человек 10 написали, что у них все работает, а проблема всегда была или в другом компиляторе или во внимательности.

    Only registered users can participate in poll. Log in, please.

    Стоит ли организовать следующее хабра-соревнование через 3-6 месяцев, только с онлайн-приемом решений и проверкой на компилируемость не отходя от кассы?

    • 7.3%Нет уж, и так весь новый год испортил… К тому же, всегда есть USACO, TopCoder…130
    • 94.2%Пожалуй да!1681
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 141

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

        while :; do
          dd if=/dev/urandom of=file.cpp bs=1K count=1
          if clang++ file.cpp && [[ $(echo 123 | ./a.out) -eq 1591 ]]; then
            cat file.cpp; echo win
          fi
        done
        

        (=
          +1
          А break где? ;)
            0
            Где-то тут :)

            Скрытый текст
            #!/bin/bash
            i=`cat i`;
            
            compile() {
              r=$(clang++ file.cpp 2>&1| grep generated)
              if echo $r | grep -q ' 0 errors'; then
                let i++;
                echo $i > i
                cp file.cpp $i.cpp
              fi
              echo -ne "\r$r";
            }
            
            while :; do
              dd if=/dev/urandom of=file.cpp bs=1K count=1 2>/dev/null
              if compile && [[ $(echo 123 | ./a.out 2>/dev/null) -eq 1591 ]]; then
                echo win
                exit
              fi
            done
            
            0
            Перловский быстрее найдётся )
            +3
            Лучше не ждать объяснений, а самому разобраться. Тем более, что там всё просто :)
              +2
              Сори, но я немного не понял — это был сарказм, я надеюсь? Потому что если для вас понятен сорец победителя — я хочу пожать вам руку.
                0
                Нет, мне он действительно понятен. Правда, не в таких деталях, чтобы понять, зачем нужна конструкция !!~-n (которую я бы записал просто как n!=1). Хотя нет, посмотрел еще раз — и понял, это потому, что алгоритм не воспринимает 2, как простое число, и его приходится учесть отдельно. Так что в самом деле всё понятно. Непонятно только, почему он вызывает проблемы у других. Вы что, не ломали игрушки с помощью дизассемблера? Там и не такие головоломки встречались :)
                .
                  +13
                  Как я читал этот код:
                  1. Видим длинную строку. На код непохоже, вероятно, это таблица в какой-то системе счисления.
                  Смотрим на использование. Видим схему Горнера (x=x*96+"..."[i]-32) — всё правильно, основание 96, но как в одном цикле заполняется целый массив? Ага, u[i/7+2] — в течение 7 шагов это один и тот же элемент. То есть, числа 7-значные. Остроумно, примем на вооружение. Я бы оставил двойной цикл.
                  448=7*какая-то степень двойки — годится. Почему +2? Пока непонятно, оставим на потом.
                  2. Следующий цикл — разностная схема. Кодировка вторыми разностями, дело знакомое. Я иногда гладкие функции тоже так кодирую.
                  3. sqrt(n) — понятно. n>>24<<24 — знакомая конструкция, оставили старшие 8 бит. Не лучше ли n&-0x1000000? Или n&-1<<24? Автору виднее…
                  4. Опять n>>24. Почему не соптимизировано с предыдущим? Пока неважно, наверное, невыгодно. 2*!L*!!~-n… Понятно, если L==0 или… (считаю с конца) n!=1, то 2 иначе 0. Наверное, зачем-то нужно.
                  5. Ну, тут понятно. Одно решето для поиска простых, другое — для анализа нужного интервала. Детали уже неинтересны. Хотя… почему там в одном месте 2*i, а не i*i? Опять же, автору виднее…
                  В общем, всё просто. Где можно выиграть? Я бы попробовал задавать табличку как (n*n/ln(n)*какой-то коэффициент + поправка из таблицы), с шансами уложиться в 5 знаков на элемент, а на освободившихся 100 байтах попробовать устроить вычисление с шагом 30, которое раза в 2 быстрее — но лень…
                    +2
                    А я то думал что более-менее разбираюсь в С++…
                      0
                      В пункте 4, конечно, не «или», а «и».
                  +16
                  Алгоритм победителя использует метод блочного решета эратосфена с предподсчётом на 64 значения. фактически, чем больше заранее рассчитанная таблица, тем меньшего, в среднем, размера блок элементов придётся проходить и тем быстрее будет работать реализация. Предподсчёт на 64 элемента, в среднем, ускоряет блочный алгоритм рассчёта в 128(или всё же в 64?) раз(а) относительно блочного решета без предподсчёта. Вся сила решения — в умении упаковать таблицу заранее просчитанных значений вместе с кодом распаковки и досчёта в 1к исходного кода.

                  например, простое блочное решето эратосфена, которое я отправил на конкурс:
                  блочное решето
                  #define PM (1 << 16)
                  #define CZ (1 << 16)
                  
                  char c[CZ + 1];
                  int  pp[PM + 1];
                  char v[PM + 1];
                  int pc = 0;
                  
                  int64_t prime_r(int n)
                  {
                  	// first primes
                  	pc = 0;
                  	memset(pp,0x00, PM*sizeof(int));
                  	memset(v,0xff, PM*sizeof(char));
                  
                  	for(int i = 2; i*i < PM; i++) if(v[i])for(int j = i*i; j < PM; j += i)v[j] = 0;
                  	for(int i = 2; i < PM; i++)if(v[i]) pp[pc++] = i;
                  
                  	// sum of prime
                  	int64_t sum = 0;
                  	for(int64_t i = 0; pp[i] <= n && i < pc; i++)sum += pp[i];
                  
                  	for (int64_t ii = pp[pc - 1]; ii <= n; ii += CZ)
                  	{
                  		memset(c,0xff, CZ*sizeof(char));
                  		for(int64_t i = 0; i < pc; i++)
                  		{
                  			int h = ii % pp[i];
                  			int j = (h > 0) ? pp[i] - h: 0;
                  			for(; j < CZ; j += pp[i]) c[j] = 0;
                  		}
                  		int64_t si = ((ii + CZ) >= n) ? n - ii : CZ;
                  		for(int64_t i = 0; i < si; i+=2) if(c[i]) sum += (i + ii); 
                  	}
                  	return sum;
                  }
                  


                  оно же, с таблицей предподсчёта на 16 элементов, которое я так и не отправил:
                  блочное решето с предподсчётом на 16 субблоков
                  #define PM (1 << 16)
                  #define CZ (1 << 16)
                  
                  char c[CZ + 1];
                  int  pp[PM + 1];
                  char v[PM + 1];
                  int pc = 0;
                  
                  int64_t cum_16 [16] = {
                  	0,
                  	0x1c20fef2f09ca,
                  	0x6c63d57586d96,
                  	0xeec0010744a8e,
                  	0x1a233866cf59db,
                  	0x28618ac5327caa,
                  	0x399e13d0ec9c4e,
                  	0x4dd275b39fbecc,
                  	0x64fa7e62f08931,
                  	0x7f0f2d33432004,
                  	0x9c0f0b992adb2e,
                  	0xbbf49b7cf3b1fe,
                  	0xdebe8bda61ec0f,
                  	0x10467f40dc3f52f,
                  	0x12ceee2b93e7816,
                  	0x158524685365cc7
                  };
                  
                  int64_t prime_rr16(int n)
                  {
                  	// first primes
                  	pc = 0;
                  	memset(pp,0x00, PM*sizeof(int));
                  	memset(v,0xff, PM*sizeof(char));
                  
                  	for(int64_t i = 2; i*i < PM; i++) if(v[i])for(int64_t j = i*i; j < PM; j += i)v[j] = 0;
                  	for(int64_t i = 2; i < PM; i++)if(v[i]) pp[pc++] = i;
                  
                  	// sum of prime
                  	int64_t sum = 0;
                  	for(int64_t i = 0; pp[i] <= n && i < pc; i++)sum += pp[i];
                  
                  	int64_t s = (n >> 27)? (n & 0xf8000000) + 1 : pp[pc-1];
                  	if(n >> 27) sum = 0;
                  	sum += cum_16[n >> 27];
                  	for (int64_t ii = s; ii <= n; ii += CZ)
                  	{
                  		memset(c,0xff, CZ*sizeof(char));
                  		for(int64_t i = 0; i < pc; i++)
                  		{
                  			int64_t h = ii % pp[i];
                  			int64_t j = (h > 0) ? pp[i] - h: 0;
                  			for(; j < CZ; j += pp[i]) c[j] = 0;
                  		}
                  		int64_t si = ((ii + CZ) >= n) ? n - ii : CZ;
                  		for(int64_t i = 0; i < si; i+=2) if(c[i]) sum += (i + ii); 
                  	}
                  	return sum;
                  }
                  


                  Простое блочное решето, отправленное на конкурс, позволило занять 14 место. Версия с предподсчётом у меня работает, в худшем случае, ~17 раз быстрее. Что дало бы, примерно, 0,2 секунды и 7-5 место. Добавление таблицы предпросчёта до 64 значений даёт прирост примерно в 5-6 раз, что даёт примерно 0,04 — 0,034 секунды, а именно, результат победителей.

                  +5
                  разница в три порядка — это круто.
                    +3
                    Чудеса оптимизаций и предпросчетов. Мне вот интересно, много ли решений работают за рамками обозначенными заданием. Посмотреть бы, сколько чисел успеет посчитать, если ограничить временем в 60секунд, найти постепенно поднимая входное число.
                    Не знал, что блочное решето настолько быстрее обычного линейного.

                    ЗЫ большинство участников, похоже, read-only. Хороший стимул.
                    0
                    Расстроил вердикт «Ошибка компиляции», хотя всё равно в лучшем случае было бы место 80е.
                    Странно, по той ссылке, которая рекомендовалась для проверки компилируемости ошибок не было выявлено, или я чего-то не понял.
                      0
                      Видимо вы послали одно, а тестировали другое. Сообщения об ошибках компилятора лежат в архиве:

                      6_main.cpp:13:3: error: unknown type name '__int64'; did you mean '__int64_t'?
                      __int64 s=0;
                      ^~~~~~~
                      __int64_t
                      /usr/include/x86_64-linux-gnu/bits/types.h:44:25: note: '__int64_t' declared here
                      typedef signed long int __int64_t;
                      ^
                      1 error generated.
                        +2
                        да, уже разобрался

                        upd. надо было писать long long
                        и почему я написал __int64, а не __int64_t как было в примере?

                        Надо больше спать.

                        Исходник исправил, но не сохранил и прикрепил к письму.
                        В следующий раз буду внимательней.
                          +3
                          В стандартной библиотеке С есть stdint.h, в котором объявлены типы int64_t, uint64_t и т.п. для 32, 16 и 8 битов. Странно, но многие до сих пор этого не знают.
                      +2
                      А скрипт забора почты (по pop3 или imap) и сохранения вложения не быстрее ли было нагуглить, чем руками две сотни писем разгребать?
                        +4
                        Можно было конечно, но я видимо слишком недогадливый упорный
                          +2
                          упорный упоротый. Многие были уверены, что на другой стороне автоматика!!1
                        • UFO just landed and posted this here
                          +4
                          А мне интересно, что же такое замутил mrigi с «попыткой работать с отсутствующей сетью»
                            +1
                            Отправку данных на свой суперкомпьютер, стоящий в подвале?

                            Кстати да, опубликуйте! Интересно же.
                              +4
                              Может быть у него ботнет из 10000 компьютеров был подготовлен? В правилах же это никак не оговаривалось.
                              • UFO just landed and posted this here
                                  +1
                                  Исходные тексты опубликованы ( 3.14.by/files/solutions.zip ), только IP на всякий случае зацензурен. В принципе, в десятку сетевое решение mrigi попадало :-)

                                  Было еще одно решение с сетью — gribozavr -а, но он сразу написал что там сеть :-)
                                    0
                                    Дык посмотрите его решение. Оно там есть в архиве.А если кому лень смотреть, то вот оно: paste.org.ru/?mcvbey
                                    Жаль, что айпишник CENSORED. Из-за этого я не могу проверить работу этой прожки
                                      0
                                      да, я уже посмотрел и порадовался хитрости автора :)
                                    +1
                                    Вы можете использовать автоматизированную систему для проведения олимпиад по типу ACM.
                                      +14
                                      Спасибо за инвайт!

                                      Не думал, что заберусь так высоко. Наверно мне повезло с тестами (у меня не монотонно возрастает время работы с ростом n) — на худшем для меня тесте мое решение работает 0.6 с на моей машине.

                                      Суть решения описана в комментарии в самом решении. Если подробно — тупое блочное решето, вообще без оптимизаций, почти идентичное реализации с e-maxx. Всего блоков получилось порядка 7000, с шагом в 350 блоков я предпосчитал ответы. Теперь для первых 350*x блоков ответ берем из таблицы, а для оставшихся не более чем 350 блоков досчитываем блочным решетом.

                                      Все константы подобраны эмпирически.

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

                                      Мое решение можно было еще соптимизировать мелкими оптимизациями (ускорение раза в 2-3), но я особо не заморачивался. К сожалению, новый год встретил с насморком и температурой и на всякие извращения уже не было сил.
                                        +5
                                        >>C#: Один случай.
                                        Видимо, тяжелый.
                                        // 4-поточный аткинс без предподсчётов — 44 место.
                                          +2
                                          >> singstio 304 байта, никакого «сжатия»
                                          //Однопоточное решето Эратосфена — 46 место (время работы сравнимое с вашим )
                                        • UFO just landed and posted this here
                                            +12
                                            Если распечатать содержимое массива u после распаковки, то там наверняка будет что-то типа этого:

                                            ...::[ HAI THERE GUISE! ]::… === ...::[ SHADEWARE PROUDLY PRESENTS THIS SOLUTION TO HABRAHABR CHALLENGE! ]::… === ...::[ GREETZ TO:
                                              +4

                                              0
                                              8729068693022
                                              33483086021512
                                              73556704159776
                                              128615914639624
                                              198434653286059
                                              282816794399923
                                              381679805364266
                                              494848669845962
                                              622268080796348
                                              763838964861611
                                              919523465460242
                                              и.т.п.
                                                –1
                                                главное чтобы «cout
                                                  –1
                                                  хм. парсер порезал всё: 'cout
                                                    –1
                                                    ладно, nvm.
                                                +5
                                                Спасибо за новогодний контест! Было весело.

                                                Мое решение представляет собой многопоточное блочное решето Эратосфена с предподсчетом. Идея следующая — разобьем отрезок допустимых значений инпута на равные части и подсчитаем в этих точках ответ. Тогда можно искать сумму простых только в интервале от ближайшего известного числа до n (или наоборот, в зависимости от того что ближе). В блочном решете это значит что нужно обрабатывать только те блоки, которые затрагивают эту область. Простые до корня из n нам придется найти в любом случае, но это быстро.
                                                Ну и блоки обрабатываются независимо, поэтому запустим их в нескольких потоках. На моем двухъядерном ноутбуке это давало прирост скорости примерно в полтора раза.

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

                                                Более читаемое решение: http://pastebin.com/jjkpDNin
                                                  +3
                                                  Пока победитель не написал, скажу, что его решение достаточно простое и используется обычное решето с бит сетом. Другое дело, что сумма простых чисел считается от ближайшего кратного ~16млн (1<<24) числа. То есть все суммы 1, 16млн, 32млн,… загнаны в предрасчет. А уже начиная от этих предрасчитаных сум нужно найти все простые до n и их сумму. Как-то так. Мне понравилась идея.
                                                    +2
                                                    Можно еще добавить, что в массив предпосчёта записаны не суммы, а их вторые разности (что разумно, потому что сумма простых растёт примерно как n^2/og(n)), причём в 96-ричной системе.
                                                    0
                                                    Думаю, что многопоточное решение всё-таки будет быстрее: у победителя каждое значение таблицы на 64 значения занимает 7 байтов, следовательно, уменьшение таблицы в 2 раза освободит 224 байта (или 192, если кодировка значения станет занимать 8 байтов) — мне кажется этого достаточно для реализации многопоточности.

                                                    Таким образом, 2-кратное увеличение обсчитываемого интервала должно с лихвой компенсироваться 4 потоками.
                                                      0
                                                      Только сжать в 2 раза не получится. Простые числа — очень сложно ведущая себя последовательность, взять хотя бы расширенную гипотезу Римана. (Исходя из неё эта сумма будет порядка N^2/(2*ln(n)) и там будет достаточно случайный член порядка N^3/2, т.е. сжать можно максимум на 25%).
                                                        0
                                                        Наверное вы меня не поняли. Я предлагаю просто выкинуть из таблицы каждое второе значение и работать с шагом 1<<25. Это вообще не влияет на плотность упаковки вашего решения, да и у победителя гарантировано оставляет лишние 192 байтов на имплементацию многопоточности.

                                                        Да, в среднем надо будет просчитать в 2 раза больше, но зато это распределится на 4 потока, что, как мне кажется, должно улучшить среднее время.
                                                          0
                                                          Для N<10^9 суммы простых с шагом 2^24 можно закодировать, используя значения, не превышающие 10^12 (например, первые разности последовательности S(N)-0.5126*N^2/ln(N), возможно еще минус константа). Так что в 6 байт в 96-ричной системе уложиться можно (старший байт может вылезти за 127, но тогда его можно честно записать как \2??). Третьи разности S(N) тоже почти не выходят за 10^12.
                                                            0
                                                            Тогда уж лучше S(N)-N^2*x*(1+1/(1-x))/4, где x=1/ln(N).
                                                      0
                                                      Да, кстати, на intel i7 на самом деле можно выполнять 8 потоков одновременно и иметь при этом выйгрыш в производительности.
                                                      То есть ядра-то 4, но потоков 8.
                                                      Во-первых, так сказано на сайте intel.
                                                      А во-вторых, я проверял у себя на компе (у меня тоже i7), максимальная производительность на 8 потоках получается.
                                                        0
                                                        Не у всех включен гипертрединг. У меня он выключен.
                                                          0
                                                          Тогда это надо было написать в посте, в котором ты объявил конкурс. А то я 8 потоков в своём решении использовал
                                                        +9
                                                        Моя идея совпадает с этим комментом.
                                                        Только у меня 64 блока и несколько более эффективная реализация(которую, тем не менее, можно еще ускорить в несколько раз, было бы время).
                                                        Менее обфусцированный код
                                                          +7
                                                          Впечатляет. Всемогущие хабралюди разгадали мой код быстрее меня самого. И они ни в чем не ошиблись, я лишь добавлю небольшое замечание.
                                                          Я заметил, что некоторые люди писали ручные битсеты. Зачем? vector_bool вполне быстр. Когда я ради интереса заменил его на vector_char, скорость просела в несколько раз. Мораль: доверяйте STL.
                                                          Также хотелось бы поблагодарить автора конкурса за отличную задачу и современные условия.
                                                            0
                                                            А можно вас попросить поделиться кодом, генерирующим 448-байтный «стринг» из массива? :)
                                                              +1
                                                              Скрытый текст
                                                              #include <iostream>
                                                              #include <algorithm>
                                                              #include <string>
                                                              #include <iterator>
                                                              
                                                              int main()
                                                              {
                                                                 std::vector<long long> arr
                                                                 ( 
                                                                    ( std::istream_iterator<long long>(std::cin) ), 
                                                                      std::istream_iterator<long long>() 
                                                                 );
                                                                 
                                                                 for (int i = arr.size() - 1; i > 1; --i)
                                                                 {
                                                                    arr[i] -= 2 * arr[i - 1] - arr[i - 2];
                                                                 }
                                                                 
                                                                 for (auto x : arr)
                                                                 {
                                                                    std::string str;
                                                                    
                                                                    for (; x; x /= 96)
                                                                    {  
                                                                       str += char(x % 96 + 32);
                                                                       
                                                                       if ( std::string("\\\"\'").find(str.back()) != std::string::npos)
                                                                          str += '\\';
                                                                    }
                                                                       
                                                                    std::cout << std::string(str.rbegin(), str.rend());
                                                                 }
                                                              }
                                                              


                                                              Результат (на этом же сайте, я, кстати, тестировал свой код).
                                                            +1
                                                            У меня тоже решето с предподсчетом. Компилятор ругался, потому что я использовал символы с кодами больше 127. Решение старался сделать максимально прозрачным) Кстати, кто еще хочет порешать похожие задачи, но килобайта мало, есть трудная задача как раз на блочное решето: www.spoj.com/problems/PRIMES2/. Учтите, там Pentium 3!
                                                              0
                                                              как раз хотел спросить, как так удачно получилось у победителя, что в строковой константе все символы оказались «легальными»
                                                                0
                                                                уже увидел
                                                                  0
                                                                  А я не совсем понял — там удачно не оказалось кода 127, или он записан как \177 (всю строку просматривать лень). Просто в ASCII-7 есть 94 а не 95 непробельных символа, так что системе счисления следовало бы быть 95.
                                                                    0
                                                                    Символ 127 там есть, и ничего плохого от этого не случилось. Мне не важна графическая интерпретация строки, мне нужно было закодировать предподсчёт.
                                                                      0
                                                                      Строго говоря, компилятор не обязан допускать во входном коде символы за пределами extended character set. Clang ориентирован на UTF-8, поэтому на не-UTF-8 он ругается. (А мог бы и вообще ошибку кидать — и был бы прав.)
                                                                        0
                                                                        Все в пределах Extended ASCII Codes. Я компилировал перед отправкой, ошибок не было. Да, я понимаю, что это недопустимо в промышленном программировании, но эта задача имеет олимпиадный характер.
                                                                          0
                                                                          Что такое Extended ASCII Codes? (Такого понятия нет в стандарте.) Я понимаю что ошибок не было, но это добрая воля компилятора (по стандарту он мог бы и отказаться это компилировать).
                                                                            0
                                                                            Я имел в виду extended character set. К чему строгое следование стандарту в данной конкретной задаче? Согласно стандарту, компилятор много чего мог сделать, но это не значит, что он должен по-умолчанию придираться ко всему подряд.
                                                                              0
                                                                              Некорректных UTF-8 последовательностей нет в extended character set, в том-то и дело. На корректный UTF-8 Clang не выдаёт предупреждений.

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

                                                                              К чему ещё в вашей программе можно «придраться»?
                                                                              0
                                                                              Инициализации целочисленных переменных нулём по умолчанию тоже нет в стандарте, всем участникам повезло :)
                                                                                +1
                                                                                Вы правы! Я вчера прогнал топовые решения под AddressSanitizer, Undefined Behavior Sanitizer — ничего не нашёл и совсем забыл про Memory Sanitizer. Как оказалось, зря — там всё плохо.

                                                                                В решениях bklim, dark1ight, Icemore, madkite, MaSaK, Mrrl, ripatti, udalov, vbarinov, VladVR, ZhekSooN есть использование значений неинициализированных переменных.
                                                                                  0
                                                                                  Что такое UTF-8 последовательность? Clang поругался только на 2 символа, что в них особенного? При ограничении в 1024 байта естественно ожидать от участников экономии кода исходя из предположений, которые при данных ключах компиляции почти всегда верны. Да, я согласен, что предупреждения игнорировать не стоит, но в данной задаче это не критично. Лучше поищите логические ошибки в программах, это сложнее и увлекательнее, так как тестов было мало, наверняка они есть.
                                                                                    0
                                                                                    Clang ругался на две строчки, со многими символами в каждой. pastebin.com/t7L3q67H — он подчёркивает всё, что не UTF-8.

                                                                                    Термин «UTF-8 последовательность» — согласно спецификации Unicode (в версии 6.2 это определение D86 в главе 3).
                                                                                    +2
                                                                                    Всмысле? Ткните мне переменную, которая используется без инициализации.

                                                                                    Глобальные переменные по умолчанию инициализируются нулями. Из стандарта:

                                                                                    «Objects with static storage duration (3.7.1) shall be zero-initialized (8.5) before any other initialization takes place.»

                                                                                    В остальных переменных, конечно же, по умолчанию мусор. Однако каждой из этих переменных всегда присваивается не мусорное значение до того, как значение этой переменной будет где либо использовано. Или так делать нельзя? Если да, то почему?
                                                                                      0
                                                                                      Я сильно извиняюсь, совсем забыл что для MemorySanitizer нужно использовать инструментированную стандартую библиотеку C++, а я использовал обычную — отсюда ложное срабатывание (считалось что n не инициализирована, но она инициализируется кодом в стандартной библиотеке во время чтения из cin). Перпроверил — в вашей программе всё ОК, остальные не перепроверял.
                                                                                      +1
                                                                                      А где это в моём решении «использование значений неинициализированных переменных»? Просто любопытно. Я думаю, передачу указателя в scanf Вы не считаете таковым использованием? ;)
                                                                                      Все остальные переменные у меня инициализируются, а память под массив выделяется с помощью calloc (который по man-у инициализирует память нулями).
                                                                                        0
                                                                                        Извините, я использовал неправильную стандартную библиотеку и получил ложные срабатывания: habrahabr.ru/post/164567/#comment_5668261

                                                                                        Перепроверил ваше решение — всё ОК.
                                                                    +30
                                                                    Я бухал и все пропустил ((
                                                                      +5
                                                                      всё правильно сделал! :)
                                                                      0
                                                                      Странно, почему никто не спрашивает:
                                                                      К чему эти пляски с Clang, чем вас не устроил более распространенный (и быстрый) gcc?

                                                                      Зачем нужны искусственные ограничения на размер решения? Видимо, раз задача при искусственных же ограничениях на тесты сводится к предподсчету, то она не очень удачна для соревнования по алгоритмам. Победителям пришлось прогонять код через обфускатор — это как бы намекает.
                                                                        +3
                                                                        Если бы не было ограничения на 1024 байта, то решения были бы более сложными, замысловатыми, использовали бы больше оптимизаций и пр. Тогда бы открывался бы ещё больший простор для предподсчёта. Было бы разумно использовать всякие сложные алгоритмы. В общем, задача была бы мега-сложная, пришлось бы кодить 5 часов, а то и все 24, чтобы можно было дать конкурентноспособное решение.

                                                                        В общем, в этом конкурсе вся суть в том, чтобы написать решение так, чтоб оно было коротким. А то можно было бы, скажем, копирнуть какую-нибудь профессиональную программу. Например, статья на вики про решето Аткина ссылается на домашнюю страницу второго автора этого решета (Бернштейна). Там лежит его собственная реализация алгоритма: cr.yp.to/primegen.html. Какой-нибудь хабравчанин мог бы просто копирнуть эту прожку.
                                                                          –1
                                                                          Мне кажется лучше подошла бы задача на строки (может даже онлайновая), или графы, или запросы на отрезке (поле для оптимизации структуры). В таких задачах предподсчет вряд ли возможен.

                                                                          Чтобы люди не убивались 24 часа, можно заранее объявить время публикации условий и закрыть прием решений через 3-5 часов. Как, собственно, давно и делают онлайн-площадки соревнований по программированию.
                                                                            +2
                                                                            Так и не нужно было убиваться 24 часа, сели, за час написали — и дальше праздновать :-)
                                                                            А насчет clang — за ним будущее, да и полезно вспомнить что компиляторы бывают разные.
                                                                              0
                                                                              Победители потратили явно не час. Поэтому чтобы люди писали час, надо и ограничение такое поставить.
                                                                                0
                                                                                Я думаю у них нужно спросить, сколько они потратили )
                                                                                  +1
                                                                                  И никто не мешает иметь домашние заготовки. Задача поиска всех простых чисел на интервале довольно часто встречается в олимпиадном программировании. Я думаю, в той или иной формулировки top таблицы с этой задачей уже сталкивался.
                                                                                    0
                                                                                    Я потратил все 24 часа (с учётом около 8-часового сна, еды и пр.). Я думаю, 4 часа точно кодил.
                                                                                  –1
                                                                                  Я думаю, будущее не за clang. Всё-таки, gcc — это стандарт в мире свободного ПО и мире бизнеса. Никто не станет просто так пересаживаться на clang.
                                                                                    +1
                                                                                    Диванные аналитики в треде?

                                                                                    В FreeBSD уже ушли с GCC, Debian на подходе.
                                                                                      0
                                                                                      У gcc древний и сложный C код, в нем разобраться сложно.
                                                                                      А clang написан с нуля на C++ и сразу «по хорошему», потому на него все и переходят.
                                                                              +3
                                                                              Без ограничений на размер решения была бы жесть! Можно написать решение за ~N^0.5 с предподсчетом за ~N(асимптотики с точностью до логарифмов). И тогда отделить решения было бы очень трудно. Я ничего не обфусцировал, и если бы написал цикл в 19 строчке не до N, а до (n-x+1)/2, то скорее всего, выиграл бы.
                                                                                +5
                                                                                Без ограничения размера я бы выиграл. У меня таблица 10^9 готовых ответов.
                                                                                  0
                                                                                  Пока вы будете заполнять таблицу в памяти или обращаться к жесткому диску, я давно уже ответ посчитаю. Мне нужно меньше 1ms времени и 1MB памяти на тест.
                                                                                +2
                                                                                Спасибо за инвайт! (я на 6 месте в таблице).

                                                                                Ох, похоже, что моё решение — самое быстрое из тех, что не использует предпросчёт (хех, пока тут не сказали, я и не догадывался, за счёт чего меня обходят более чем в четыре раза). Особой магии у меня нет, всё то же блочное решето, распараллеленное на 4 потока, каждый поток обрабатывает один из возможных остатков по модулю 12 (1, 5, 7, 11). Похоже, можно было ускорить ещё раза в полтора, взяв 8 потоков и простые остатки по модулю 30.
                                                                                  +5
                                                                                  Захотел провести альтернативное тестирование (среди первых 21). На тех же самых тестах, используя ту же самую методику запуска, проверки и измерения времени (на php). Вот такая тестирующая машинка:
                                                                                  $ uname -a
                                                                                  Linux moon 3.6.10-1-ARCH #1 SMP PREEMPT Tue Dec 11 09:40:17 CET 2012 x86_64 GNU/Linux
                                                                                  $ clang -v
                                                                                  clang version 3.2 (tags/RELEASE_32/final)
                                                                                  Target: x86_64-unknown-linux-gnu
                                                                                  Thread model: posix
                                                                                  $ cat /proc/cpuinfo | grep -F 'model name' | head -1
                                                                                  model name: AMD FX(tm)-6100 Six-Core Processor

                                                                                  Видим, что всё то же самое (linux x64 и clang 3.2), только процессор немного другой фирмы.

                                                                                  Получил я такие результаты (последнее число — суммарное время по 4-м тестам):
                                                                                  1 shadeware 0.20930314064026
                                                                                  2 mikhaelkh 0.25842094421387
                                                                                  3 kbxxi 0.65344190597534
                                                                                  4 ripatti 0.80067110061646
                                                                                  5 Icemore 0.82941699028015
                                                                                  6 Zver1992 1.9382400512695
                                                                                  7 monoid 2.2213151454926
                                                                                  8 Mrrl 3.3820571899414
                                                                                  9 Staker 3.9848639965057
                                                                                  10 SyDr 4.081221818924
                                                                                  11 madkite 16.979673147202
                                                                                  12 udalov 20.033820152283
                                                                                  13 bklim 21.501169919968
                                                                                  14 cfighter 22.276267766953
                                                                                  15 vanla 23.618012905121
                                                                                  16 ZhekSooN 24.388655185699
                                                                                  17 MaSaK 24.595273017883
                                                                                  18 VladVR 25.226194143295
                                                                                  19 dark1ight 26.574873924255
                                                                                  20 vbarinov 26.777559995651
                                                                                  21 borozdinKirill 33.735852956772


                                                                                  Не ожидал, что результаты будут настолько отличаться. Хотя первые два решения остались на местах.
                                                                                  Повторные запуски дают ту же картину.
                                                                                  Если кто хочет проверить у себя (а интересно посмотреть на результаты, полученные на других процессорах), то вот архив с решениями и тестирующими скриптами, которые я использовал. Там просто запустить ./test.sh (в linux x64, разумеется). В случае проблем попробовать перекомпилить с помощью ./compile.sh
                                                                                    +3
                                                                                    Вот что кеш животворящий делает :-)

                                                                                    Также полагаю влияет и то, что ваш процессор состоит из 3-х пар ядер — оптимизация многопоточных приложений должна быть другая, что и продемонстрировало ухудшение времени работы многопоточного решения от icemore.
                                                                                      +1
                                                                                      Мне кажется, что дело ещё в скорости RAM. Забыл сказать, что у меня 1866MHz (на i7 у Вас максимум 1600MHz). Но зато, как Вы заметили, кэша меньше. В итоге моё решение (обычное решето, где кэш почти не используется, а скорость памяти очень важна) «поднялось» с 21-го до 11-го, обойдя решения с блочным решетом (где не так активно гуляют по памяти, а больше по кэшу).
                                                                                        +1
                                                                                        Да, на 8-и планках высоких частот достигать трудно. У меня вообще номинал, 1333.
                                                                                    +3
                                                                                    Смотря на коды первых 2-х мест, так и хочется сказать авторам — «Вы ЗВЕРИ!»
                                                                                      +4
                                                                                      Хочется порадоваться, что еще есть люди, способные на такое.
                                                                                        –2
                                                                                        Главное, чтобы в коде для продакшна такого не было.
                                                                                          +4
                                                                                          Если его эквивалент будет в микропроцессоре, где всего 1 килобайт ПЗУ — то чем это плохо?
                                                                                            +2
                                                                                            Мне больше представляется ситуация, когда такой код достается кому-то в «наследство» и его нужно как-то поддерживать и модифицировать.

                                                                                            Та и даже самому автору нужно будет через полгода-год вспоминать что же это такое и как оно вообще работает, если это нигде не задокументировано.
                                                                                              +1
                                                                                              Достаточно задокументировать входы-выходы и написать эквивалентный неэффективный фрагмент. Поменять что-то в сверхоптимизированном коде в любом случае было бы затруднительно (даже автору), пришлось бы восстанавливать его заново, используя приёмы из старого кода в качестве подсказок.
                                                                                      +2
                                                                                      Не хочу открывать холиварный коммент, однако хочется сказать: на таких вот примерах можно показать, для чего нужна алгоритмистика в программировании. А то некоторые люди считают, что если есть пузырьковая сортировка, то про qsort можно уже не знать, не говоря уже про какой-нибудь radix sort.
                                                                                        +1
                                                                                        По мне, так это как раз не очень показательный пример :) Многие скажут: «Как мне это пригодиться на практике?», т.к. вряд ли большинство программистов сталкивается с реализацией теоретико-числовых алгоритмов (за исключением людей, которые занимаются криптографией). Гораздо лучше смотрелась бы задачка на нестандартную структуру данных.
                                                                                        А вообще, программирование — частный случай алгоритмистики, которая, в свою очередь, частный случай дискретной математики.
                                                                                          +1
                                                                                          Так тут практики гораздо больше чем кажеться — на непортабельном C++ коде срезалось участников больше, чем с неправильным алгоритмом.
                                                                                            +1
                                                                                            Я думаю, задайте вы A+B Problem, срезалось бы не меньше :) А если ещё компилить каким нибудь Sun c++ под Sun OS, так вообще страшно представить.
                                                                                            +1
                                                                                            Ну, я больше говорил про «алгоритмистику в общем».
                                                                                            Если, например, писать высоконагруженный игровой сервер, работающий в режиме критической многопоточности, разница 0.025 с. или 25 с. на какой-то операции может означать, будет сервер держать 10 или 1000 одновременных активных игроков. А это фактически будет означать, сможет ли проект жить (геймплей тут не беру в расчет).
                                                                                            Привел такой пример, т.к. знаю не еденичный случай, когда из-за того, что серверные разработчики забыли про теорию графов, хоронился проект, а иногда и игровая студия вместе с ним. Какие были убытки уж вообще молчу…
                                                                                              0
                                                                                              Да, это же теория графов, она частенько бывает полезна. Ее даже можно назвать теоретическим минимумом для программиста. Я же говорю про теоретико-числовые алгоритмы, которые вообще непонятно как применять на практике. Можно решать только специально выдуманные задачи, т.е. «задача ради задачи».
                                                                                              Ну а в целом я с вами согласен, алгоритмы нужно знать и уметь применять.
                                                                                                0
                                                                                                Действительно, задачи, связанные с простыми числами, почти не встречаются (если не рассматривать криптографию). Мне они попадались либо когда были нужны точные вычисления (особенно, гарантированное сравнение с нулём — например, метод Гаусса или базис Грёбнера, ведомые многомодульной арифметикой — ну, или многомодульная арифметика сама по себе), либо когда структура конечного поля была удобна для задания какого-то графа (фрагмент решетки на плоскости Лобачевского).
                                                                                                Но это в production коде. При разработке (поиск подходящих параметров, конфигураций и т.п.) они встречаются чаще, но там важнее их быстро и правильно написать, чем добиваться эффективности.
                                                                                                На практике поиск простого числа ещё используется при реализации Hashtable в .NET…
                                                                                          +9
                                                                                          Считайте меня занудой, но повторю свою мысль из стартового топика:

                                                                                          Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.

                                                                                          Я сам поленился участвовать, да и смотря на код победителей понимаю, что не мог бы рассчитывать на высокие места. Но мне всё равно хочется, чтобы победитель определялся на основании более обширных тестов, исключающих случайность. И хотя я уверен, что 1-2 места в любом случае останутся за shadeware и mikhaelkh (респект!!!), их же код, но с более плотной таблицей в верхней четвети диапазона был бы наверняка ещё быстрее на данных тестах, немотря на «провал» в области непосредственно перед таблицей.

                                                                                          Среднее время ТОП-3 менее 0.1 с — гораздо более показательными были бы 1000 и даже 10000 тестов на разных(!) значениях.

                                                                                          Также мне был бы интереснен рэнкинг «по худшему времени» — после обфускации большинство решений легко укладываются в 1024 байта, и для дальнейшего ускорения используют таблицу предварительно вычисленных значений. Это значит, что худшее время программы не так просто найти (хотя и не так сложно, учитывая небольшое число возможных локальных максимумов). Но на мой взгляд этот рэнкинг очень показательный.
                                                                                            0
                                                                                            Оценивать скорость программы по 4 тестовым числам — недостаточно. Легко может победить программа с более плохим «основным кодом», но с более удачным выбором значений таблицы.

                                                                                            Ну, вообщем, так и случилось. BarsMonster должен был рассказать про способ оценивания решения подробнее в своем предыдущем посте. Я думал, что нужно минимизировать худшее время работы, как это обычно надо в олимпиадном программировании. У меня код во многом похож с shadeware, тоже предподсчет 64 значений но, в отличии от него есть оптимизация, выкидывающая все четные числа. Я все время считал весь массив, и это стоило мне 1 места, так как в тестах в среднем надо было посчитать 0.41 массива, как результат — мой код на 12% медленнее. Если бы я написал цикл в 19 строчке не до N, а до (n-x+1)/2, то программа заработала в 2 раза быстрее.
                                                                                              0
                                                                                              Значит все как в жизни — помимо корректной реализации нужны еще и верные предположения :-)
                                                                                                0
                                                                                                Помню на республиканской олимпиаде был случай — задача была про деньги, и нужно было предположить, что использовать нужно было только купюры имеющие хождение в стране (в условии этого было не сказано).

                                                                                                Драмы было очень много
                                                                                                +1
                                                                                                Кстати, вы не думали распределять таблицу не равномерно?
                                                                                                Ведь просеивание последних блоков занимает больше времени (число проходов растёт O(sqrt(N) / ln(N))).

                                                                                                Заодно и количество значений может быть любым, а не только степенью 2, позволяя использовать практически каждый свободный байт.
                                                                                                  0
                                                                                                  Да, у меня были далеко не идеальные оптимизации. По правде говоря, я вообще не ожидал, что выиграю.
                                                                                                  Я стремился к чему-то такому.
                                                                                                  Скрытый текст
                                                                                                  //@shadeware
                                                                                                  #include <cstdio>
                                                                                                  #include <vector>
                                                                                                  #include <cmath>
                                                                                                  #include <cstdlib>
                                                                                                  
                                                                                                  int main()
                                                                                                  {
                                                                                                  	//especially for
                                                                                                  	http://habrahabr.ru
                                                                                                  
                                                                                                  	//расшифровка предподсчета
                                                                                                  	
                                                                                                  	long long precalc[66] = {};
                                                                                                  	
                                                                                                  	for (int i = 0; i < 64 * 7; i++)
                                                                                                  	{
                                                                                                  		precalc[i / 7 + 2] = precalc[i / 7 + 2] * 96 + "+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL05Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i] - 32;
                                                                                                  	}
                                                                                                  	
                                                                                                  	for (int i = 0; i < 64; i++)
                                                                                                  	{
                                                                                                  		precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
                                                                                                  	}
                                                                                                  
                                                                                                  	int n;
                                                                                                  	scanf("%d", &n);
                                                                                                  
                                                                                                  	long long answer;
                                                                                                  	int left;
                                                                                                  
                                                                                                  	if (n & (1 << 23) ) //n ближе к правой границе блока
                                                                                                  	{
                                                                                                  		answer = -precalc[(n >> 24) + 2];
                                                                                                  		//так как answer отрицательный, модуль числа будет уменьшатся
                                                                                                  		//при сложении, следовательно, основной код не изменится.
                                                                                                  		
                                                                                                  		left =  (n >> 24 << 24) + (1 << 24);
                                                                                                  		std::swap(left, n);
                                                                                                  		++left;
                                                                                                  	}
                                                                                                  	else //n ближе к левой границе
                                                                                                  	{
                                                                                                  		left = n >> 24 << 24;
                                                                                                  
                                                                                                  		if (left == 0)
                                                                                                  		{
                                                                                                  			answer = 2 * (n > 1);
                                                                                                  		}
                                                                                                  		else
                                                                                                  		{
                                                                                                  			answer = precalc[(n >> 24) + 1];
                                                                                                  		}
                                                                                                  
                                                                                                  	}
                                                                                                  
                                                                                                  	int sq = sqrt(n) + 1e-7;
                                                                                                  	
                                                                                                  	//уменьшаем в 2 раза все переменные, так как четные числа учитываться не будут 
                                                                                                  	
                                                                                                  	n = (n - 1) / 2;
                                                                                                  	left /= 2;
                                                                                                  	sq /= 2;
                                                                                                  
                                                                                                  	std::vector<bool> sieve(sq + 1), block(n - left + 1);
                                                                                                  	block[0] = !left;
                                                                                                  
                                                                                                  	//блочное решето
                                                                                                  	for (int i = 1; i <= sq; ++i)
                                                                                                  	{	
                                                                                                  		if (!sieve[i])
                                                                                                  		{
                                                                                                  			//просеивание до корня
                                                                                                  			
                                                                                                  			//так как i уменьшено в 2 раза, то исходное i = 2 * i + 1
                                                                                                  			//i * i -> 2 * i * (i + 1)
                                                                                                  			for (int j = 2 * i * (i + 1); j <= sq; j += 2 * i + 1)
                                                                                                  			{
                                                                                                  				sieve[j] = 1;
                                                                                                  			}
                                                                                                  
                                                                                                  			//просеивание блока
                                                                                                  
                                                                                                  			int j;
                                                                                                  			
                                                                                                  			//вычисление левой границы, от которой будем просеивать
                                                                                                  			if (left == 0)
                                                                                                  			{
                                                                                                  				j = 2 * i * (i + 1);
                                                                                                  			}
                                                                                                  			else
                                                                                                  			{	
                                                                                                  				//находим первое j, которое кратно i && >= left
                                                                                                  				j = 2 * (left + i);
                                                                                                  				j -= j % (2 * i + 1);
                                                                                                  
                                                                                                  				//просеивать четные числа ни к чему, они будут пропускаться
                                                                                                  				if (j % 2 == 0)
                                                                                                  				{
                                                                                                  					j += 2 * i + 1;
                                                                                                  				}
                                                                                                  								
                                                                                                  				j /= 2;
                                                                                                  			}
                                                                                                  
                                                                                                  			for (; j <= n; j += 2 * i + 1)
                                                                                                  			{
                                                                                                  				block[j - left] = 1;
                                                                                                  			}
                                                                                                  		}
                                                                                                  	}
                                                                                                  	
                                                                                                  	//подсчет ответа
                                                                                                  	for (int i = 0; i <= n - left; ++i)
                                                                                                  	{
                                                                                                  		if (!block[i])
                                                                                                  		{
                                                                                                  			answer += i * 2 + left * 2 + 1;
                                                                                                  		}
                                                                                                  	}
                                                                                                  	
                                                                                                  	printf("%lld", std::llabs(answer));
                                                                                                  }
                                                                                                  


                                                                                                  Данный код работает в худшем случае в ~3 раза быстрее, чем то, что я послал на конкурс. Среднее же время вообще стремится к нулю. И исходник все еще можно обфусцировать до 1024 байт(изменилось не так уж и много).
                                                                                                    0
                                                                                                    2-кратное изменение понятно, а дальше за счёт чего? Из-за вдвое меньшей используемой памяти?

                                                                                                    Кстати, для относительно небольших N, можно «подбирать» корень — это дольше, но пренебрежимо мало по сранвению с остальным кодом. Зато позволяет сэкономить место.
                                                                                                    for(;++q*q<n;);
                                                                                                    

                                                                                                    вместо
                                                                                                    #include <cmath>
                                                                                                    q=sqrt(n)+1e-7;
                                                                                                    
                                                                                                      0
                                                                                                      Из-за вдвое меньшей используемой памяти?

                                                                                                      В том числе. Это позволяет переписать циклы, чтобы счетчик инкрементился, а не увеличивался на два. Ну и еще компилятор лучше оптимизирует такие циклы.
                                                                                                      Также при просеивании теперь пропускаются четные значения, и само просеивание начинается с i * i (вместо 2-3 * i).
                                                                                                      ++q*q<n

                                                                                                      Это же undefined behavior :)
                                                                                                      Я знаю про это, но недостатка в байтах не было. К тому же, нужно как-то найти размер для решета(n / 2 — некошерно).
                                                                                                        0
                                                                                                        Ну хорошо, забирайте ваш байт: :)

                                                                                                        for(;q*q<n;++q);
                                                                                                        


                                                                                                        Ещё может быть можно выцарапать пару байтов заменив

                                                                                                        	for (int i = 0; i < 64; i++)
                                                                                                        	{
                                                                                                        		precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
                                                                                                        	}
                                                                                                        


                                                                                                        на

                                                                                                        	for (int i = 0; i < n>>24; i++)
                                                                                                        	{
                                                                                                        		answer = precalc[i + 2] += 2 * precalc[i + 1] - precalc[i];
                                                                                                        	}
                                                                                                        


                                                                                                        * Я не придираюсь — наоборот, ваше решение кажется мне настолько близким к совершенству, что не могу удержаться от попыток довести его до абсолюта :)
                                                                                                          0
                                                                                                          A, ещё я не понял, зачем в «стринге» использовать \' вместо '.
                                                                                                            0
                                                                                                            Из той же оперы — в 13M.MfL0" "5Q2Oz50fxnC зачем нужны двойные кавычки? Или в clang-е есть ограничение на максимальную длину строкового литерала?
                                                                                                              0
                                                                                                              Возможно это «редакторская» правка — чтобы решение влезало в экран.
                                                                                                        0
                                                                                                        0.018682479858398 секунды ;-)
                                                                                                          0
                                                                                                          BarsMonster А у меня на измененном коде сколько? В 19 строчке N заменить на n-x+1>>1
                                                                                                            0
                                                                                                            Ответ неправильный получается:

                                                                                                            px@px-VirtualBox:/var/process/Solutions2/bin$ ./202
                                                                                                            980000000
                                                                                                            24528412653250953


                                                                                                            for (j=(x?((r=i-x%i)&1?r:r+i):i*i)/2;j<N-x+1>>1;j+=i)v[j]=1;
                                                                                                              0
                                                                                                              Там не N, а n. Я ещё отправил правильную версию по почте)
                                                                                                                0
                                                                                                                0.02280980348587 секунд
                                                                                                    0
                                                                                                    Там не N, а n.
                                                                                                      0
                                                                                                      Решение в 165 байт, по времени укладывается.
                                                                                                      Можно сэкономить 4 байта, пожертвовав 7-ю гигабайтами.

                                                                                                      #include<iostream>
                                                                                                      char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(!p[i])for(j=i*i;j<=n;j+=i)p[j]=1;for(;n-->2;)s+=p[n]?0:n;std::cout<<s;}
                                                                                                      
                                                                                                        0
                                                                                                        164
                                                                                                        #include<iostream>
                                                                                                        char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(j=!p[i])for(;j++*i<=n;)p[j*i]=1;for(;n-->2;)s+=p[n]?0:n;std::cout<<s;}
                                                                                                        
                                                                                                          +1
                                                                                                          при n=2 ответ 2, у тебя 0. Ещё SIGSEGV при n = 1<<30.
                                                                                                            0
                                                                                                            Пофиксил, и теперь
                                                                                                            163
                                                                                                            #include<iostream>
                                                                                                            char p[1<<30];long long n,s,i=1,j;int main(){std::cin>>n;for(;++i<4e4;)if(j=!p[i])for(;++j*i<=n;)p[j*i]=1;for(;n;)s+=!p[n]*n--;std::cout<<s-1;}
                                                                                                            

                                                                                                            Я не очень знаю Си, вроде бы s+=!p[n]*n--; — это не случай неопределённого поведения, и всё ок т.к. приоритет [] выше, чем --?
                                                                                                              +1
                                                                                                              Это UB, приоритеты тут не при чём.
                                                                                                                –1
                                                                                                                Там нет UB. Выражения s+=!p[n]*n--; и s+=!p[n]*n;n--; будут равнозначными.
                                                                                                                  +1
                                                                                                                  C11, 6.5 p2
                                                                                                                  If a side effect on a scalar object is unsequenced relative to either a different side effect
                                                                                                                  on the same scalar object or a value computation using the value of the same scalar
                                                                                                                  object, the behavior is undefined.

                                                                                                                    –1
                                                                                                                    IMHO, ключевое is unsequenced может возникнуть в этом выражении s+=!p[n]*n-- только если определен, например, operator* — для параметров функции не определен порядок.
                                                                                                                      0
                                                                                                                      Признаю, вы правы, учитывая следующее
                                                                                                                      Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.

                                                                                                                      так и не удалось найти те самые исключения «Except where noted»
                                                                                                                        +1
                                                                                                                        Порядок гарантируется в операциях a&&b, a||b, a?b:c и «запятая».
                                                                                                                  0
                                                                                                                  std::cin>>n можно внести внутрь for
                                                                                                                    0
                                                                                                                    И, раз памяти не жалко, вместо 1<<30 использовать 2е9
                                                                                                                      0
                                                                                                                      [] и постфиксный — имеют одинаковый приоритет.
                                                                                                                  0
                                                                                                                  long long не нужен, достаточно просто long.

                                                                                                                  На linux-x86_64 используется модель LP64, где long 64-разрядный, в отличие от LLP64 в Windows x64, где long — 32 бита, а long long — 64 бита.
                                                                                                                  0
                                                                                                                  Я правильно понимаю, что единицу не стоит считать как простое число?
                                                                                                                  +1
                                                                                                                  Еще задачи на решето:
                                                                                                                  easy:
                                                                                                                  www.spoj.com/problems/TDPRIMES/
                                                                                                                  www.spoj.com/problems/TDKPRIME/
                                                                                                                  hard:
                                                                                                                  www.spoj.com/problems/PRIMES2/
                                                                                                                  www.spoj.com/problems/KPRIMES2/
                                                                                                                  Учтите, там Pentium 3, в 8 раз медленнее моего Core 2 Duo. Мои решения hard задач работают ~3 раза быстрее TL.
                                                                                                                  Кто заинтересовался, советую почитать:
                                                                                                                  code.google.com/p/primesieve/

                                                                                                                  Only users with full accounts can post comments. Log in, please.