Модераторы: JackYF, bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Ещё одна задача... К экспертам спортивного программирования 
V
    Опции темы
altairaimenov
Дата 5.3.2015, 19:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 3.3.2015

Репутация: нет
Всего: нет



Добрый день! Нам даётся число 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
PM MAIL   Вверх
sQu1rr
Дата 5.3.2015, 19:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



Ну а что у вас не получается то? мы тут все такие помогаем, а то я смотрю вы обрадовались что за вас все вчера решили smile
PM MAIL Skype GTalk   Вверх
altairaimenov
Дата 5.3.2015, 20:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 3.3.2015

Репутация: нет
Всего: нет



Цитата(sQu1rr @ 5.3.2015,  19:16)
Ну а что у вас не получается то? мы тут все такие помогаем, а то я смотрю вы обрадовались что за вас все вчера решили smile

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

Это сообщение отредактировал(а) altairaimenov - 5.3.2015, 20:12
PM MAIL   Вверх
sQu1rr
Дата 6.3.2015, 12:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



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

Здесь есть раздел - алгоритмы, там помогают именно с ними. Но не надо уже дублировать. Есть какиенибудь идеи - как решить?
PM MAIL Skype GTalk   Вверх
konshyn
Дата 6.3.2015, 15:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 295
Регистрация: 19.9.2013

Репутация: нет
Всего: нет



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

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




--------------------
«Потому что ценность акта действия в этой стране возрастает в несколько раз».
PM MAIL Skype   Вверх
feodorv
Дата 7.3.2015, 15:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Цитата(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 Найти цитируемый пост)
числа с нечетным набором цифр

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
konshyn
Дата 9.3.2015, 11:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 295
Регистрация: 19.9.2013

Репутация: нет
Всего: нет



Цитата(feodorv @  7.3.2015,  15:10 Найти цитируемый пост)

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

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


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




Цитата(feodorv @  7.3.2015,  15:10 Найти цитируемый пост)
Для чисел с нечетным числом цифр всё вообще элементарно. 

Да:)


--------------------
«Потому что ценность акта действия в этой стране возрастает в несколько раз».
PM MAIL Skype   Вверх
feodorv
Дата 9.3.2015, 17:28 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Цитата(konshyn @  9.3.2015,  11:06 Найти цитируемый пост)
Прежде, чем написать, я проверил:)

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

Ну тогда частичные суммы имеют иной вид:
Цитата(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) smile 


Цитата(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).

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
konshyn
Дата 10.3.2015, 11:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 295
Регистрация: 19.9.2013

Репутация: нет
Всего: нет



Цитата(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).


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


--------------------
«Потому что ценность акта действия в этой стране возрастает в несколько раз».
PM MAIL Skype   Вверх
feodorv
Дата 11.3.2015, 03:28 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



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;
}


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

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
konshyn
Дата 11.3.2015, 11:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 295
Регистрация: 19.9.2013

Репутация: нет
Всего: нет



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


--------------------
«Потому что ценность акта действия в этой стране возрастает в несколько раз».
PM MAIL Skype   Вверх
altairaimenov
Дата 11.3.2015, 18:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 3.3.2015

Репутация: нет
Всего: нет



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


Я не откажусь от обьяснений)
PM MAIL   Вверх
feodorv
Дата 12.3.2015, 00:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



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

Несколько предварительных замечаний.
  • Для чисел порядка 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) будет идти с плюсом для четноцифровых чисел и для четных нечетноцифровых чисел; и с минусом для нечетных нечетноцифровых чисел ( smile  smile ). То есть знакопеременная природа у чисел с четным числом цифр и нечетным числом различна, приходится рассматривать их суммы отдельно.
  • Как совершенно справедливо указал 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

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
feodorv
Дата 12.3.2015, 01:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Если представить четноцифровое число 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! То есть суммирование сотнями приводит нас к редукции задачи smile 


Здесь мы, пожалуй впервые сталкиваемся с рядом
Код

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) опять идёт с плюсом)))


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
feodorv
Дата 12.3.2015, 01:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Ясно, что в конце концов мы доредуцируемся до двухциферных чисел. Иными словами, в конце редукции мы должны вычислить сумму 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];
}


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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
altairaimenov
Дата 12.3.2015, 18:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 3.3.2015

Репутация: нет
Всего: нет



Спасибо, то что мне надо было, я понял!)
PM MAIL   Вверх
altairaimenov
Дата 13.3.2015, 11:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 14
Регистрация: 3.3.2015

Репутация: нет
Всего: нет



Спасибо! smile 
PM MAIL   Вверх
sQu1rr
Дата 18.3.2015, 17:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



Цитата(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))


Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 16:47
PM MAIL Skype GTalk   Вверх
feodorv
Дата 18.3.2015, 19:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
sQu1rr
Дата 18.3.2015, 19:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



Учитывая что я забываю русский, и плохо объясняю, я предпологаю что переварить придется не алгоритм а то что я написал smile Но я всегда буду рад вопросам. Если будет время приведу рабочий код
PM MAIL Skype GTalk   Вверх
sQu1rr
Дата 20.3.2015, 16:39 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



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

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

Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 16:57
PM MAIL Skype GTalk   Вверх
feodorv
Дата 20.3.2015, 18:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



Цитата(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));

 smile 


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

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
sQu1rr
Дата 20.3.2015, 18:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



Цитата(feodorv @  20.3.2015,  15:22 Найти цитируемый пост)
Здесь что-то должно быть знакопеременным, не?

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

Цитата(feodorv @  20.3.2015,  15:22 Найти цитируемый пост)
А я думал так:

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

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

ЗЫ

Цитата(feodorv @  20.3.2015,  15:22 Найти цитируемый пост)
Я лично особого смысла в этом не вижу, разница должна быть минимальной.

Вот мне и интересно. В моем случае просматривается каждая цифра, в вышем через 2, но у вас больше вычесление. Просто интересно.
PM MAIL Skype GTalk   Вверх
sQu1rr
Дата 20.3.2015, 19:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13



Исправляюсь
Код

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% быстрее.

Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 19:47
PM MAIL Skype GTalk   Вверх
feodorv
Дата 22.5.2019, 12:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45



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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
Google
  Дата 17.7.2019, 01:21 (ссылка)  





  Вверх
Страницы: (2) [Все] 1 2 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.1661 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.