Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Ещё одна задача...

Автор: altairaimenov 5.3.2015, 19:05

Добрый день! Нам даётся число n. Необходимо ставить поочередно "+" и "-" между цифрами от 1 до n и вывести результат примера Ограничение : 0.5 секунды n - 10^15 Пример: 12 Ответ: 5 Поясняю: +1 -2 +3 -4 +5 -6 +7 -8 +9 -1+0 -1+1 -1+2 = 5 P.s. Язык - C++

Автор: sQu1rr 5.3.2015, 19:16

Ну а что у вас не получается то? мы тут все такие помогаем, а то я смотрю вы обрадовались что за вас все вчера решили

Автор: altairaimenov 5.3.2015, 20:11

Цитата(sQu1rr @ 5.3.2015,  19:16) Ну а что у вас не получается то? мы тут все такие помогаем, а то я смотрю вы обрадовались что за вас все вчера решили  Дело в том что N = 10^15. Тривиальный алгоритм я могу написать,но он до 10^7.Я просто искал форумы где я могу просить помощи в нерешенных мной задач.Занимаюсь я не ради кого-то,а ради себя. Думаю понятно

Автор: sQu1rr 6.3.2015, 12:53

Цитата(altairaimenov @  5.3.2015,  17:11 ) Дело в том что N = 10^15. Тривиальный алгоритм я могу написать,но он до 10^7.Я просто искал форумы где я могу просить помощи в нерешенных мной задач.Занимаюсь я не ради кого-то,а ради себя. Думаю понятно  Здесь есть раздел - алгоритмы, там помогают именно с ними. Но не надо уже дублировать. Есть какиенибудь идеи - как решить?

Автор: konshyn 6.3.2015, 15:18

Обыная задачка на последовательности: суммы: 1..9 = 5 10..99 = 45 100..999 = 450 1000..9999 = 4500. Так как на нужно записывать цифры по порядку, то: числа с нечетным набором цифр имеют положительные суммы, с четным - отрицательные, т.е., например, нам нужно найти сумму от 1 до 99 999, то будет такая последовательность: +5 -45 + 450 - 4500 + 45000 = 40910. Тут понятно, что сложить 5 чисел намного быстрее, чем пускать 5 циклов, чтобы посчитать от 1 до 100 000, или как Вы там считаете. Я думаю, что дальше сами справитесь с анализом цифр.

Автор: feodorv 7.3.2015, 15:10

Цитата(konshyn @  6.3.2015,  15:18 ) +5 -45 + 450 - 4500 + 45000 Как-то я не уверен, что здесь будет знакопеременный ряд. В обоснование приведу такое соображение. Рассмотрим знакоинвертированный ряд (для удобства): Код +0-1+2-3+... Тогда в подпоследовательности 0..9 будет четное число членов, и 1 от числа 10 пойдет со знаком +. В подпоследовательности 10..99 опять-таки будет четное число членов, и 1 от числа 100 пойдет со знаком +. В подпоследовательности 100..999 опять-таки будет четное число членов, и 1 от числа 1000 пойдет со знаком +. И так далее. Цитата(konshyn @  6.3.2015,  15:18 ) числа с нечетным набором цифр Для чисел с нечетным числом цифр всё вообще элементарно.

Автор: konshyn 9.3.2015, 11:06

Цитата(feodorv @  7.3.2015,  15:10 ) Как-то я не уверен, что здесь будет знакопеременный ряд. В обоснование приведу такое соображение. Рассмотрим знакоинвертированный ряд (для удобства): 1) Прежде, чем написать, я проверил:) 2) Знакоинвертированный ряд здесь не может быть примером, т.к. автор написал, как выглядит последовательность. Цитата(feodorv @  7.3.2015,  15:10 ) Для чисел с нечетным числом цифр всё вообще элементарно.  Да:)

Автор: feodorv 9.3.2015, 17:28

