|
|
|
|
#1
17.02.2010, 00:03
|
|||
|
|||
Нужна идея...
Маша очень любит играть с числами. Она достает из большого мешка карточки с написанными на них цифрами от 0 до 9 и составляет из них разные числа. Однажды, когда она составила очередное число, к ней подошел вундеркинд Миша и с удивлением заметил:
- Ты смотри, если в твоей числе переставить две последние цифры на начало, то число увеличится вдвое. Задача: Составьте программу NUMGAME, которая бы за двумя последними цифрами определяла наименьшее число, увеличившиеся бы вдвое после их перестановки, если такое существует. Входные данные: В текстовом файле NUMGAME.IN записаны без пропуска две цифры. Исходные данные: В выходной файл NUMGAME.OUT одной строкой записывается наименьшее число с данным свойством, которое заканчивается этими цифрами или сообщения NO SOLUTION в случае отсутствия такого числа. Пример: NUMGAME.IN - 06 NUMGAME.OUT - 03015075376884422110552763819095477386934673366834 1708542713567839195979899497487437185929648241206 Делал через поиск, но такой способ не подходит (в течении 2 часов не нашло ни 1 числа, да и потом не нашло бы скорее всего) У кого то есть приблизительные идеи? код не нужен, нужны идеи. |
|
#2
17.02.2010, 13:55
|
||||
|
||||
|
А такие числа есть ?
( вообще то это уже математика, которой ужасно давно не занимался поэтому, если кто найдет ошибки - исправьте ) Пусть исходное число = y*100 + x где x - натуральное число от 0 до 99. y - любое положительное натуральное число. (т.е. число 123= 1*100 + 23) Введем z представляющую порядок Т.е. z = 10, 100, 1000, .... ( z=10^n) и y < z ( если z= 100 y=0..99) Тогда задачу можно представить в виде системы: 1. y < z 2. (y*100 + x)*2 = x*z + y 2: y*200 - y = x*z - x*2 y * 199 = x * (z - 2) Подставим в 1. x * (z - 2) / 199 < z x*z - x*2 < z * 199 -x*2<z(199-x) z>-x*2/(199-x) z - любое ( к сожалению в первом варианте у меня z выходила отрицательным, что означало отсутствие таких чисел, но при переписывании нашел ошибку ). Зато формула y = x * (z - 2) / 199 позволяет быстро перебрать все варианты в пределах Int64. Я делал это так: Код:
procedure TForm1.tbChislaClick(Sender: TObject);
var
x : Integer;
Zmax, y,z: Int64;
Surse, Dest: Int64;
begin
Memo1.Clear;
ZMax := High(Int64) div 100;// чтобы не вылезти за пределы
for x := 1 to 99 do
begin
z := 10;
while z <= ZMax do
begin
y := x * (z - 2);
if (y mod 199) = 0 then // y должно быть целым числом
begin
y := y div 199;
Memo1.Lines.Add(Format('(%d) %d - %d',[z, x, y] ));
end;
z := z*10;
end;
end;
Memo1.Lines.Add('STOP');
end; |
|
#3
17.02.2010, 22:02
|
|||
|
|||
|
фы
Цитата:
вот ведь пример такого числа 03015075376884422110552763819095477386934673366834 1708542713567839195979899497487437185929648241206 )) Да ваш вариан не находит ни одного числа.. но я не пойму как работает ваша программа, где идет перестановка чисел в начало или что-то как то так) P.s это областная олимпиадная задача, так что простым способом ее так не решить, нужно еще как то злощастный нолик учитывать, который может стоять в начале числа и в первой цифре двух последних цифер... как в примере.. |
|
#4
17.02.2010, 22:50
|
||||
|
||||
|
Моя программа вычисляет такие числа по формуле:
y = x * (z - 2) / 199 ( смотри выкладки ) И у нее ограничение размерностью Int64 где самое большое число 9223372036854775807 И она учитывает левые нули. Для нахождения чисел большей велицины надо применить длинную арифметику. По существу x - это NUMGAME.IN для каждого x надо перебирая z= 10, 100, ... т.е. 10^n проверять чтобы x * (z - 2) делилось на 199 без остатка ( если верны мои математические выкладки ) тогда и получишь недостающие цифры ( y ) например для твоего числа x=06 ; z=10^97; ( в степени 97 ) 06 * ( 10^97 - 2 ) mod 199 = 0 ( должно ) y= 06 * ( 10^97 - 2 ) div 199 = 03015075376884422110552763819095477386934673366834 17085427135678391959798994974874371859296482412 количество нулей с лева можно определить взяв логарифм от z ( т.е. зная степень 10 ) Если у тебя есть функции для работы с такими числами ( например в виде строк ) - проверь на этом числе. Если таких формул нет попробуй использовать вот это: Работа с очень большими числами И необязательно полностью цитировать пост - неудобно читать  Последний раз редактировалось s0Creator, 17.02.2010 в 22:52. |
|
#5
17.02.2010, 23:06
|
||||
|
||||
|
Вот код, объяснение через пару минут напишу.
Также выкладываю решение для всех чисел от 0 до 99. Код:
program Project1;
const maxarray = 200;
var x,y,p:byte;
a: array [1..maxarray] of byte;
i:integer;
isfind:integer;
begin
assign(input, 'NUMGAME.IN');
reset(input);
assign(output, 'NUMGAME.OUT');
rewrite(output);
// read
Readln(x);
y := x mod 10;
x := x div 10;
// solve
p := 0;
a[1] := y;
a[2] := x;
isfind := 0;
for i:=3 to maxarray do
begin
a[i] := a[i-2]*2 + p;
p := a[i] div 10;
a[i] := a[i] mod 10;
if ((a[i]=x) and (a[i-1]=y) and (p=0)) then
begin
isfind := i-2;
break;
end;
end;
// output
if (isfind > 1) then
begin
for i:=isfind downto 1 do
Write(a[i]);
Writeln('');
end
else
begin
Writeln('NO SOLUTION');
end;
close(input);
close(output);
end. |
|
#6
17.02.2010, 23:18
|
||||
|
||||
|
malekskv откуда задача ? с http://acm.timus.ru ? Вроде я там видел подобную...
Решение выглядит очень просто: 1. Пусть abc...defxy - формат числа, которое надо найти 2. Нам даются две последние цифры - x и y ( в примере x=0 y=6 ) 3. Тогда если искомое число умножить на 2, должно получится число xyabc...def 3. Попробуем умножить искомое число на 2 в столбик: Тогда видно, что: f = y*2 mod 10 p = y*2 div 10 // перенос, если y*2 >= 10 След. шаг: e = (x*2+p) mod 10 p = (x*2+p) div 10 След. шаг: d = (f*2+p) mod 10 p = (f*2+p) div 10 И т.д И выполнять это надо до момента, когда две последние полученные цифры станут равными x и y и перенос при этом будет равен 0 |
Линейный вид
