Счастливые билеты

    Уже больше недели хожу пешком и катаюсь на общественном транспорте, проездные билеты не продают после 5-го числа, поэтому приходится каждый раз при посадке оплачивать проезд. А что чаще всего делают школьники и студенты (а часто даже взрослые люди, каждый день наблюдаю) с билетом первым делом? Проверяют его на принадлежность к так называемым «счастливым», чтобы потом положить к себе в коллекцию, а может даже «по-тихому» съесть для верности. А может просто выкинуть :)

    Счастливые билеты

    В любом случае, это какое-никакое развлечение и повод для радости. И что-то детство в одном месте у меня заиграло, стало интересно, какова вероятность получить «счастливый» билет? Сколько всего «счастливых» билетов?

    Помню, что в школе даже кто-то делал исследовательскую работу (или что-то в этом роде, не суть), мы пытались выводить формулы, рисовать графики и прочее.

    Но, поскольку мощность наших компьютеров зачастую позволяет идти неоптимальным путем (с точки зрения математики), то решил не заморачиваться выводом формул.

    В итоге оказалось быстрее :)
    Привык программировать на Perl. Большинство здравомыслящих программистов, думаю, легко повторят тоже самое за несколько минут хоть на Delphi, хоть на Basic, хоть на JavaScript, etc.
    Программа просто перебирает практически миллион комбинаций (989к, первый счастливый билет 1001).

    #!/usr/bin/perl

    print "Content-Type: text/html\n\n";

    $num = 1000;
    $s = 0;

    while ($num < 1000000) {

      $ln = length($num);

      $l6 = substr($num,$ln-6,1) if ($ln > 5);
      $l5 = substr($num,$ln-5,1) if ($ln > 4);
      $l4 = substr($num,$ln-4,1);
      $l3 = substr($num,$ln-3,1);
      $l2 = substr($num,$ln-2,1);
      $l1 = substr($num,$ln-1,1);

      if ($l6+$l5+$l4 eq $l3+$l2+$l1) {
         print 0 x (6-$ln), "$num\n";
         $s++;
      }

      $num++;

    }

    print "Сумма = $s";


    * This source code was highlighted with Source Code Highlighter.


    В итоге на выходе я получил сумму, равную 55251 счастливому билету.
    Чуть округляя, получаем, что примерно каждый 18-й билет «счастливый».

    Уже из интереса решил поискать математическое решение, и нашел весьма интересный рассказ, рекомендую почитать, если хотите немного отвлечься на 10-15 минут от работы, достаточно интересно. На этой же странице еще много интересного про счастливые билеты.

    А на Википедии можно посмотреть краткую вытяжку, там хорошо и коротко показано распределение «счастливых» билетов.

    Как и в Википедии, так и в рассказе указано число 55252. В момент написания топика думал, что билета с номером 000000 не существует. В комментарии приведено доказательство существования такого билета.

    Что я хотел всем этим сказать? Да, собственно, ничего особенного. Если нужно расслабиться во время рабочего дня — можно найти массу интересных (кроме игр) и полезных для умственной деятельности вещей.

    Будьте счастливы!

    UPD: Посчитал количество билетов типа «встреча» (суммы отличаются на единицу) и «письмо» (отличаются на 2). «Встреча» — 109494 билетов, «письмо» — 106524 билетов. В итоге примерно каждый 4-ый билет привносит немного позитива в нашу жизнь :)
    Поделиться публикацией
    Комментарии 141
      +6
      Прочитал про билетики и вспомнил классную статью «Полезные Билетики» от XaocCPS

        0
        почему-то все меня идиотом считают, когда я в трамвае считаю числа...)
          0
          Особенно когда в «сотню» играешь. Думают, наверное, каким имбецилом надо быть, чтобы что-то подсчитывать 15 минут в автобусном билете.
            0
            Именно в них))
            +1
            А как вы определяете, что вас посчитали идиотом, если не секрет? :)
              0
              По взгядам и отзывам знакомых))
          +5
          Я как-то рассчитывал методом рекурсии ряд Фиббоначчи (где последующий член равен сумме двух предыдущих). Был очень удивлён, обнаружив следующий феномен: при расчёте членов ряда Фибоначчи с шагом, равным единице, процессорное время на каждом следующем шаге увеличивается в число, которое стемится к 1,61803398874989484… — короче, к числу Фи, или Золотому Сечению.
          Можете поломать голову над этой задачкой:)
            +5
            Отношение члена любого аддитивного ряда (а ряд Фиббоначи именно такой) к предыдущему члену стремится к золотому сечению. Чем больше числа тем дольше их вычисляет компьютер. Тут всё линейно и ничего удивительного.
              +3
              Нам на дифурах предподаватель когда-то рассказал байку про китов.

              Исследователи китов обнаружили, что отношение длины окружности кита в самом его «широком» месте к наибольшему диаметру того же кита всегда лежит в диапазоне 3.09-3.20! Поразительный факт! Тоже тема для размышлений ;-)
                0
                Ха-ха. Вызвали у меня радость. Видно исследователи китов не учили математику:)
                  +1
                  Интересно, что если взять достаточно гладкий камень, то угол между максимальным и минимальным диаметром будет около 90°.
                    0
                    Угол между диаметрами? Это как? _Оо
                      0
                      Все диаметры проходят через центр. Есть один наибольший и один наименьший диаметры.
                      Диаметры это отрезки. Найти угол между отрезками, проходящими через одну точку при желании возможно.
                        0
                        Ну если диаметром считать хорду, проходящую через центр, а за центр взять например центр масс.
                      +1
                      Нам препод по дискретке говорил, что в каком-то американском штате число Пи решили округлить до 3-х. Ну для простоты расчетов.
                        +1
                        Это правда. В Алабаме.
                    +10
                    перл ужасен!

                    #!/usr/bin/env python
                    n = 0
                    for num in range(1000000):
                       st = str(num)
                       st = '0'*(6-len(st)) + st;
                       if int(st[0]) + int(st[1]) + int(st[2]) == int(st[3]) + int(st[4]) + int(st[5]):
                          n = n+1
                    print n

                    $ python tickets.py
                    55252
                      +2
                      Я не претендую на оптимальный код :) Собрано на коленке.
                        +13
                        пайтон ужасен! :-))))

                        for($i=1,$s='00000'.$i,$c=0;$i<=999999;$i++,$s=sprintf('%06s',$i))
                        ($s[0]+$s[1]+$s[2]==$s[3]+$s[4]+$s[5])&&$c++;
                        echo "Сумма = $c";


                        — php

                        Кому не слабо написать короче? :-))))))
                          +10
                          ээ…

                          php ужасен.
                            +6
                            Это стеб был просто, если что. :-)

                            На пайтоне можно написать в 2 строки? Я серьезно, интересно просто.
                              +4
                              можно в одну (написал ниже)
                            +15
                            len([x for x in ["%06d"%x for x in range(1000000)] if sum(map(int,x[0:3])) == sum(map(int,x[3:6]))])

                            — нечитаемый python.
                              +1
                              Ну, вторая строка все равно будет с выводом. У меня тоже фактически 1 строка в этом случае, т. к. первые две на самом деле составлюят одну.

                              Но у вас красивее получилось, стоит признать.
                                +8
                                нет, не будет.

                                более быстрый вариант с выводом и без использования строк:
                                print len([x for x in range(1000000) if x/100000+x/10000%10+x/1000%10 == x % 1000/100 + x%100/10 + x%10])
                                  +2
                                  В php такое не проканает. Максимум вот так:

                                  for($i=1,$c=0;$i<=999999||die("$c");$i++,$s=sprintf('%06s',$i),@($s[0]+$s[1]+$s[2]==$s[3]+$s[4]+$s[5])&&$c++);
                                    +6
                                    На php:
                                    echo «Сумма = 55252, честное слово!»;
                                +5
                                в коллекцию от руби:

                                ('000001'..'999999').inject(0){|count, i| x = i.to_s; x[0].to_i + x[1].to_i + x[2].to_i == x[3].to_i + x[4].to_i + x[5].to_i? count + 1: count }
                                  +3
                                  perl, просто perl

                                  perl -le 'print scalar grep { my @t = split //, $_; $t[0]+$t[1]+$t[2] == $t[3]+$t[4]+$t[5] } map { sprintf( "%06d", $_ ) } (0..999999);'

                                  perl -MList::Util=sum -le 'print scalar grep { my @t = split //, $_; sum( @t[0..2] ) == sum( @t[4..5] ) } map { sprintf( "%06d", $_ ) } (0..999999);'

                                  perl -le 'print scalar grep { $_ % 10 + $_/10 % 10 + $_/100 % 10 == $_/1000 % 10 + $_/10000 % 10 + $_/100000 % 10 } (0..999999);'
                                    +1
                                    perl -MList::Util=sum -le 'print scalar grep { my @t = split //, $_; sum( @t[0..2] ) == sum( @t[4..5] ) } m(«000000»..«999999»);'
                                      0
                                      опечатался m — в конце лишняя =(
                                        +1
                                        И тогда уж не
                                        sum( @t[0..2] ) == sum( @t[4..5] )
                                        а
                                        sum( @t[0..2] ) == sum( @t[3..5] )
                                      +1
                                      Для perl это непозволительно длинные решения! :) Предлагаю так:

                                      $ perl -e 's|(?=.)|$a++%6>2?"+":"-"|ge,$b+=!eval for"0"x6..9x6;print$b'
                                      55252

                                      Короче пока не придумал.
                                        +1
                                        два решения, не претендующие на краткость, скорее на некоторую «оптимальность» алгоритма:

                                        первое «лобовое» решение, которое возникло сразу во время чтения статьи
                                        #!/usr/bin/perl -w
                                        
                                        use strict;
                                        
                                        my @summa = ();
                                        
                                        for my $i ( 0 .. 999 ) {
                                        	push @summa, summa($i);
                                        }
                                        
                                        for my $i ( 0 .. $#summa ) {
                                        	for my $j ( 0 .. $#summa ) {
                                        		printf "%03d%03d\n", $i, $j if $summa[$i] == $summa[$j];
                                        	}
                                        }
                                        
                                        sub summa
                                        {
                                        	my $x = shift;
                                        
                                        	my $s = 0;
                                        
                                        	while ( $x ) {
                                        		$s += $x % 10;
                                        		$x = int($x / 10);
                                        	}
                                        
                                        	return $s;
                                        }
                                        


                                        второе решение, которое возникло сразу после завершения
                                        #!/usr/bin/perl -w
                                        
                                        use strict;
                                        
                                        my %summa = ();
                                        
                                        for my $i ( 0 .. 999 ) {
                                        	push @{ $summa{summa($i)} }, $i;
                                        }
                                        
                                        for my $x ( sort { $a <=> $b } keys %summa ) {
                                        	my @x = @{ $summa{$x} };
                                        	for my $i ( @x ) {
                                        		for my $j ( @x ) {
                                        			printf "%03d%03d\n", $i, $j;
                                        		}
                                        	}
                                        }
                                        
                                        sub summa
                                        {
                                        	my $x = shift;
                                        
                                        	my $s = 0;
                                        
                                        	while ( $x ) {
                                        		$s += $x % 10;
                                        		$x = int($x / 10);
                                        	}
                                        
                                        	return $s;
                                        }
                                        


                                        второе решение требует 56252 итерации для нахождения 55252 чисел :)
                                          +1
                                          Для вывода всех «счастливых номеров» второе решение похоже оптимально (лучше никак не сделать). Можно только записать его в коротком golf-style:

                                          $i=$_,s//+0x/gc,push@{$a[eval]},$i for"000"..9x3;map{for$x(@$_){print"$x$_\n"for@$_}}@a


                                          Но если задача только посчитать их количество — то легко можно обойтись 1000 с небольшим итераций. См ниже в комментариях:

                                          s//+0x/gc,$a[eval]++for 0..999;$s+=$_*$_ for@a;print$s
                                    +1
                                    «Кому не слабо написать короче?» — это опасный призыв ;)

                                    Ваш вариант для php можно немного сократить:

                                    for($i=1000000;$i||die("$c");$s=sprintf("%06s",--$i),$s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5]||@$c++);

                                    (или еще на 1 символ, если забить на warning)

                                    Может можно и короче, но я не знаток php. На perl, например, можно это же решение «в лоб» реализовать сильно короче:

                                    s|(?=.)|$a++%6>2?"+":"-"|ge,$b+=!eval for"0"x6..9x6;print$b

                                      0
                                      Да, вы неплохо сократили пример, но есть одна ошибка. Операция || выполнится раньше минуса, и все будет работать не верно. Вот так павильно:
                                      for($i=1000000;$i||die("$c");$s=sprintf('%06s',--$i),$s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5]or@$c++);


                                      Или в вашем придется ставить скобки на выражение $s[0]+$s[1]+$s[2]-$s[3]-$s[4]-$s[5].
                                        0
                                        Я, конечно, php плохо знаю — но не настолько :) В php, как и в большинстве схожих языков, у логических операций приоритет ниже, чем у сложения-вычитания.

                                        Но когда я писал, я не смотрел в документацию — я просто всегда проверяю подобные куски кода, прежде чем опубликовать. Поэтому не поверьте, а проверьте — все будет работать верно! ;)
                                          0
                                          А, это моя тупая ошибка. Я проверил на самом деле с самого начала, но с той лишь разницей, что у меня было $s[0]+$s[1]+$s[2]==$s[3]+$s[4]+$s[5]||@$c++ — поэтому не сработало. Я еще очень удивился этому, т. к. на самом деле должно было. Поэтому и решил, что || выполнился раньше.

                                          Вощем, да — я стормозил.
                                            0
                                            Да, можете не комментировать, я знаю, что еще раз сторомзил. :-)))
                                        +1
                                        А я могу так:
                                        for(;$i<1000;$i++,$s="".$i)$a[$s[0]+$s[1]+$s[2]]++;foreach($a as $i)$k+=$i*$i;echo $k;

                                        Проверено, работает.
                                          +2
                                          Ну это уже другой способ решения ;) Тогда уж на php можно так:

                                          for(;$i<=999;)$a[array_sum(str_split($i++))]++;foreach($a as$i)$k+=$i*$i;echo$k;

                                          — на несколько символов короче.

                                          А на perl — еще короче:

                                          s//+0x/gc,$a[eval]++for 0..999;$s+=$_*$_ for@a;print$s

                                        0
                                        print «55252»; // :)
                                        0
                                        ну коль уж пошла такая пьянка…
                                        (я имею ввиду, что наши коды здесь просто ужасны вообще в силу своей тормознутости, ибо тут все стремятся сейчас абы их код был короче, ане оптимальней)
                                        ловите:

                                        n,s=0,'000000'
                                        while s.size
                                          +1
                                          черт, опять забыл про угловые скобки… ..(

                                          n,s=0,'000000'
                                          while s.size<7
                                          s.succ!
                                          n+=1 if s[0]+s[1]+s[2]==s[3]+s[4]+s[5]
                                          end
                                          p n
                                            0
                                            просто кардинальная оптимизация по сравнению с
                                            ('000001'..'999999').inject(0){|count, i| x = i.to_s; x[0] + x[1] + x[2] == x[3] + x[4] + x[5]? count + 1: count }

                                            (при первом комменте я накосячил с приведением)
                                              +1
                                              Пардон, когда я начал писать свой коммент, ваш ещё просто небыл написал.
                                              Да, мы сделали одинаково ..)
                                              А можно ещё укоротить, если заюзать select и size
                                                +1
                                                на самом деле ваш код примерно на 30 процентов быстрее. но он совсем не рубивский :)
                                        +1
                                        Я на этой задачке в школе на олимпиаде завалился, так же как и вы сделал все неоптимальным методом, а оказалось что некоторые преподаватели своим ученикам рассказывали о более продуктивных методах решений данной задачи.
                                          0
                                          Да, всего их около 540 Кб (http://heel.org.ua/stuff/lucky_tickets.php)
                                            +3
                                            «жертвы метрополитена» наверное всю жизнь их жрать будут ;)

                                            мне кажется это всё контроллёры придумали чтобы не скучно работать было — каждый раз цирк и почти гарантированная эффективность ;) а для жертвы приключение ;)
                                            если учесть что есть как минимум два метода расчёта и народ не всегда правильно считает — то скучно не было ;)
                                            +
                                            semachki.narod.ru/txt/bilet.htm

                                            никогда не жрал и жрать не буду, со стороны это так… меня больше интересовали автоматы по продаже билетов, где сверху прозрачная часть корпуса и через щель в ней кидаешь монетки на резиновую дорожку с разделителями, крутишь ручку чтобы вылезли билеты и видно как внутри двигается резинка-коврик, монетки как лежали на ней так и лежат (те никакого процесса над ними не происходит) но ты уже получил билеты — кажется это и был комунизм ;)
                                              0
                                              pki.botik.ru/articles/t-autobus1971.pdf
                                              ;)
                                              0
                                              А я до сих пор не знаю как считать счастливые билетики, как не смешно это может звучит:) Раньше меня это особо не интересовало, а потом как-то пересели на магнитные и я и не помню таких билетов.

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

                                              Но номера есть везде, даже на магнитных, а как понять счастливый он или нет не знаю до сих пор… Не расскажите?
                                                0
                                                Сумма первой тройки цифр должна быть равна сумме второй тройки
                                                  +2
                                                  это нормально

                                                  в статье ссылка на wiki — там три варианта счёта:
                                                  Счастливость» билета можно определить несколькими методами. Наибольшее распространение получили три из них:
                                                  1) Московский — если на автобусном билете напечатано шестизначное число, и сумма первых трех цифр равна сумме последих трех, то этот билет считается счастливым.
                                                  2) Ленинградский (менее распространённый) — если сумма чётных цифр билета равна сумме нечётных цифр билета, то билет считается счастливым (в статье журнала «Квант» именно этот способ назван «московским»).
                                                  3) Некоторые люди считают, что если арифметический квадратный корень из суммы шести цифр номера билета есть целое число, то билет также является счастливым. Количество таких билетов с шестизначными номерами равно 99153.

                                                  пластик не жри ;)
                                                    0
                                                    99153 — если считать, что существует «000000»
                                                      0
                                                      как-то в Томске слышал еще один вариант- сумма первых двух цифр равна сумме вторых двух цифр и равна сумме третьих двух цифр
                                                      • НЛО прилетело и опубликовало эту надпись здесь
                                                      –3
                                                      Я уже писал в комментарии идею решения задачи про счастливые билетики методом динамического программирования. habrahabr.ru/blogs/i_am_clever/40036/#comment_970933
                                                      Вообще, если честно, не понимаю, какой смысл делать на Хабре пост про программу уровня школьника-восьмиклассника?
                                                        +3
                                                        Я не программист. И мне такие задачки почитать интересно :)
                                                        –1
                                                        А вы уверены, что билеты начинются с 000 000? Мне почему то казалось, что с 100 000, ибо ниразу в жизни не видел билет начинающийся на 0.
                                                          0
                                                          Я видел. Существуют такие. Точно.
                                                            0
                                                            Первый билет в серии 000001, это точно )
                                                            0
                                                            брутфорс… какой ужас… люди совершенно разучились думать! умножать и делить в уме, делая пометки ручкой на бумаге…
                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                +6
                                                                0: 000: 1: 1: 1
                                                                1: 001: 3: 3: 9
                                                                2: 002 011: 3+3: 6: 36
                                                                3: 003 012 111: 3+6+1: 10: 100
                                                                4: 004 013 022 112: 3+6+3+3: 15: 225
                                                                5: 005 014 023 113 122: 3+6+6+3+3: 21: 441
                                                                6: 006 015 024 033 114 123 222: 3+6+6+3+3+6+1: 28: 784
                                                                7: 007 016 025 034 115 124 133 223: 3+6+6+6+3+6+3+3: 36: 1296
                                                                8: 008 017 026 035 044 116 125 134 224 233: 3+6+6+6+3+3+6+6+3+3: 45: 2025
                                                                9: 009 018 027 036 045 117 126 135 144 225 234 333: 3+6+6+6+6+3+6+6+3+3+6+1: 55: 3025
                                                                10: 019 028 037 046 055 118 127 136 145 226 235 244 334: 6+6+6+6+3+3+6+6+6+3+6+3+3: 63: 3969
                                                                11: 029 038 047 056 119 128 137 146 155 227 236 245 335 344: 6+6+6+6+3+6+6+6+3+3+6+6+3+3: 69: 4761
                                                                12: 039 048 057 066 129 138 147 156 228 237 246 255 336 345 444: 6+6+6+3+6+6+6+6+3+6+6+3+3+6+1: 73: 5299
                                                                13: 049 058 067 139 148 157 166 229 238 247 256 337 346 355 445: 6+6+6+6+6+6+3+3+6+6+6+3+6+3+3: 75: 5625

                                                                14: 059 068 077 149 158 167 239 248 257 266 338 347 356 446 455: 6+6+3+6+6+6+6+6+6+3+3+6+6+3+3: 75: 5625

                                                                10+136+666+2080+5050+8730+10924=812+7130+19654=7942+19654=20596 *2=41192 +5625= 45817 -1=45816

                                                                ну вот исписал бы отсилы пол-листа, и без никаких формул из комбинаторики
                                                                да, погрешность в 20%, но мне бы немного усталости с глаз, да в руки тетрадь, ане notepad, и всё прекрасно считается за 10минут
                                                                  +1
                                                                  Лень — двигатель прогресса…
                                                              +1
                                                              Я смотрю в Новосибирске самые счастливые билеты :)
                                                                –1
                                                                помню свой первый «компьютер» 8битная приставка сюбор, там был интерпретатор языков G-BASIC и F-BASIC, на нем в 8м классе я расчитывал эту задачку. решалась задачка 2мя способами: вложенными циклами и с помощью массива. точный результатов не помню, но помню что меня удивило что вероятность получить счастливый билетик не так уж и мала :)
                                                                теперь я смело могу сказать что BASIC ужасен, причем во всех своих проявлениях :)
                                                                  +1
                                                                  Ага, а теперь в 1000 раз быстрее.

                                                                  #include <stdio.h>
                                                                  #include <memory.h>
                                                                  
                                                                  void main()
                                                                  {
                                                                    int dynamic_proramming_rules[27], answer = 0; //coz 27 is max sum of nubers in [1..999]
                                                                    memset(dynamic_proramming_rules,0,sizeof(dynamic_proramming_rules));
                                                                    for (int i=1; i<=999; ++i) {
                                                                      ++dynamic_proramming_rules[i/100+(i%100/10)+(i%10)-1];
                                                                    }
                                                                    for (int i=0; i<27; ++i) {
                                                                      answer += dynamic_proramming_rules[i] * dynamic_proramming_rules[i];
                                                                    }
                                                                    printf("%i", answer);
                                                                  }
                                                                    0
                                                                    А причем здесь dynamic_proramming?
                                                                      0
                                                                      Наверно для пафоса.
                                                                        0
                                                                        Я поясню. Наше шестизначное число разбивается на две триады. В первой триаде мы подсчитываем распределение сумм. Во второй — мы то же самое не делаем, а используем уже подсчитанное распределение (т. к. они одинаковы). Это и есть динамическое программирование. Пусть на уровне инфузории туфельки, но оно. :)
                                                                      0
                                                                      Такой код больже похож на ДП

                                                                      #include #define forn(i, n) for(int i = 0; i < int(n); ++i)
                                                                      #define SQR(a) ((a) * (a))
                                                                      using namespace std;
                                                                      int main(){
                                                                      nt true_dynamic_proramming_rules[4][28], ans = 0;
                                                                      memset(true_dynamic_proramming_rules, 0, sizeof(true_dynamic_proramming_rules));
                                                                      true_dynamic_proramming_rules[0][0] = 1;
                                                                      forn(q, 3)
                                                                      forn(i, 19) forn(j, 10)
                                                                      true_dynamic_proramming_rules[q + 1][i + j] += true_dynamic_proramming_rules[q][i];
                                                                      forn(i, 28) ans += SQR(true_dynamic_proramming_rules[3][i]);
                                                                      cout << ans;
                                                                      return 0;
                                                                      }
                                                                        0
                                                                        Кхм, код страннно изменился во время форматирования в 1 и 5 строчках.
                                                                          0
                                                                          Очень хорошо! Очень масштабируемое решение!
                                                                      +12
                                                                      А у нас в универе на базах данных нужно было решить эту задачу с помощью SQL, причем не используя таблиц. Извините что такой динный коммент, хабру бы не помешала фича заключающая код в бокс со скроллами (просветите если есть). MySQL 5.0:

                                                                      SELECT COUNT(T1.R1) AS "Всего счастливых билетов"
                                                                      FROM
                                                                      (SELECT 0 R6 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T6`,

                                                                      (SELECT 0 R5 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T5`,

                                                                      (SELECT 0 R4 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T4`,

                                                                      (SELECT 0 R3 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T3`,

                                                                      (SELECT 0 R2 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T2`,

                                                                      (SELECT 0 R1 UNION
                                                                      SELECT 1 UNION
                                                                      SELECT 2 UNION
                                                                      SELECT 3 UNION
                                                                      SELECT 4 UNION
                                                                      SELECT 5 UNION
                                                                      SELECT 6 UNION
                                                                      SELECT 7 UNION
                                                                      SELECT 8 UNION
                                                                      SELECT 9) `T1`

                                                                      WHERE T6.R6+T5.R5+T4.R4=T3.R3+T2.R2+T1.R1;

                                                                        +1
                                                                        порадовало
                                                                          +1
                                                                          Вот это жесть.
                                                                            0
                                                                            Я переложил ваш запрос на Оракл. Стало несколько короче.
                                                                            select count(*) as "Всего счастливых билетов" from 
                                                                            (select rownum-1  R6 from dual
                                                                              connect by level <= 10),  
                                                                            (select rownum-1 R5 from dual
                                                                              connect by level <= 10),
                                                                            (select rownum-1 R4 from dual
                                                                              connect by level <= 10),
                                                                            (select rownum-1 R3 from dual
                                                                              connect by level <= 10),
                                                                            (select rownum-1 R2 from dual
                                                                              connect by level <= 10),
                                                                            (select rownum-1 R1 from dual
                                                                              connect by level <= 10)
                                                                            where R1+R2+R3=R4+R5+R6;
                                                                            


                                                                            Здесь для генерации чисел от 0 до 9 используется цикл с 10 итерациями: connect by level <= 10. Таблицы не используются, если не считать dual за таблицу.
                                                                            +3
                                                                            Перл ужасен, да и вообще надо использвать более прогрессивные методы.
                                                                            Ведь число счастливых билетов есть суть интеграл:
                                                                            1/pi * int( (sin(5x)/sin(x/2) )6,0,pi )

                                                                            Далее пишем простой код.
                                                                            #include <iostream>
                                                                            #include <math.h>
                                                                            
                                                                            double pi = 3.1415926535897932384626433832795028841971693993751; 
                                                                            
                                                                            double f(double arg)
                                                                            { 
                                                                            return 1/pi * pow(sin(arg*5)/sin(arg/2),6);
                                                                            }
                                                                            
                                                                            int _tmain(int argc, _TCHAR* argv[])
                                                                            { 
                                                                            const int N=15;
                                                                            double knots[N],values[N];
                                                                            for(int i=0;i<N;i++)
                                                                            {
                                                                            knots[i] = i*pi/N + (i-N/2)*1e-7;
                                                                            values[i] = f(knots[i]);
                                                                            }
                                                                            double result=0;
                                                                            for(int i=1;i<N;i++)
                                                                            result+=(values[i]+values[i-1]) / 2 * (knots[i] - knots[i-1]);
                                                                            std::cout<<result << '\n';
                                                                            
                                                                            return 0;
                                                                            }
                                                                            получаем 55252,2
                                                                            вычитаем 1, поскольку 1 билет (000000) нам не интересен, а 0,2 это погрещность при интегрировании. Если нужно более точно, то можно воспользоваться методом «3/8», он дает приблежение как четвертая степень, а не как вторая.
                                                                              –1
                                                                              определять pi это велосипед :)
                                                                              #define _USE_MATH_DEFINES
                                                                              #include <math.h>

                                                                              И далее заменяете все вхождения double pi на M_PI

                                                                              #define M_PI       3.14159265358979323846
                                                                                0
                                                                                Ну еще и интегрирование трапецией тот еще велосипет. Наверняка есть либы, в которых это все давно написано.
                                                                                Целью было показать альтернативный метод вычисления, который скорее всего будет быстрее, чем любой перебор.
                                                                                Впрочем каюсь, каюсь.
                                                                                  0
                                                                                  Сдаюсь, я не смог сравнить ваш и #мой (ДП) код выше — они оба выполняются за 0 тиков :)
                                                                                    +5
                                                                                    Действительно, велосипед :)
                                                                                    Интегрируем в элементарных функциях
                                                                                      +2
                                                                                      Выпендрился, зачет. :-)))
                                                                                  0
                                                                                  Прежде, чем использовать прогрессивные методы их нужно еще и доказать:)
                                                                                    0
                                                                                    В статье приведена очень занимательная ссылка. Там этот (и не только этот) метод обосновывается. Вообще эта ссылка — самое полезное, что есть в статье, IMHO :)
                                                                                      0
                                                                                      эх, не обновился я вовремя! ;)
                                                                                      0
                                                                                      См. доказательство тут: http://www.ega-math.narod.ru/Quant/Tickets.htm#A2
                                                                                    +1
                                                                                    Осталось решить эту задачу шаблонами С++ сразу на этапе компиляции, как завещал Великий и Ужасный Александреску ;-)
                                                                                      0
                                                                                      for (i1=0, i1<=9,i1++)
                                                                                      for (i2=0, i2<=9,i2++)
                                                                                      for (i3=0, i3<=9,i3++)
                                                                                      for (i4=0, i4<=9,i4++)
                                                                                      for (i5=0, i5<=9,i5++)
                                                                                      for (i6=0, i6<=9,i6++)
                                                                                      if (i1 + i2 + i3) == (i4 + i5 + i6) {....}

                                                                                      может, как-то так? или кто-то в каментах уже писал про подобное?
                                                                                        +35
                                                                                        Кто говорил что билета 000000 не существует? Вот вам моя гордость. Единственный случай, когда два счастливых билета идут подряд.
                                                                                          +4
                                                                                          Ога! Вы кондуктор?
                                                                                            +18
                                                                                            Неа. Просто повезло. Однажды когда зашёл в трамвай, купил билет с номером где-то 999987. Потом подошёл к кондуктору и попросил билет с девятками, а за ним был и с ноликами. Купил оба.
                                                                                              0
                                                                                              я примерно так-же брал ребенку 5-ки :)
                                                                                              увидел что они рядом и купил все билеты до них включительно, кондуктор смотрел на меня круглыми глазами :")
                                                                                            0
                                                                                            Хм :) Каюсь, не знал!
                                                                                              0
                                                                                              круто
                                                                                                0
                                                                                                Везет же людям!
                                                                                                  +6
                                                                                                  Даже и не знаю — кушать или нет. =)
                                                                                                  +4
                                                                                                  Почти 54 метра рулончик то будет (:
                                                                                                    0
                                                                                                    Прямо как туалетная бумага :)
                                                                                                    0
                                                                                                    Wow!!!
                                                                                                      0
                                                                                                      Stack Overflow :)
                                                                                                      –2
                                                                                                      первый счастливый билет 1001)
                                                                                                      а почему не 0110?
                                                                                                        0
                                                                                                        001001 видимо хотели сказать.
                                                                                                        Четырёхзначные билетики наврятли где-то водятся.
                                                                                                        +1
                                                                                                        Спасибо за ссылку на статьи из «Кванта».
                                                                                                          +1
                                                                                                          «Счастливые» билетики собираю )). Надеюсь, теперь процесс их нахождения будет проще =).
                                                                                                            +2
                                                                                                            Посчитал количество билетов типа «встреча» (суммы отличаются на единицу) и «письмо» (отличаются на 2). «Встреча» — 109494 билетов, «письмо» — 106524 билетов. В итоге примерно каждый 4-ый билет привносит немного позитива в нашу жизнь :)

                                                                                                            А ещё можно ввести «коэффициент счастливости» билета — пусть это будет 1 — (abs(сумма_первых_трех_цифр — сумма_последних_трех_цифр) / 27). Тогда у счастливых билетов «коэффициент счастливости» будет равен 1, у «встречи» — 26/27, у «письма» — 25/27. Теперь можно напридумывать названий для остальных значений и подобрать для себя удобный коэффициент исходя из желаемой вероятности получить «почти счастливый» билет. Можно ещё распределение посчитать, в общем будет чем себя занять на пару дней.
                                                                                                              0
                                                                                                              Ещё интересно получить условные плотности этого распределения при фиксированных первых цифрах, например :) Так как если исходить из предположения о том, что номера выдаются подряд, то эти цифры будут меняться редко, стало быть, есть возможность оценить свои шансы на сегодняшний день, зная цифры во вчерашнем билете.
                                                                                                              +3
                                                                                                              Мне казалось, что в Москве такие билетики уже давно не используются, нет?
                                                                                                                0
                                                                                                                Да, счастливые билеты по-московски — это те, которые вешают турникет :)
                                                                                                                +4
                                                                                                                Вспомнилось:
                                                                                                                «Не существует ни одного числа, которое не обладало бы какими-нибудь необычными свойствами.»
                                                                                                                (М. Гарднер. От мозаик Пенроуза к надёжным шифрам)
                                                                                                                  0
                                                                                                                  билетов, счастливых по новосибирски, ровно 670 штук (см. Статью «кванта»). А полусчастливых (когда суммы каких либо двоек равны) уже 1990!
                                                                                                                    +2
                                                                                                                    Я счастливый билет всегда на выходе съедаю.
                                                                                                                      +2
                                                                                                                      Не рекомендую это делать, они не стерильны.
                                                                                                                        0
                                                                                                                        Просто счастья очень хоца.
                                                                                                                      +5
                                                                                                                      Я всё жду, когда кто-нить из вас на брейнфаке напишет код.
                                                                                                                        +6
                                                                                                                        ++++++++++[->++++++++++[->++++++++++[-><[->+>+<<]>[-<+>]<<[->>+>+<<<]>>[-<<+>>]<<<[->>>+>+<<<<]>>>[-<<<+>>>]>[[->>>>>>>>>>>>>>>>>>>>>>>>>>>>>+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<]>[-<+>]<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>>>>>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<<<<<<<-]>+<<[[->+<]>-<<]<]<]<]>>>>>[[-<+<+>>]<[-<[-<+<+>>]<[->+<]>>]<[-]>>>]<<<<<<[>[-<+>]<<]>.

                                                                                                                        всю ночь пыхтел ..)
                                                                                                                          0
                                                                                                                          У вас ошибка в 138 символе, BrainFuck Engine обломится ;)
                                                                                                                            0
                                                                                                                            этот символ ">" — в чем его ошибка уж извольте обосновать ..))))
                                                                                                                              0
                                                                                                                              Ну оно и правда не валидно ))) На выходе только один символ «ф» ;)
                                                                                                                                0
                                                                                                                                Ааа… я забыл уточнить, что пренебрег ограничением в 256 и выводом в ASCII ..)
                                                                                                                        0
                                                                                                                        В 10 классе у меня на олимпиаде по математике такая задача была
                                                                                                                          +3
                                                                                                                          Хм. У меня тоже. И у человека выше. Как-то слишком часто повторяются условия задач на олимпиадах.
                                                                                                                          –1
                                                                                                                          у меня в кошельке до сих пор лежат билеты еще с 10го и 11 класов школы, когда ездаили на занятия по УПК — мне всегда доставался счастливый билет. Накопилось штук 50 8)
                                                                                                                            +3
                                                                                                                            Пожарьте их на растительно масле с сыром и луком. Съеште. И будет вам счастье. :-))))
                                                                                                                            +3
                                                                                                                            у меня прямо передо мной сейчас лежит билетик с номером 011110, (на работе в понедельник буду, отсканирую) который я получил в самый неудачный день в моей жизни, причем я совершенно случайно потратил на него последний пятак, и уехал на этом дурацком троллейбусе не туда куда мне нужно… на этом неудачи закончились правда…
                                                                                                                              0
                                                                                                                              В маршрутке Медведково — Тарасовка выдают за один проезд сразу 4 билета: на 17 рублей + 10 рублей + 10 рублей + 3 рубля = на сумму 40 рублей
                                                                                                                                +1
                                                                                                                                В Ростове-на-Дону мне рассказывали про парня, у которого дома висела картина — спинка от старого троллейбусного сиденья, сплошь обклеенная _счастливыми_ билетиками.

                                                                                                                                Называлась инсталляция просто и незатейливо: «Счастье» :-)
                                                                                                                                  +4
                                                                                                                                  еще одно решение на перле, чуть подлиннее предложенных, зато выглядит забавно:

                                                                                                                                  print 0+grep{/(.)(.)(.)(.)(.)(.)/ && $1+$2+$3==$4+$5+$6}'0'x6..1x6
                                                                                                                                    +1
                                                                                                                                    ой, третий с конца символ должен быть конечно не 1, а 9. С девятками просто очень долго работает :)
                                                                                                                                      0
                                                                                                                                      Ну у меня подход в принципе точно такой же — только я прямо в строку вставляю плюсы и минусы — и потом делаю eval ;)
                                                                                                                                        +1
                                                                                                                                        ваш вариант бесспорно более хитроумен, зато мой больше похож на сиськи :)
                                                                                                                                          0
                                                                                                                                          Да, меня уже собственные сотрудники пристыдили — сказали, что сиськи круче :-\
                                                                                                                                            +1
                                                                                                                                            Ладно, тогда хоть сокращу на пару символов Ваше решение :)

                                                                                                                                            print~~grep{/(.)(.)(.)(.)(.)(.)/,$1+$2+$3==$4+$5+$6}"0"x6..9x6

                                                                                                                                      +2
                                                                                                                                      В итоге все начали мериться пиписьками, у кого код меньше :) Не ожидал ))
                                                                                                                                        –2
                                                                                                                                        Формулу придумать не удалось но кое-что наваял:



                                                                                                                                        Здесь k — это сумма цифр, n — количество цифр в половинке билета.
                                                                                                                                        Количество возможных комбинаций для конкретной суммы k вычисляется по формуле:
                                                                                                                                        Nn(k) = Nn(k-1) + Nn-1(k) — Nn-1(k-10).
                                                                                                                                        Вообще говоря это справедливо для ячеек, выделенных голубым цветом, ибо для остальных одно из значений в формуле не существует (равно нулю).
                                                                                                                                        Так, для оранжевых ячеек это будет:
                                                                                                                                        Nn(k) = Nn(k-1) + Nn-1(k),
                                                                                                                                        а для жёлтых:
                                                                                                                                        Nn(k) = Nn(k-1) — Nn-1(k-10).
                                                                                                                                        Например, количество всевозможных комбинаций для «трехзначных» билетов сумма цифр в которых равна 12, будет равно:
                                                                                                                                        73 = 69 + 7 — 3.

                                                                                                                                        Количество всех билетов вычисляется как сумма квадратов полученных значений для всех k.

                                                                                                                                          0
                                                                                                                                          А я раньше играл в «сотню» с этими билетиками. Суть — расставить арифметические знаки между цифрами так, чтобы в результате получилось сто. Например, попался билет 516233. Решение: 5 * 16 + 23 — 3 = 100. Весьма занимательно и полезно с утра для пробуждения по дороге :)
                                                                                                                                            0
                                                                                                                                            Советую посмотреть самый первый комментарий, там ссылка на статью об этом.
                                                                                                                                            0
                                                                                                                                            Не в тему про билеты, но в тему про интересные занятия, когда делать нечего.
                                                                                                                                            Вероятно, вы видели игрушку
                                                                                                                                            users.cosmostv.by/rmaksim/coding/yours40moves/yours40moves.html
                                                                                                                                            где нужно переставить шарики за 40 ходов.
                                                                                                                                            Так вот первое, что мне пришло в голову (и было реализовано) — это написать программку, которая найдет мне решение.
                                                                                                                                            Сначала принялся за JavaScript, как не требующий ничего, кроме блокнота и браузера. Когда понял, что медленно получается, перекинул на с++, доработал и эта зараза нашла мне все возможные варианты, в том числе и вожделенные 40 ходов :)

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

                                                                                                                                            Самое читаемое