Цитата(konshyn @  9.3.2015,  11:06 ) Прежде, чем написать, я проверил:) Вот это одобряю!    Ну тогда частичные суммы имеют иной вид: Цитата(konshyn @  6.3.2015,  15:18 ) 1..9 = 5 10..99 = 45 100..999 = -450 1000..9999 = 4500 10000..99999 = -45000 А общая сумма такая: 5 - (45 - 450 + 4500 - 45000)   Цитата(konshyn @  9.3.2015,  11:06 ) Знакоинвертированный ряд здесь не может быть примером Почему? Трудно в конце знак поменять?))) Такой ряд удобен, потому что для него частичные суммы 0..9 = -5 10..99 = 45 100..999 = -450 1000..9999 = 4500 10000..99999 = -45000 тупо складываются, а итоговая сумма выглядит проще: -(-5+45-450+4500-45000). Если что, то я тоже проверял)))

Автор: konshyn 10.3.2015, 11:31

Цитата(feodorv @  9.3.2015,  17:28 ) Почему? Трудно в конце знак поменять?))) Такой ряд удобен, потому что для него частичные суммы 0..9 = -5 10..99 = 45 100..999 = -450 1000..9999 = 4500 10000..99999 = -45000 тупо складываются, а итоговая сумма выглядит проще: -(-5+45-450+4500-45000). Вы правы, более удобное решение за Вами:)

Автор: feodorv 11.3.2015, 03:28

konshyn, да там удобства кот наплакал, но все же))) Благодаря тому, что сумма ряда Код +0 - 0 + 0 - 1 + 0 - 2 + ... + 0 - 9 +1 - 0 + 1 - 1 + 1 - 2 + ... + 1 - 9 ... +9 - 0 + 9 - 1 + 9 - 2 + ... + 9 - 9 равна нулю, для чисел с четным числом цифр возможно рассчитать частичную сумму от 100..0 до abc..z (а это то, что не доставало))) путем редуцирования начального числа делением на 100 (что подразумевает индукцию). С учетом некоторых хитростей программа для вычисления частичных сумм произвольных четноцифровых (черт, как это одним словом сказать?) чисел приобрела вид: Код #include <stdio.h> #define gint_t int #define GPRINT "" int R[100]; void rFill( void ) {   unsigned int i;   R[0] = 0;   for( i = 1; i < 100; ++i)     R[i] = R[i-1] + (i / 10) - (i % 10); } int sumNumber( gint_t num ) {   int rm[20], sum = 0, sign = 1;   unsigned int digits = 0;   do   {     rm[digits++] = (int) (num % 10);     num /= 10;   }   while( num > 0 );   while( digits > 0 )   {     if( sign > 0 ) sum += rm[digits-1]; else sum -= rm[digits-1];     sign = -sign;     digits--;   }   return sum; } gint_t sumEvenPartial( gint_t num ) {   gint_t A = num / 100;   int B = (int) (num % 100);   if( A == 0 ) return R[B] + 45;   return sumEvenPartial(A) * 100 - sumNumber( A ) * (99 - B) + R[B]; } int main( void ) {   unsigned int digits;   gint_t num;   rFill();   for( num = 99; num <= 99999999; num = 100 * num + 99)     printf( "Sum(%" GPRINT "d) = %" GPRINT "d\n", num, sumEvenPartial( num ));   return 0; } Если это всё ещё интересно Альтаиру, то расскажу, как она получилась.

Автор: konshyn 11.3.2015, 11:34

feodorv, мне интересно. Напишите, пожалуйста

Автор: altairaimenov 11.3.2015, 18:20

Цитата(feodorv @  11.3.2015,  03:28 ) Если это всё ещё интересно Альтаиру, то расскажу, как она получилась. Я не откажусь от обьяснений)

Автор: feodorv 12.3.2015, 00:03

Да, давайте сейчас, а то потом всё забудется... Несколько предварительных замечаний. Для чисел порядка 10^15 int не годится, так как он, скорее всего, 32-х битный. Нужны 64-х битные целые, это, например, long long в никсах или __int64 в виндах. Нужно так же правильно выводить эти числа на печать. Поэтому в программе введен тип (можно и через typedef) gint_t для 64-х битных (знаковых) целых и соответствующий макрос для функции печати printf - GPRINT. Так, для виндов можно записать: Код #define gint_t __int64 #define GPRINT "I64" Но для наших целей (разработки алгоритма) можно временно ограничиться простым int. Все соображения будут применяться для знакоинвертированного ряда +0-1+2-3+..., извините за занудство))) Придется вводить несколько надоедливых обозначений. Первым обозначением будет S(X..Y), означающее знакопеременную сумму цифр всех чисел от X до Y включительно. Мы, соответственно, ищем S(0...N). Второе обозначение - T(X) (где X - некое натуральное число), означающее знакопеременную сумму его цифр (то есть только этого числа). В программе ей отвечает функция sumNumber(). Тогда наш искомый ряд для числа N (возьмем его достаточно большим) запишется таким образом: Код S(0..N) =  + T(0) - T(1) + ... - T(9) + T(10) + T(11) + ... + T(99)  + T(100) - T(101) + ... - T(999) + ... +/- T(N) Понятно, что T(X) будет идти с плюсом для четноцифровых чисел и для четных нечетноцифровых чисел; и с минусом для нечетных нечетноцифровых чисел (    ). То есть знакопеременная природа у чисел с четным числом цифр и нечетным числом различна, приходится рассматривать их суммы отдельно. Как совершенно справедливо указал konshyn, частичные суммы Код S(0..9) = T(0) - T(1) + ... - T(9) S(10..99) = T(10) + T(11) + ... + T(99) ... можно заранее посчитать и забыть до этапа финального суммирования. (Удивительно, конечно, что они очень друг на друга похожи). При этом достаточно легко можно доказать, что Код S(1000..9999) = 100 * S(10..99) S(100000..999999) = 100 * S(1000..9999) ... S(100..999) = (1000-100) / 2 *(-1) S(10000..99999) = (100000-10000) / 2 *(-1) ... То есть проблем в вычислении этих частичных сумм нет никаких (вплоть до любого порядка). В принципе, в окончательной программе можно хранить массив значений этих сумм, а можно и уже просуммированные значения этих сумм, где индекс массива означает число цифр в последнем просуммированном числе 99...9: Код P[0] = S(0..9) P[1] = S(0..9) + S(10..99) P[2] = S(0..9) + S(10..99) + S(100..999) ... А можно всё и посчитать, это не долго))) Остается найти неполную частичную сумму S(10^(n-1)..N), где n - число цифр числа N. Здесь для нечетного n (то есть для нечетноцифровых чисел) все относительно просто, так как T(X) и T(X+1) в значительной степени уничтожают друг друга, а именно: Код T(2*M) - T(2*M+1) = -1 если в числе 2*M содержится нечетное число цифр. Таким образом, достаточно посчитать число пар, содержащихся в интервале 10^(n-1)..N, умножить на -1, и, если N - число чётное, добавить T(N). (Не проверял, но по идее должно работать)))) Для четноцифровых чисел простого решения не нашел. Поначалу казалось, что можно рассмотреть ряд от 0 до N, где все числа в ряду имеют n-цифр, то есть если их в числе меньше, то к нему слева приписываются нули, например для числа 1203: Код + 0 - 0 + 0 - 1 + 0 - 0 + 0 - 2 ... + 0 - 9 + 9 - 9 + 1 - 0 + 0 - 0 + 1 - 0 + 0 - 1 ... + 1 - 2 + 0 - 0 + 1 - 2 + 0 - 1 + 1 - 2 + 0 - 2 + 1 - 2 + 0 - 3 то, поскольку известно число строк в получившейся таблице, то можно исхитриться посчитать число цифр одного достоинства в каждом столбце, потом все правильно просуммировать, потом вычесть добавленный верхний треугольник, получив искомое. Мозгов на идею не хватило, зато родилась иная идея, о которой ниже.

