2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Jednakost
Сообщение29.08.2020, 23:28 


01/09/14
351
Есть задача. Суть такова: есть выражение вида $A = B$, где $A$ и $B$ - некоторые числа. Нужно разработать алгоритм определяющий каково минимальное количество нулей, которые нужно вставить между цифрами $A$ чтобы обратить выражение в равенство. Строки вида "$0xxx$" рассматривать как "$xxx$". Максимальное количество символов в $A$ равно $1000$, $B$ не больше $5000$.
Пример: $143175=120$. Здесь минимальное количество плюсов $2$, т.е. $14+31+75=120$.
Ещё пример: $5025=30$. Ответ: $1$, т.е. $5+025 = 5+25 = 30$.
Ещё пример: $999899=125$. Ответ: $4$: $9 + 9 + 9 + 89 + 9 = 125$.
Я долго думал, но ничего кроме перебора не придумал. Но перебор крайне долгая операция. Прошу подсказок.

Оригинальная формулировка:
While browsing a math book, Mirko found a strange equation of the form A=S.What makes the equation strange is that A and S are not the same,which makes the equation incorrect. Mirko realized that the left side of the equation should have addition operations between some pairs of digits in A. Write a program that inserts the smallest number of addition operations on the left side to make the equation correct. The numbers in the corrected equation may contain arbitrary amounts of eading zeros.

 Профиль  
                  
 
 Re: Jednakost
Сообщение29.08.2020, 23:42 
Супермодератор
Аватара пользователя


09/05/12
22921
Кронштадт
Charlz_Klug в сообщении #1481294 писал(а):
Пример: $143175=120$. Здесь минимальное количество нулей $2$, т.е. $14+31+75=120$.
А почему символ $+$ вы называете "нулем"?

 Профиль  
                  
 
 Re: Jednakost
Сообщение29.08.2020, 23:46 


01/09/14
351
Спасибо за замечание! Поправил.

 Профиль  
                  
 
 Re: Jednakost
Сообщение29.08.2020, 23:56 
Модератор


20/03/14
11273
Charlz_Klug
Лучше приведите формулировку из ссылки: Ваша интерпретация совершенно непонятна.

 Профиль  
                  
 
 Re: Jednakost
Сообщение30.08.2020, 00:05 


01/09/14
351
Добавил оригинальную формулировку.

 Профиль  
                  
 
 Re: Jednakost
Сообщение30.08.2020, 00:44 
Заслуженный участник
Аватара пользователя


16/07/14
4882
Москва
[надо как-то более явно написать, что $B < 5000$, а не количество символов меньше $5000$, а то я долго думал над, видимо, более сложной задачей]
Charlz_Klug, представьте, что вы решили поставить последний плюс на $i$-й позиции. Как выглядит задача по оптимальной расстановке остальных плюсов?

 Профиль  
                  
 
 Re: Jednakost
Сообщение30.08.2020, 02:55 
Заслуженный участник


23/07/08
8783
Харьков
Charlz_Klug в сообщении #1481296 писал(а):
Спасибо за замечание! Поправил.
Не всё!
Charlz_Klug в сообщении #1481294 писал(а):
каково минимальное количество нулей, которые нужно вставить между цифрами $A$


Charlz_Klug в сообщении #1481302 писал(а):
Добавил оригинальную формулировку.
Не всю! Разве это, например, не имеет значения?:
Цитата:
Note: The input data will guarantee that a solution, although not necessarily unique, will always exist.


Charlz_Klug в сообщении #1481294 писал(а):
eading zeros
leading? ending?

 Профиль  
                  
 
 Re: Jednakost
Сообщение30.08.2020, 09:09 
Заслуженный участник
Аватара пользователя


16/07/14
4882
Москва
svv в сообщении #1481311 писал(а):
Разве это, например, не имеет значения?
На самом деле нет. По крайней мере я не могу придумать алгоритм, который быстро находит число плюсов, если решение есть, и делает что-то не то, если решения нет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, maxal, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group