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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Вопрос по задаче 
:(
    Опции темы
kolesnle
Дата 11.12.2013, 15:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Упертый сишник
*


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

Репутация: нет
Всего: нет
Условие(Задача D) В смысле как показано на рисунке? Что это за замкнутые области?
PM MAIL   Вверх
bsa
Дата 11.12.2013, 15:47 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196
Подозреваю, что тут под областями понимаются "дырки" в окружностях цифр. Например, только цифры 6, 8, 9 и 0 содержат эти "дырки" и "окружности". Таким образом, если число N меньше 6, то число областей будет 0. Если N=10, то число областей будет 5 (8 - содержит две области)...


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
kolesnle
Дата 11.12.2013, 15:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Упертый сишник
*


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

Репутация: нет
Всего: нет
Цитата(bsa @  11.12.2013,  15:47 Найти цитируемый пост)
Подозреваю, что тут под областями понимаются "дырки" в окружностях цифр. Например, только цифры 6, 8, 9 и 0 содержат эти "дырки" и "окружности". Таким образом, если число N меньше 6, то число областей будет 0. Если N=10, то число областей будет 5 (8 - содержит две области)... 

Интересная версия. Попробую smile
PM MAIL   Вверх
feodorv
Дата 11.12.2013, 16:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(kolesnle @  11.12.2013,  16:55 Найти цитируемый пост)
Интересная версия.

По-моему, единственно верная версия))))




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


Упертый сишник
*


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

Репутация: нет
Всего: нет
Цитата(feodorv @  11.12.2013,  16:08 Найти цитируемый пост)
По-моему, единственно верная версия))))

Действительно smile Решилось) Единственное, пугает ограничение 10^18, очень пугает...
PM MAIL   Вверх
bsa
Дата 11.12.2013, 17:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196
от 1 до 10 - 5 областей
от 1 до 100 - 55 областей
от 1 до 1000 - 555 областей
...
надеюсь, я не просчитался


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
feodorv
Дата 11.12.2013, 19:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(kolesnle @  11.12.2013,  17:30 Найти цитируемый пост)
Единственное, пугает ограничение 10^18, очень пугает... 

Совершенно не должно))) Во-первых, 10^16, что укладывается в 64 бита, во-вторых, эта задача не решается перебором, а просто определением числа вхождений заданной цифры в последовательность, в-третьих, как уже указал bsa, всё это можно ещё и заоптимизировать))))


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


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(bsa @  11.12.2013,  18:39 Найти цитируемый пост)
от 1 до 10 - 5 областей
от 1 до 100 - 55 областей
от 1 до 1000 - 555 областей

А у меня чисто теоретически получился такой ряд:
Цитата

от 1 до 10 => 1*5 - 1 +1 областей
от 1 до 100 => 20*5 - 11 + 2 областей
от 1 до 1000 => 300*5 - 111 + 3 областей

 smile 


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


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196
Цитата(feodorv @  12.12.2013,  00:45 Найти цитируемый пост)
А у меня чисто теоретически получился такой ряд:
Ну значит я просчитался. Я особо долго не думал над этим.


--------------------
Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.
PM   Вверх
feodorv
Дата 12.12.2013, 10:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(bsa @  12.12.2013,  11:14 Найти цитируемый пост)
Ну значит я просчитался. Я особо долго не думал над этим.

Не знаю. Нужно проверить программно)))

kolesnle, как там дела?


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


Упертый сишник
*


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

Репутация: нет
Всего: нет
Цитата(feodorv @  12.12.2013,  10:42 Найти цитируемый пост)
kolesnle, как там дела? 

Нормально. Пока все выходит

Добавлено через 3 минуты и 23 секунды
Цитата(feodorv @  11.12.2013,  23:45 Найти цитируемый пост)
от 1 до 10 => 1*5 - 1 +1 областей
от 1 до 100 => 20*5 - 11 + 2 областей
от 1 до 1000 => 300*5 - 111 + 3 областей

Правильно smile А почему так получилось?
PM MAIL   Вверх
feodorv
Дата 12.12.2013, 16:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 12
Всего: 45
Цитата(kolesnle @  12.12.2013,  15:52 Найти цитируемый пост)
А почему так получилось? 

А давайте я Вам процитирую (лучше я всё равно не сформулирую) из книги Шкляровский, Ченцов, Яглом "Избранные задачи и теоремы элементарной математики", 1978 года издания, задача номер 104:
Цитата

Сколько и каких цифр понадобится для того, чтобы записать все целые числа от 1 до 100 000 000 включительно?

Ответ:
Цитата

Рассмотрим сначала все целые числа от 0 до 99 999 999; при этом те из этих чисел, которые имеют меньше восьми цифр, дополним слева нулями так, чтобы они стали восьмизначными. Мы будем иметь 100 000 000 восьмизначных чисел, для записи которых нам потребуется, очевидно, 800 000 000 цифр. При этом здесь каждая из 10 цифр будет использована равное число раз, поскольку все они совершенно равноправны (нуль может стоять на первом месте точно так же, как и всякая другая цифра). Следовательно, каждая цифра будет у нас использована 80 000 000 раз.

Теперь подсчитаем, сколько здесь будет лишних нулей (т.е. нулей, приписанных спереди чисел, имеющих меньше восьми цифр). Однозначных чисел (не считая нуля) имеется всего девять, двузначных чисел 99-9=90, трехзначных чисел 999-99=900, и т.д. Так как к однозначной цифре мы приписали слева семь нулей (не считая цифр первого числа, которое у нас записывалось так: 00 000 000) будет равно:

7*9 + 6*90 + 5*900 + 4*9000 + 3*90000 + 2*900000 + 1*9000000 = 11 111 103

Припишем теперь 1 слева первого числа 00 000 000; при этом мы получим все целые числа от 1 до 100 000 000. Мы видим, что для записи этих чисел требуется 80 000 000 двоек, троек, и т.д. до девяток, 80 000 001 единиц (одну лишнюю единицу мы приписали слева числа 00 000 000) и 80 000 000 - 11 111 103 = 68 888 897 нулей.

Все это наводит на размышления по поводу 10^16. В конце концов всё сводится к циклу по разрядности числа N (то есть максимум 16 итераций!) при аккуратном программировании. 

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


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

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

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

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

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

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




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


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

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