Автор: feodorv 12.3.2015, 01:34

Если представить четноцифровое число N в виде 100*A+B, то так и хочется написать Код Т(100*A+B) = T(A) + T(B) Увы, формула не совсем верная, так как число B может быть одноциферным, и тогда его слева нужно дополнить нулём (который в сумме как раз пойдёт со знаком плюс). Ничего страшного, для таких двухциферных чисел введём новое обозначение T2(B), где В - либо двуциферное число, либо одноциферное, но дополненное нулём слева. Тогда формула приобретает вид: Код Т(100*A+B) = T(A) + T2(B) А теперь эту формулу будем суммировать от 10^(n-1) до N.  Возьмем для примера число 8765 (для него A=87, B=65). Понятно, что  Код S(1000..8765) = S(1000..8699) + S(8700..8765) То есть неполную частичную сумму мы разбили на две суммы - основную (в которой участвуют пачки по 100 штук чисел: Код T(1000) + T(1001) + ... + T(1099) + T(1100) + T(1101) + ... + T(1199) + ... T(8600) + T(8601) + ... + T(8699) и остаточную (с неполной сотней чисел). С учетом вышеприведенной формулы основная сумма приобретает вид: Код SUM(A:10..86) SUM(B:0..99) T(100*A+B) = SUM(A:10..86) SUM(B:0..99) (T(A) + T2(B)) = {SUM(A:10..86) SUM(B:0..99) T(A)} + {SUM(A:10..86) SUM(B:0..99) T2(B)} =  100 * {SUM(A:10..86) T(A)} + 77 * {SUM(B:0..99) T2(B)} Удивительно, но в сумме SUM(A:10..86) T(A) мы неожиданно узнаем S(10..86) (то есть неполную частичную сумму для числа, которое в 100 меньше изначального, и ещё на единицу, это важно). А вторая сумма оказывается равной 0! То есть суммирование сотнями приводит нас к редукции задачи   Здесь мы, пожалуй впервые сталкиваемся с рядом Код T2(0) + T2(1) + ... + T2(99) =  + 0 - 0 + 0 - 1 + 0 - 2 + ... + 0 - 9 + 1 - 0 + 1 - 1 + 1 - 2 + ... + 1 - 9 + 2 - 0 + 2 - 1 + 2 - 2 + ... + 2 - 9 ... + 9 - 0 + 9 - 1 + 9 - 2 + ... + 9 - 9 полная сумма которого равна 0))) В дальнейшем нам придётся иметь дело с неполной суммой этого ряда, поэтому давайте на нём остановимся поподробнее. Обозначим через R(X) (где X - натуральное число, меньшее 100) следующую сумму Код R(X) = T2(0) + T2(1) + ... + T2(X) Мы уже убедились, что R(99) равно 0. Для числа X, представленного в виде 10*a+b (здесь a и b - цифры двухциферного числа X), аналитически можно найти значение  Код R(10*a+b) = (2*a - b) * (b+1) / 2  -  5 * a * (10 - a) Что легко проверить программным путем. Но, проще, всё же, определить массив R[100] и заполнить его в начале программы, что и делает функция rFill(). Тем не менее, у нас есть ещё остаточная сумма, давайте её найдём: Код S(8700..8765) =  SUM(B:0..65) T(8700 + B) = SUM(B:0..65) (T(87) + T2(B)) = {SUM(B:0..65) T(87)} + {SUM(B:0..65) T2(B)) = 66 * T(87) + R(65) Итого: Код S(1000..8765) = 100 * S(86) + 66 * T(87) + R(65) В общем случае, если представить четноцифровое число N в виде 100*A+B, то получается так: Код S(100*A+B) = 100 * S(A-1) + (B+1) * T(A) + R(B) Вот так))) Тем не менее, эта редукционная формула имеет один изъян, а именно значение A-1. Дело в том, что если A представляет собой степень десятки (например, 1000), то A-1 становиться нечетноцифровым числом (для нашего примера - 999), что нарушает редукцию, так как мы хотим, чтобы все числа для S() были бы четноцифровые. Программно этот случай можно обойти (так как основная сумма в этом случае просто равна 0), но, честно говоря, выглядит это не очень красиво. Хотелось бы избавиться от -1 для A, и это возможно, если в основную сумму впихнуть 100 следующих чисел, а потом вычесть то лишнее, что мы этим добавили: Код S(1000..8765) = S(1000..8799) - S(8766..8799) С суммой по сотням проблем нет, а вот с остатком придётся разобраться: Код S(8766..8799) =  SUM(B:66..99) T(8700 + B) = SUM(B:66..99) (T(87) + T2(B)) = {SUM(B:66..99) T(87)} + {SUM(B:66..99) T2(B)) = (99-66+1) * T(87) + R(99) - R(65) =  (99-65) * T(87) - R(65) Теперь, в общем случае, имеем Код S(100*A+B) = 100 * S(A) - (99-B) * T(A) + R(B) Любопытно, что R(B) опять идёт с плюсом)))

Автор: feodorv 12.3.2015, 01:59

Ясно, что в конце концов мы доредуцируемся до двухциферных чисел. Иными словами, в конце редукции мы должны вычислить сумму S(10..K), где К - двухциферное число, состоящее из первых двух цифр числа N. Казалось бы, эту сумму и так легко найти простым циклом, но понятно, что ряд S(10..K) - это кусок R(K), в котором отброшены первые 10 членов: Цитата + 0 - 0 + 0 - 1 + 0 - 2 + ... + 0 - 9 + 1 - 0 + 1 - 1 + 1 - 2 + ... + 1 - 9 + 2 - 0 + 2 - 1 + 2 - 2 + ... + 2 - 9 ... + 9 - 0 + 9 - 1 + 9 - 2 + ... + 9 - 9 Поэтому  Код S(10..K) = R(K) - T2(0) - T2(1) - .. - T2(9) = R(K) - R(9) = R(K) + 45 То есть имея массив R[], мы легко можем вычислить последнюю сумму S(10..K). Объединим все полученное в одну функцию, которая индуктивно будет вызывать сама себя: Код gint_t sumEvenPartial( gint_t num ) {   // Разобьем число num на составные части 100 * A + B   gint_t A = num / 100;   int B = (int) (num % 100);   // Если число num меньше 100 (то есть A == 0), то мы дошли до конца редукции   if( A == 0 ) return R[B] + 45;   // Иначе применим редукционную формулу   return sumEvenPartial(A) * 100 - sumNumber( A ) * (99 - B) + R[B]; } Как-то так, как сумел, так и объяснил, прошу прощения за графоманство

Автор: altairaimenov 12.3.2015, 18:07

Спасибо, то что мне надо было, я понял!)

Автор: altairaimenov 13.3.2015, 11:52

Спасибо!

Автор: sQu1rr 18.3.2015, 17:32

Цитата(feodorv @  11.3.2015,  21:03 ) Для четноцифровых чисел простого решения не нашел Забавно потому что это первое до чего я догодался когда решал эту задачу. К сожалению не хватило времени дописать полное решение (подвела смекалка с 5 45 450 ...) и уехал в отпуск не решив. В любом случае поделюсь своим решением для чисел с четным кол-вом цифр. Будем считать сумму цифр ТОЛЬКО n-значных чисел до (включая) искомое число. Возьмем например 1254. Будем брать каждую цифру отдельно, всего их 4. Начнем с конца для простоты 4: цифры от 1 до 9 (сумма которых 45) встречались 25 раз (от 1000 до 1250). еще встречались 1, 2, 3, 4 по одному разу 5: цифры от 1 до 9 встречались 2 раза. в этот раз их сумма 450, так как для каждой цифры имеем 10 вариаций (цифра справо). еще 1 - 10 раз, 2 - 10 раз, 3 - 10 раз, 4 - 10 раз, и 5 - 5 раз (5 потому что 50 51 52 53 54) 2: цифры от 1 до 9 встречались 0 раз (но если бы встречались нужно было бы умножить на 100), плус 1 * 100 и 2 * 55 1: 0 * 45 * 1000 + 1 * 255 Вот для наглядности 25 * 45 + 1 + 2 + 3 + 4                                1135 2 * 45 * 10 + 1 * 10 + 2 * 10 + 3 * 10 + 4 * 10 + 5 * 5        1025 0 * 45 * 100 + 1 * 100 + 2 * 55                        210 0 * 45 * 1000 + 1 * 255                                255 мы знаем что числы стоящие на четных местах будут в плюсе (ну или в минусе, это можно исправить, но для этого решения скажем что в плюсе), а нечетные в минусе. получим сумму 65, что есть верное решение. (ну и останется посчитать 0..999 по формуле 5 45 450 ... что бы получить полное решение, но это я здесь не обсуждаю) В общем виде формула такая A = [1,2,5,4] B = [0,0,2,5,4,1] // число минус первое n-значное число, в этом случае 1000 и с еденицой на конце и с 0 вначале пусть N это функция которая берет цифры и превращает их в число, n - кол-во знаков минус 1, i = 0.., j = n-i, sign = 1 если i честное и -1 если нечетное sum += sign * (N(B[0..j]) * 45 * 10^i + sum(0..A[j]-1) * 10^i + (A[j])*(N(B[j+2..n+2])+1))

Автор: feodorv 18.3.2015, 19:54

sQu1rr, спасибо! Но надо переварить

Автор: sQu1rr 18.3.2015, 19:59

Учитывая что я забываю русский, и плохо объясняю, я предпологаю что переварить придется не алгоритм а то что я написал  Но я всегда буду рад вопросам. Если будет время приведу рабочий код

Автор: sQu1rr 20.3.2015, 16:39

Код, как обещал Код inline int sumDigits(int_t n) // сумма цифр {     auto sum = 0;     for (auto s = 1; n; n /= 10, s = -s) sum += s * (n % 10);     return sum; }   inline int_t sub(int dig) // первое {dig}-значное число (для 4 = 1000, для 1 = 0) {     return dig == 1 ? 0 : static_cast<int_t>(std::pow(10.0, dig - 1)); } inline int_t odd(int_t n, int dig) // решаем нечетноцифренную последовательность {     // в точности как описано на первой странице темы     return (n - sub(dig)) / 2 + ((n % 2) ? 1 : -sumDigits(n)); } inline int_t even(int_t n, int dig) // решаем четноцифренную последовательность {     // как я описал в предадущем посте. сократил названия переменных для сохранения места     // похоже на месиво, но мне доставляет     // sum - конечная сумма     // b - число состоящее из цифр правее текущей (правее d). так как начинаем справа, равна 0     // z - множитель, равен 1 дня самой правой цифры и увелечивается на каждом шагу в 10 раз     // x - число состоящее из цифр левее текущей (левее d). так как начинаем справа равна числу без последней цифры.     // число x на самом деле на sub(dig) меньше настоящего числа. все это описано в предыдущем посте. грубо говоря самая левая цифры - меньше на 1     auto sum = 0LL, b = 0LL, z = 1LL, x = (n - sub(dig)) / 10;     for (auto s = -1; n; n /= 10, s = -s, x /= 10, z *= 10) {         int d = n % 10; // текущая цифра         // sign * ((N(B[0..j]) * 45 + sum(0..A[j]-1)) * 10^i + (A[j])*(N(B[j+2..n+2])+1))         sum += s * ((x * 45 + (d * (d - 1) / 2)) * z + d * (b + 1));         b += d * z; // добавляем к b (слева) просмотренную цифру     }     return sum; } int solve(int_t n) // решаем для n {     auto sum = 0;     auto dig = static_cast<int>(std::floor(std::log10(n))) + 1;     if (dig > 1) sum = 5; // первая сумма в последовательности (какое-то прямо исключение, бесит)     if (dig > 2) for (int i = 2, a = 45; i < dig; ++i, a *= 10) sum += a; // тут все понятно     // выбираем четное либо нечетное решение и прибавляем к сумме     return sum + ((dig % 2) ? odd(n, dig) : even(n, dig)); } И вот проверка. Хотелось бы сравнить производительность вашего решения с моим, к сожалению нету под рукой компилятора, код писал в блакноте, и проверял в ideone. http://ideone.com/KQp8c7

