Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
3 / 3 / 0
Регистрация: 26.11.2017
Сообщений: 30
1

Найти номер счета который нельзя будет получить из цифр числа X заданным способом

03.08.2018, 18:42. Показов 1044. Ответов 7
Метки нет (Все метки)

Ограничение по времени, сек 2
Ограничение по памяти, мегабайт 64

Банк «Кисловодск» переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Входные данные
Вводится натуральное число X без ведущих нулей (1 ≤ X < 10^1000)

Выходные данные
Выведите искомое N без ведущих нулей.
--------------------------------------------------------------------------------------------------------------
Добрый день!Помогите с идеей решения.(Решение должно работать линейно длине X,и не должно пробегаться по строке и увеличивать значение до тех пор,пока N не будет найдено).Спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.08.2018, 18:42
Ответы с готовыми решениями:

Выдавать номер того элемента массива который будет равен модулю введенного числа
Здравствуйте, нужно сделать программу которая будет выдавать номер того элемента массива который...

Найти номер элемента, который будет первый по порядку большим некоторого t
Помогите написать прогу на Си первый и второй члены последовательности равны 1, третий равен сумме...

Подсчитать сумму цифр последнего положительного числа, используя для счета суммы цифр функцию
С клавиатуры вводятся 15 чисел , посчитать сумму чисел последнего положительного числа ,...

Получить все натуральные числа меньше n, квадрат суммы цифр, который равен t
Помогите пожалуйста. Кому не сложно Даны натуральные числа n, t. Получить все натуральные числа...

7
Заблокирован
Эксперт C
04.08.2018, 08:55 2
Цитата Сообщение от Exiti Посмотреть сообщение
Помогите с идеей решения.
К = 0
Заводите 10 битовых счетчиков наличия.
Просматриваете строку Х и на каждую встреченную цифру взводите соответствующий счетчик.
Делаете это, пока все счетчики не взведутся.
Как взведутся: К++ и сбрасываем счетчики.
Искомое число состоит из К девяток + 1 Цифра. Эта цифра = номеру первого невзведенного счетчика.
Вот и все.

Добавлено через 2 минуты
ЗЫ. Использованная терминология не на 100 процентов общепринята. Если что непонятно - спрашивайте.

Добавлено через 2 минуты
ЗЗЫ. Ограничения что-то очень уж мягкие. Пробежаться, почти ничего не делая, по строке в 1000 символов за 2 сек? Да можно 100 раз это сделать!
1
20 / 20 / 4
Регистрация: 18.01.2017
Сообщений: 80
04.08.2018, 10:05 3
Вроде бы алгоритмом Байта в примере получается 29, а ответ 21. Или я что-то неправильно понял?

Я не программист и не уверен что нигде не напутал, но попробую составить алгоритм. На всякий случай проверьте не чушь ли я пишу. Это решение "в лоб", скорее всего есть способы проще и быстрее:
1. Пишем цифры числа в вектор. Создаём целую переменную n = 0 означающую число знаков без единицы в N.
2. Пробегаем вектор с конца до тех пор пока не встретится все 10 цифр.
3. Если такое место нашлось, запоминаем в другой вектор P номер элемента (или можно итератор элемента) и прибавляем к n единицу, затем повторяем п. 2.
4. Если такое место не находится то ищем максимальную цифру А перед последним записанным положением элемента.
5. Цифры в интервале между вхождением A из пункта 4 и предпоследним запомненным положением (или концом исходного числа если мы запомнили в P меньше 2-х положений числа) образуют некоторое число B, запишем его как другой вектор цифр.
6. Максимальное число k которое можно составить из B "банковским" методом не меньше A*10 +9 и не больше A*10 +18. Находим его перебором (10 значений).
7. N состоит из k и (n-1) -х девяток если n > 1, или равно k если n < 2.

Добавлено через 20 минут
Извините, я неточно выразился в п. 5 и п.3, уточню: B состоит из А и цифр до предпоследнего запомненного положения в P. Например, при Х = 120134567891234567890, B = 12013456789. При этом в P запоминаются положения 120134567891234567890.
2
Заблокирован
Эксперт C
04.08.2018, 11:48 4
Цитата Сообщение от algrigor Посмотреть сообщение
Вроде бы алгоритмом Байта в примере получается 29, а ответ 21.
Да, вы почти правы. Для Х=12013456789 ответ в самом деле 22, а по моему алгоритму получается 90. Не все учел, однако.
В самом деле мой алгоритм дает некоторую верхнюю оценку для этого минимального числа. Чтобы получить точное значение, его надо модифицировать. Подумать надо....

Добавлено через 11 минут
Цитата Сообщение от algrigor Посмотреть сообщение
попробую составить алгоритм.
Весьма похоже на правду.
Но я бы разбил Х на куски, в каждом из которых присутствуют все 10 цифр. Значность числа n - количество этих кусков(обозначим K)+1
Ясно, что любое число значности K получить можно. Значит n имеет значность K+1. А вот дальше надо колдовать над последним куском и "хвостом". Если я опять чего не напутал...
2
20 / 20 / 4
Регистрация: 18.01.2017
Сообщений: 80
04.08.2018, 12:48 5
Цитата Сообщение от Байт Посмотреть сообщение
ответ в самом деле 22
Спасибо что подсказали, я тоже ошибся, причём три раза (как минимум).
1 ошибка. Невнимательно прочитал условие и искал последнее из ряда идущих подряд чисел которые можно получить из исходного числа, следовательно если бы не было других ошибок к моему ответу нужно было бы добавить единицу (т. е. N состояло из k+1 и (n-1) нулей если n > 1, либо равно k+1 если n < 2).
2 ошибка. В п. 4 написал "Если такое место не находится то ищем максимальную цифру А перед последним записанным положением элемента", когда нужно искать максимальную цифру А перед последним записанным положением элемента, такую что она и меньшие цифры уже присутствуют. Если такой такой цифры нет то N могло бы быть равно 10^n.
3 ошибка. Но это всё не гарантирует что цифры N после k+1 это нули. Например если Х= 1 2013456789 2301456789, то 220 (и даже 221) ещё можно набрать удаляя цифры х.

В общем, прошу прощения у топикстартера, я грубо ошибся и мой алгоритм никуда не годится.
1
3 / 3 / 0
Регистрация: 26.11.2017
Сообщений: 30
04.08.2018, 13:17  [ТС] 6
Всем спасибо!Нашел решение на просторах интернета)
0
Заблокирован
Эксперт C
04.08.2018, 13:20 7
Цитата Сообщение от Exiti Посмотреть сообщение
Нашел решение
Так может покажите? Или ссылочку дайте.. Мы же старались, нам интересно...
0
3 / 3 / 0
Регистрация: 26.11.2017
Сообщений: 30
04.08.2018, 15:04  [ТС] 8
http://inf.1september.ru/article.php?ID=200601601
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.08.2018, 15:04

Создать бинарный файл, который нельзя будет корректно прочитать обычным блокнотом
Проблема такова. Я создаю через программу бинарный файл в 16-ричном виде и надо, чтобы его нельзя...

создать проект, который из цифр вводимого с клавиатуры будет считать количество цифр, которые принадлежат [15
Помогите !!! Создать проект, который из цифр вводимого с клавиатуры будет считать количество цифр,...

Input в который нельзя ввести никакие символы кроме цифр от 0 до 9
Как сделать так, чтобы в input типа text можно было ввести только цифры от 0 до 9? А остальные...

Получить номер материнской платы и номер диска, который находится в дисководе в данный момент
Делаю базу данных на Visual Studio 2010 на языке Visual Basic. Необходимо собрать информацию о...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.