Форум PHP

Добрый день.

Рассмотрим последовательность чисел от 1000000000 и до 1999999999
(включительно). В этой последовательности чисел вычеркнем все числа, сумма цифр
которых меньше 30. Из оставшихся чисел вычеркнем все числа, сумма цифр которых больше
или равна 40. Из оставшихся чисел вычеркнем все числа, в которых цифра 5 содержится
более одного раза. Найдите остаток от деления произведения оставшихся чисел на число 29.
Обоснуйте свой ответ и приложите исходные тексты (например, тексты программ или
электронные таблицы), использованные для получения ответа.

Понятное дело что цикл 1000000000 и до 1999999999 будет оченьььььььь долго выполняться. я без понятия как еще вычеркнуть те числа, тут нужны какие-то формулы математические или еще что, прошу подсказки в какую сторону копать, все заранее большое спасибо!

Вообще цикл должен содержать 3486784401 итерраций. Теоретически даже в 32-битное число убираемся, но понятно, что задача комбинаторная, именно для этого число начинается с такого значения, чтобы подчеркнуть, что первая цифра не очень важна, а числа следует рассматривать как строки.

а можно что-то более конкретное и по подробней, не очень понял.

Анализа таких алгоритмов обычно начинают с того, а собственно какое минимальное число и какое максимальное. Очевидно, что минимально значение начинается с 1111111599 (30), а максимальное 1999930000 (40). Дальше пока ничего не вспомнилось :)))

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

Пардон, мб начинается с 1000003999 т.к.:

for($i=1000000000; $i<2000000000; $i++) {     $arr_sum=array_sum(str_split($i));     if($arr_sum>30)     {         echo $i;         exit();     } }

А ну да... ну это в любом случае ничего не дает - слишком близко число к началу и то и другое... дерево тут надо строить, чтобы сразу ветками отрубать области, где нет решений.

Очевидно также, что нужно циклом перебирать не значения от 1000000000 и до 1999999999, а символы от последнего 0 до первого 1, это позволит быстрее подсчитать значения и отсечь решения, которые ведут к неправильному результату.

А где такие жосткие задачки, если не секрет? Чет попытался проанализировать - мозг закипел (

Олимпиада Ломоносова от МГУ для школьников, это еще не сложное задание http://lomonosov.msu.ru/sites/default/files/tasks/2011-2012/informatics_2012.PDF

Школьники.... ......и на себе ощущаешь на сколько за последние 15 лет заржавел мозг (((

>1. На счёт перебора:
>Длинные числа можно, например, представлять массивом из 10 цифр.
>Напишите функцию, которая по заданному числу быстро выдаёт следующее, удовлетворяющее >условию.
>
>2. На счёт перемножения:
>Остаток произведения равен произведению остатков (Математика рулит!).
>Поэтому надо накапливать не офигенное произведение чисел, а остаток от произведения >остатков.
>Напишите функцию, вычисляющую остаток от деления "числа-массива" на 29.
>
>3. На мой счёт:
>200руб и золотой ключик в Ваших руках!

Источник: http://otvet.mail.ru/question/68707158

какойто бред, но малоли поможет

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

Ну на переборе только "правильных" чисел и обрубании "веток" я зашпарился, но учитывая пункт 2 предыдущего поста сделал так:

<?php   set_time_limit(0);   $startmicrotime = microtime(true);   $ost = 0;   for($i = 1000000000; $i < 1009999999; $i++){     $arr_sum=array_sum(str_split($i));     if($arr_sum < 30 || $arr_sum > 40) continue;     if(substr_count((string)$i,"5",1) > 1) continue;     if(!$ost) $ost = $i%29;     else $ost = ($ost*($i%29))%29;   }   echo $ost."<br>".round(microtime(true)-$startmicrotime,4); ?>

результат

18 55.4892

Значит до 1999999999 за 5500 секунд сосчитает =)

А если переписать вот так:

<?php   set_time_limit(0);   $startmicrotime = microtime(true);   $ost = 0;   for($i = 1000000000; $i < 1009999999; $i++){     $s = (string)$i;     if(substr_count($s,"5") > 1) continue;     $sum = $s[1]+$s[2]+$s[3]+$s[4]+$s[5]+$s[6]+$s[7]+$s[8]+$s[9];     if($sum < 29) continue;     if($sum > 38) continue;     $ost = $ost ? ($ost*($i%29))%29 : $i%29 ;   }   echo $ost."<br>".round(microtime(true)-$startmicrotime,4); ?>

то время сокращается почти в 2 раза

13 29.7928

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

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

Даже не собираюсь спорить. Но и решения к сожалению не вижу. А хотелось бы увидеть!

только чтоб в пределах 30 секунд, мало будет того, что нужно составить перебор так чтоб не проверять цифры на соответствие условиям, но и как-то нужно будет исключить из вычислений около 90% подходящих под условия значений, т.к. по первому условию (от 30 до 40) подходит 11% всех чисел, а это 111 111 111 штук. Ну еще процентов 5 из них исключится по второму условию, пусть даже 10%, останется 100 миллионов, а 10 миллионов считаются 30 секунд. значит только на вычисления нужно 300 сек. Короче говоря ОООООООчень хотелось бы увидеть красивое решение =)

а разве так:

if($sum < 29) continue;  if($sum > 38) continue;

быстрее чем:

if($sum < 29 || $sum > 38) continue;

???

не значительно, но на таких объемах.... Около секунды сэкономило. Просто в 1ом варианте проверяется 1 условие и если оно совпадает, то сразу переходит к следующему кругу, а во 2ом варианте проверяются всегда оба условия. Больше всего экономия на

$sum = $s[1]+$s[2]+$s[3]+$s[4]+$s[5]+$s[6]+$s[7]+$s[8]+$s[9];

хм, в свое время эксперементировал, да и логично предположить что если одно условие верно то второе не нужно проверять (если между ними стоит ИЛИ) доказательство.

if(true || echo123()) { echo 'эта строка будет выводиться'; } function echo123() { echo 'эта строка не будет выводиться'; }

>Остаток произведения равен произведению остатков (Математика рулит!).

если так, то в списке этих чисел найдется несколько, которые делятся на 29 без остатка, т.е. с остатком 0. А значит и произведение общее - 0. В качестве доказательства необходимо найти хотя бы одно число из диапазона, удовлетворяющее условиям на сумму цифр и нацело делящееся на 29.

Function olimp29() {     For ($i=34482759; $i<68965517; $i++)    {         $arr_sum=array_sum(str_split($i*29));         if($arr_sum < 30 ) continue;         if($arr_sum > 40) continue;         Return $i*29;     } }

34482759* 29 = 1000000011 - начало диапозона
68965517*29 = 1999999993 - конец диапазона.
перебираем только числа, нацело делящиеся на 29.
Функция вернет первое число, соответствующее условиям. Время выполнения: 0.0012

Да, вы правы. Любое число умноженное на число кратное 29 также будет кратно 29.

И ведь я когда написал скрипт вычисляющий перебором, видел этот ноль, но счел багом (исключением из правила) и подправил скрипт так чтоб ноль не получался =(