Автор: feodorv 20.3.2015, 18:22

Цитата(sQu1rr @  20.3.2015,  16:39 )    if (dig > 2) for (int i = 2, a = 45; i < dig; ++i, a *= 10) sum += a; Здесь что-то должно быть знакопеременным, не? Цитата(sQu1rr @  20.3.2015,  16:39 ) Хотелось бы сравнить производительность вашего решения с моим Я лично особого смысла в этом не вижу, разница должна быть минимальной. Цитата(sQu1rr @  20.3.2015,  16:39 )     return (n - sub(dig)) / 2 + ((n % 2) ? 1 : -sumDigits(n)); А я думал так: Код    return (n +1 - sub(dig)) / 2 + ((n % 2) ? 0 : -sumDigits(n));    Результат, даваемый функцией even() проверю попозже)))

Автор: sQu1rr 20.3.2015, 18:43

Цитата(feodorv @  20.3.2015,  15:22 ) Здесь что-то должно быть знакопеременным, не? А. вот в чем моя ошибка  я считаю сумму цифр с конца числа. весело, весело. Тоже очень думал чот должно быть знакопеременным. Цитата(feodorv @  20.3.2015,  15:22 ) А я думал так: Не вижу принципиальной разницы. Код исправлю, отпишусь позже ЗЫ Цитата(feodorv @  20.3.2015,  15:22 ) Я лично особого смысла в этом не вижу, разница должна быть минимальной. Вот мне и интересно. В моем случае просматривается каждая цифра, в вышем через 2, но у вас больше вычесление. Просто интересно.

Автор: sQu1rr 20.3.2015, 19:00

Исправляюсь Код inline int sumDigits(int_t n, int dig) {     auto even = !(dig % 2);     auto sum = 0;     for (auto s = 1; n; n /= 10, s = -s) sum += s * (n % 10);     return even ? -sum : sum; } inline int_t sub(int dig) {     return dig == 1 ? 0 : static_cast<int_t>(std::pow(10.0, dig - 1)); } inline int_t odd(int_t n, int dig) {     return (n - sub(dig)) / 2 + ((n % 2) ? 1 : -sumDigits(n, dig)); } inline int_t even(int_t n, int dig) {     auto sum = 0LL, b = 0LL, z = 1LL, x = (n - sub(dig)) / 10;     for (auto s = -1; n; n /= 10, s = -s, x /= 10, z *= 10) {         int d = n % 10;         sum += s * ((x * 45 + (d * (d - 1) / 2)) * z + d * (b + 1));         b += d * z;     }     return sum; } int solve(int_t n) {     auto sum = 0LL;     auto dig = static_cast<int>(std::floor(std::log10(n))) + 1;     if (dig > 1) sum = 5;     if (dig > 2) for (int i = 2, a = 45, s = -1; i < dig; ++i, a *= 10, s = -s) sum += a * s;     return sum + ((dig % 2) ? odd(n, dig) : -even(n, dig)); } http://ideone.com/KQp8c7 Цитата(feodorv @  20.3.2015,  15:22 ) Результат, даваемый функцией even() проверю попозже))) уже проверил, все четко ;) всмысле вывод такой же как и с вашей функцией. Проверил все числа до 100000000. И судя по всему ваша функция на 11% быстрее.

Автор: feodorv 22.5.2019, 12:47

Ссылка на проблему: https://www.spoj.com/problems/KPSUM/.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)