ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1407. One-two, One-two

My Solution is here
Posted by vetas 28 Dec 2008 13:48
## Russian ##

## 1 Идея ##

1) Представим число A в виде 10x+m1, где x - число десятков
m1=2 (m1 не может быть равно 1, так как в этом случае искомое число A нечетное и на 2^N не разделится). Разделим число на 2, получим A=5x+1.
2) Пусть x=10y+m2, где y - число сотен. После подстановки получим A=5(10y+m2)+1=50y+5m2+1. Чтобы число A разделилось на 2, надо, чтобы m2 было нечетным. Следовательно выбираем m2=1. После деления на 2 получим: A=(50y+5*1+1)/2=25y+3.
3) Пусть y=10z+m3, где z - число тысяч. После подстановки получим A=25(10z+m3)+3=250z+25m3+3. Чтобы число A разделилось на 2, надо, чтобы m3 было нечетным. Следовательно выбираем m3=1. После деления на 2 получим: A=(250z+25*1+3)/2=125z+14.
4) Пусть z=10t+m4, где t - число десятков тысяч. После подстановки получим A=125(10t+m4)+14=1250t+125m4+14. Чтобы число A разделилось на 2, надо, чтобы m4 было четным. Следовательно выбираем m4=2. После деления на 2 получим: A=(1250t+125*2+14)/2=625t+132.

Далее процесс повторяется N раз. Последовательность mN...m4m3m2m1 образует ответ. Алгоритм требует применения длинной арифметики. Общее решение достигается за N шагов.

## 2 Алгоритм ##
Пусть m[1]=2; a_[1]=5; b_[1]=1;
Цикл i = от 2 до n
нц
  m_[i]=(если b_[i-1] нечетное, то 1, иначе 2)
  b_[i]=(если b_[i-1] нечетное, то (a_[i-1]+b_[i-1])/2, иначе (2*a_[i-1]+b_[i-1])/2)
  (так как a_[i-1] нечетное всегда по определению)
  a_[i]=a_[i-1]*5;
кц

## English (in short) ##

## 1 The Idea ##

1) Let me A = 10x+m1, where x - number of Tens
m1=2 (m1<>1, as A - odd). Division A in 2, let's receive A=5x+1.
2) Let me x=10y+m2, where y - number of Hundreds. Then A=5(10y+m2)+1=50y+5m2+1. if A%2==0, m2 is odd. Then m2=1 and A=(50y+5*1+1)/2=25y+3.
3) Let me y=10z+m3, where z - number of Thousand. Then A=25(10z+m3)+3=250z+25m3+3. if A%2==0, m3 is odd. Then m3=1 and A=(250z+25*1+3)/2=125z+14.
4) Let me z=10t+m4, где t - number of Tens thousand. Then A=125(10t+m4)+14=1250t+125m4+14. if A%2==0, m3 is even. Then m3=1 and A=(1250t+125*2+14)/2=625t+132.

Further process repeats N time. Sequence mN... m4m3m2m1 forms the answer. The algorithm demands application of long arithmetics.

## 2 The Algo ##
Let me m[1]=2; a_[1]=5; b_[1]=1;
for i = 2 to n
begin
  m_[i]=(if b_[i-1] is odd, then 1, else 2)
  b_[i]=(if b_[i-1] is odd, then (a_[i-1]+b_[i-1])/2, else (2*a_[i-1]+b_[i-1])/2)
  a_[i]=a_[i-1]*5;
end
Re: My Solution is here
Posted by format_jam 17 May 2009 08:11
thank you! excellent idea!
Re: My Solution is here
Posted by Felix_Mate 14 Aug 2016 12:51
Можно проще.
Индукция: для любого n существует число x(n) из 1 и 2 длиной n, делящееся на 2^n.
База: n=1=>x(1)=2.
Переход n->n+1: если x(n) делится на 2^(n+1), то в качестве x(n+1) можно взять x(n+1)=2x(n) (т.е. слева приписать 2), иначе x(n+1)=1x(n).
Re: My Solution is here
Posted by Sadeko 6 Mar 2019 15:44


Edited by author 10.03.2019 13:22