Добрый день! Нам даётся число 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++

Это сообщение отредактировал(а) altairaimenov - 5.3.2015, 20:11

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

Дело в том что N = 10^15. Тривиальный алгоритм я могу написать,но он до 10^7.Я просто искал форумы где я могу просить помощи в нерешенных мной задач.Занимаюсь я не ради кого-то,а ради себя. Думаю понятно   

Это сообщение отредактировал(а) altairaimenov - 5.3.2015, 20:12

Здесь есть раздел - алгоритмы, там помогают именно с ними. Но не надо уже дублировать. Есть какиенибудь идеи - как решить?

Обыная задачка на последовательности:
суммы:
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, или как Вы там считаете.

Я думаю, что дальше сами справитесь с анализом цифр.

Как-то я не уверен, что здесь будет знакопеременный ряд. В обоснование приведу такое соображение.

Рассмотрим знакоинвертированный ряд (для удобства):

Тогда в подпоследовательности 0..9 будет четное число членов, и 1 от числа 10 пойдет со знаком +. В подпоследовательности 10..99 опять-таки будет четное число членов, и 1 от числа 100 пойдет со знаком +. В подпоследовательности 100..999 опять-таки будет четное число членов, и 1 от числа 1000 пойдет со знаком +. И так далее.



Для чисел с нечетным числом цифр всё вообще элементарно.

1) Прежде, чем написать, я проверил:)
2) Знакоинвертированный ряд здесь не может быть примером, т.к. автор написал, как выглядит последовательность.





Да:)

Вот это одобряю!   

Ну тогда частичные суммы имеют иной вид:


А общая сумма такая: 5 - (45 - 450 + 4500 - 45000)  



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

Если что, то я тоже проверял)))

Вы правы, более удобное решение за Вами:)

konshyn, да там удобства кот наплакал, но все же)))

Благодаря тому, что сумма ряда
равна нулю, для чисел с четным числом цифр возможно рассчитать частичную сумму от 100..0 до abc..z (а это то, что не доставало))) путем редуцирования начального числа делением на 100 (что подразумевает индукцию). С учетом некоторых хитростей программа для вычисления частичных сумм произвольных четноцифровых (черт, как это одним словом сказать?) чисел приобрела вид:

Если это всё ещё интересно Альтаиру, то расскажу, как она получилась.

Это сообщение отредактировал(а) feodorv - 11.3.2015, 04:08

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

Я не откажусь от обьяснений)

Да, давайте сейчас, а то потом всё забудется...

Несколько предварительных замечаний.

• Для чисел порядка 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

  
  то, поскольку известно число строк в получившейся таблице, то можно исхитриться посчитать число цифр одного достоинства в каждом столбце, потом все правильно просуммировать, потом вычесть добавленный верхний треугольник, получив искомое. Мозгов на идею не хватило, зато родилась иная идея, о которой ниже.

 

Если представить четноцифровое число N в виде 100*A+B, то так и хочется написатьУвы, формула не совсем верная, так как число B может быть одноциферным, и тогда его слева нужно дополнить нулём (который в сумме как раз пойдёт со знаком плюс). Ничего страшного, для таких двухциферных чисел введём новое обозначение T2(B), где В - либо двуциферное число, либо одноциферное, но дополненное нулём слева. Тогда формула приобретает вид:
А теперь эту формулу будем суммировать от 10^(n-1) до N. 


Возьмем для примера число 8765 (для него A=87, B=65). Понятно, что 

То есть неполную частичную сумму мы разбили на две суммы - основную (в которой участвуют пачки по 100 штук чисел:
и остаточную (с неполной сотней чисел).


С учетом вышеприведенной формулы основная сумма приобретает вид:
Удивительно, но в сумме SUM(A:10..86) T(A) мы неожиданно узнаем S(10..86) (то есть неполную частичную сумму для числа, которое в 100 меньше изначального, и ещё на единицу, это важно). А вторая сумма оказывается равной 0! То есть суммирование сотнями приводит нас к редукции задачи  


Здесь мы, пожалуй впервые сталкиваемся с рядом
полная сумма которого равна 0))) В дальнейшем нам придётся иметь дело с неполной суммой этого ряда, поэтому давайте на нём остановимся поподробнее. Обозначим через R(X) (где X - натуральное число, меньшее 100) следующую сумму
Мы уже убедились, что R(99) равно 0. Для числа X, представленного в виде 10*a+b (здесь a и b - цифры двухциферного числа X), аналитически можно найти значение 

Что легко проверить программным путем. Но, проще, всё же, определить массив R[100] и заполнить его в начале программы, что и делает функция rFill().


Тем не менее, у нас есть ещё остаточная сумма, давайте её найдём:Итого:


В общем случае, если представить четноцифровое число N в виде 100*A+B, то получается так:
Вот так))) Тем не менее, эта редукционная формула имеет один изъян, а именно значение A-1. Дело в том, что если A представляет собой степень десятки (например, 1000), то A-1 становиться нечетноцифровым числом (для нашего примера - 999), что нарушает редукцию, так как мы хотим, чтобы все числа для S() были бы четноцифровые. Программно этот случай можно обойти (так как основная сумма в этом случае просто равна 0), но, честно говоря, выглядит это не очень красиво. Хотелось бы избавиться от -1 для A, и это возможно, если в основную сумму впихнуть 100 следующих чисел, а потом вычесть то лишнее, что мы этим добавили:
С суммой по сотням проблем нет, а вот с остатком придётся разобраться:Теперь, в общем случае, имеемЛюбопытно, что R(B) опять идёт с плюсом)))

Ясно, что в конце концов мы доредуцируемся до двухциферных чисел. Иными словами, в конце редукции мы должны вычислить сумму S(10..K), где К - двухциферное число, состоящее из первых двух цифр числа N. Казалось бы, эту сумму и так легко найти простым циклом, но понятно, что ряд S(10..K) - это кусок R(K), в котором отброшены первые 10 членов:
Поэтому 
То есть имея массив R[], мы легко можем вычислить последнюю сумму S(10..K).


Объединим все полученное в одну функцию, которая индуктивно будет вызывать сама себя:

Как-то так, как сумел, так и объяснил, прошу прощения за графоманство   

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

Спасибо!  

Забавно потому что это первое до чего я догодался когда решал эту задачу. К сожалению не хватило времени дописать полное решение (подвела смекалка с 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))


Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 16:47

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

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

Код, как обещал


И вот проверка. Хотелось бы сравнить производительность вашего решения с моим, к сожалению нету под рукой компилятора, код писал в блакноте, и проверял в ideone.
http://ideone.com/KQp8c7

Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 16:57

Здесь что-то должно быть знакопеременным, не?



Я лично особого смысла в этом не вижу, разница должна быть минимальной.



А я думал так:
  


Результат, даваемый функцией even() проверю попозже)))

Это сообщение отредактировал(а) feodorv - 20.3.2015, 18:23

А. вот в чем моя ошибка  я считаю сумму цифр с конца числа. весело, весело. Тоже очень думал чот должно быть знакопеременным.


Не вижу принципиальной разницы.

Код исправлю, отпишусь позже

ЗЫ


Вот мне и интересно. В моем случае просматривается каждая цифра, в вышем через 2, но у вас больше вычесление. Просто интересно.

Исправляюсь

http://ideone.com/KQp8c7


уже проверил, все четко ;) всмысле вывод такой же как и с вашей функцией. Проверил все числа до 100000000.
И судя по всему ваша функция на 11% быстрее.

Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 19:47

Ссылка на проблему: SPOJ KPSUM.