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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Ещё одна задача... К экспертам спортивного программирования 
V
    Опции темы
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   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

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

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

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

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


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

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


 




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


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

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