|
Модераторы: bsa |
|
altairaimenov |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 3.3.2015 Репутация: нет Всего: нет |
Спасибо, то что мне надо было, я понял!)
|
|||
|
||||
altairaimenov |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 3.3.2015 Репутация: нет Всего: нет |
Спасибо!
|
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Забавно потому что это первое до чего я догодался когда решал эту задачу. К сожалению не хватило времени дописать полное решение (подвела смекалка с 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 |
|||
|
||||
feodorv |
|
|||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
sQu1rr, спасибо!
Но надо переварить -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Учитывая что я забываю русский, и плохо объясняю, я предпологаю что переварить придется не алгоритм а то что я написал Но я всегда буду рад вопросам. Если будет время приведу рабочий код
|
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Код, как обещал
И вот проверка. Хотелось бы сравнить производительность вашего решения с моим, к сожалению нету под рукой компилятора, код писал в блакноте, и проверял в ideone. http://ideone.com/KQp8c7 Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 16:57 |
|||
|
||||
feodorv |
|
||||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Здесь что-то должно быть знакопеременным, не? Я лично особого смысла в этом не вижу, разница должна быть минимальной. А я думал так:
Результат, даваемый функцией even() проверю попозже))) Это сообщение отредактировал(а) feodorv - 20.3.2015, 18:23 -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||
|
|||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
А. вот в чем моя ошибка я считаю сумму цифр с конца числа. весело, весело. Тоже очень думал чот должно быть знакопеременным. Не вижу принципиальной разницы. Код исправлю, отпишусь позже ЗЫ
Вот мне и интересно. В моем случае просматривается каждая цифра, в вышем через 2, но у вас больше вычесление. Просто интересно. |
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Исправляюсь
http://ideone.com/KQp8c7 уже проверил, все четко ;) всмысле вывод такой же как и с вашей функцией. Проверил все числа до 100000000. И судя по всему ваша функция на 11% быстрее. Это сообщение отредактировал(а) sQu1rr - 20.3.2015, 19:47 |
|||
|
||||
feodorv |
|
|||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Ссылка на проблему: SPOJ KPSUM.
-------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
Правила форума "C/C++: Для новичков" | |
|
Запрещается! 1. Публиковать ссылки на вскрытые компоненты 2. Обсуждать взлом компонентов и делиться вскрытыми компонентами
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Для новичков | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |