VKontakte P-35 Задача 23 as of 29.05.17

System above is equvalent this one :-

(┐x1 v ┐x2)=1
(┐x2 v ┐x3)=1
(┐x3 v ┐x4)=1
(┐x4 v ┐x5)=1
(┐x5 v ┐x6)=1
(┐x6 v ┐x7)=1
(┐x7 v ┐x8)=1
(┐y7 v y8 )=1

*******************************
For each j=1,..,7 . We have
*******************************
¬xj  v  ¬ x(j+1)) = 1
 ¬ (xj ^ x(j+1))    =1
(xj ^ x(j+1)) = 0 

Follow known schema ( see it-n.ru/attachment.aspx?id=150390 )
for system

(┐x1 v ┐x2)=1
(┐x2 v ┐x3)=1
(┐x3 v ┐x4)=1
(┐x4 v ┐x5)=1
(┐x5 v ┐x6)=1
(┐x6 v ┐x7)=1
(┐x7 v ┐x8)=1


Let К(n) to be a  number of bit's chains of length "n", which
don't have two ones "1" coming one by one

K1(n) - end up with 1
К0(n) - end up with 0

Then we get :-

K1(n+1)= K0(n)
K0(n+1)= K1(n) + K0(n) = K(n)
K(n+1) = K1(n+1) + K0(n+1) = K0(n) + K0(n+1) = K0(n) + K(n)

Due to :-
K0(n)=K(n-1)

We are getting
K(n+1) = K(n) + K(n-1)
Proof commmited.


Answer is  eight's Fibonacci number , which is 55 (solutions )


Thus final result would be 55*3 =165

VKontakte P-31 Задача 23 as of 24.05.17

Total Records of {x} :-

15 (x1->y1=1 produces 3*Z4 )  + 16 (x1->y1=0 produces 2^4 {x3,x4,x5,x6} ) = 31
  Z4 = 2^4 - K4 ; K4 =  11 => Z4 = 5 

I follow Konstanin Polyakov's article  http://kpolyakov.spb.ru/download/inf-2014-12a.pdf
published in December of 2014 / ИНФОРМАТИКА with identifiers ZJ and KJ

Total Records of {y} :- 5*5 = 25 (K3^2)
First two equations generate  31*25 = 775 corteges

***************************************************************************************
When (x1->x2=0) then number of records {y} which might satisfy first equation
is one solution of (x1->x2) multiplied by  2^4=16 total number corteges {x3,x4,x5,x6}
*************************************************************************************** 

******************************************************************
Calculate number of corteges to remove due to (x2->y2)^(x3->y3)=0
****************************************************************** 

Case 1.

A = x1->x2 True
B = x3->x4->x5->x6  False

x1 x2                 
-----                  
0  0                   
0  1 =>                  
1  1 =>                   
1  0

x3  x4  x5   x6     x3->x4->x5->x6=0  Z4 = K3 = 5; 3(x3) leading 1.

----------------------
1=> 1    1   0
0   1    1   0              
1=> 1    0   0    
0   0    1   0
1=> 0    0   0

Entries from x2 in table bellow

y1->y2 ->  y3 = 1  K3 = 5
----------------------
1   0<=x2   1
0   0<=x2   1
1   1       1  
0   1       1    
1   0<=x2   0  

Entries from x3 in table bellow

y1->y2 ->  y3 = 1  K3 = 5
----------------------
1   0       1
0   0       1
1   1       1  
0   1       1    
1   0       0<=x3      

y4->y5-> y6 = 1  K3 = 5
--------------------
1   0     1
0   0     1                
1   1     1      
0   1     1  
1   0     0

2*3*5 generated via x1->x2
3*1*1 generated via x3->x4->x5->x6
Total 30+3 = 33
************************************************************** 

Case 2. 
A = x1->x2 False
B = x3->x4->x5->x6  False
x1 x2
------
1  0
y1->y2 ->  y3 = 1  K3 = 5
----------------------
1   0       1
0   0       1
1   1       1  
0   1       1    
1   0       0<=x3     
x3  x4  x5   x6     x3->x4->x5->x6=0  Z4 = K3 = 5; 3(x3) leading 1.
----------------------
1=> 1    1   0
0   1    1   0              
1=> 1    0   0    
0   0    1   0
1=> 0    0   0

Total 3*1*1 = 3 generated via x3->x4->x5->x6 = 0
***************************************************************
Case 3. 
A = x1->x2 False
B = x3->x4->x5->x6  True
x1 x2
-------
1   0
 
y1->y2 ->  y3 = 1  K3 = 5
----------------------
1   0       1
0   0       1
1   1       1  
0   1       1    
1   0       0 <= x3 
x3 -> x4 -> x5  -> x6  = 1  K4=11  ; 5(x3) leading 1
-----------------------------
0     0     0      0
0     0     0      1
0     0     1      1
0     1     0      0
0     1     0      1
0     1     1      1
1=>   0     0      1
1=>   0     1      1
1=>   1     0      0
1=>   1     0      1
1=>   1     1      1

Total 5*1*1=5 generated via x3->x4->x5-x6 =1


******************************************************
Result = 33 +3 +5 = 41
******************************************************


Now remind
y4->y5-> y6 = 1  K3 = 5
--------------------
1   0     1
0   0     1                
1   1     1      
0   1     1  
1   0     0 
************************************* 
So for all three cases considered
*************************************
Final result is 41*5 = 205 ( {x},{y} stays in line as cortege detected to remove )
Thus answer 775 - 205 = 570 
References
1.  http://kpolyakov.spb.ru/download/inf-2014-12a.pdf

Прозрачный код для задачи К. Полякова 506 тип (24)

                                                           Я не люблю фатального исхода
                                                           От жизни никогда не устаю
                                                           Я не люблю любое время года
                                                           Когда весёлых песен не пою
                                                                                           В.С. Высоцкий

(№ 506) Требовалось написать программу, которая получает на вход натуральное число N, не превосходящее 10⁹, и выводит число, которое получается из N после удаления всех единиц; порядок остальных цифр при этом не меняется. Например, число 19520125 должно быть преобразовано в число 952025. Число, в котором все цифры – единицы и нули, должно быть преобразовано в 0. Незначащие нули в старших разрядах полученного числа печатать не нужно. Программист написал программу неправильно.

********************************************
Оригинальный код
********************************************
var N, R, T: longint;
d: integer;
begin
readln(N);
R:=0;
T:=1;
while N>0 do begin
d := N mod 10;
if d<>1 then begin
R := R + d*T;
T := T+1
end;
N := N div 10;
end;
writeln(T);
end.

***************************************************************************************
  Зачем писать преднамеренно код на языке высого уровня,искуственно
  избегая прозрачного хода вещей. Есть тип данных Extended, conversion
  Extended into Longint  in other words inside loop type Extended позволяет
  инкрементировать s и последовательно удалить единицы  :-

  if d <> 1 then begin
     s := s + d*exp(j*Ln(10));
     inc(j);
  end;

 Цикл сделан обратная конвертация :-
    s_out := Round(s);
    writeln (s_out);

Проблем при разработке хватает, чтобы не создавать их искуственно
***************************************************************************************
program prog3;
var N,j,s_out: longint;
d:  integer;
s:  extended;

begin
readln(N);
j :=0;
s :=0;

while N > 0 do begin
  d := N mod 10;
  if d <> 1 then begin
     s := s + d*exp(j*Ln(10));
     inc(j);
  end;
N := N div 10;
end;
s_out := Round(s);
writeln(s_out);
end.
***********************************************************************************
Корректировка программы К. Полякова № 506 (24) . По видимому, как предполагается
***********************************************************************************
program polkv1;
var N, R, T: longint;
d: integer;
begin
readln(N);
R:=0;
T:=1;
while N>0 do begin
d := N mod 10;
if d<>1 then begin
R := R + d*T;
// Fixed line bellow . It was T=T+1
T := T*10;
end;
N := N div 10;
end;
// Fixed line bellow . It was writeln(T);
writeln(R);
end.

 

Solution VK Informatics Group task #23 as of 15.05.17

  

(x1 -> (x2 * y2)) * (y1 -> y2)=1
(x2 -> (x3 * y3)) * (y2 -> y3)=1
(x3 -> (x4 * y4)) * (y3 -> y4)=1
(x4 -> (x5 * y5)) * (y4 -> y5)=1
(x5 -> (x6 * y6)) * (y5 -> y6)=1
(x6 -> (x7 * y7)) * (y6 -> y7)=1
(x7 -> (x8 * y8)) * (y7 -> y8)=1

   Question above seemed interesting for me . I also hope that there is no
   mistakes down here.



Bitmask for {y}

   y1  y2  y3   y4  y5  y6  y7 y8
  ---------------------------------------------
   1    1    1    1    1   1    1    1   
   0    1    1    1    1   1    1    1 
   0    0    1    1    1   1    1    1 
   0    0    0    1    1   1    1    1  
   0    0    0    0    1   1    1    1 
   0    0    0    0    0   1    1    1 
   0    0    0    0    0   0    1    1 
   0    0    0    0    0   0    0    1 
   0    0    0    0    0   0    0    0 

   First, second entries

   y1  y2  y3   y4  y5  y6  y7 y8
  ---------------------------------------------
   1    1    1    1    1   1    1    1   
   0    1    1    1    1   1    1    1  


  (x1->x2)= 1
  (x2->x3)= 1
  (x3->x4)= 1
  (x4->x5)= 1
  (x5->x6)= 1
  (x6->x7)= 1
  (x7->x8)= 1

  x1  x2  x3   x4  x5  x6  x7 x8
  ---------------------------------------------
   1    1    1    1    1   1    1    1   
   0    1    1    1    1   1    1    1  
   0    0    1    1    1   1    1    1  
   0    0    0    1    1   1    1    1     
   0    0    0    0    1   1    1    1  
   0    0    0    0    0   1    1    1  
   0    0    0    0    0   0    1    1  
   0    0    0    0    0   0    0    1  
   0    0    0    0    0   0    0    0  


We get 9 *2

Third entry

y1  y2  y3   y4  y5  y6  y7 y8
---------------------------------------------
0    0    1    1    1   1    1    1  


(x1-> 0 )= 1
(x2->x3)= 1
(x3->x4)= 1
(x4->x5)= 1
(x5->x6)= 1
(x6->x7)= 1
(x7->x8)= 1

We get x1=0 plus 8

   x2 x3  x4  x5   x6  x7 x8
  ------------------------------------
   1    1    1    1    1   1   1
   0    1    1    1    1   1   1   
   0    0    1    1    1   1   1    
   0    0    0    1    1   1   1      
   0    0    0    0    1   1   1    
   0    0    0    0    0   1   1    
   0    0    0    0    0   0   1
   0    0    0    0    0   0   0 


Fourth entry

y1  y2  y3   y4  y5  y6  y7 y8
-------------------------------------------
0    0    0    1    1   1    1    1  


(x1-> 0) = 1
(x2-> 0) = 1
(x3->x4)= 1
(x4->x5)= 1
(x5->x6)= 1
(x6->x7)= 1
(x7->x8)= 1

We get x1=0,x2=0  plus  7

Fifth entry

y1  y2  y3   y4  y5  y6  y7 y8
-------------------------------------------
0    0    0    0    1   1    1    1

(x1-> 0) = 1
(x2-> 0) = 1
(x3-> 0) = 1
(x4->x5)= 1
(x5->x6)= 1
(x6->x7)= 1
(x7->x8)= 1

We get x1=0,x2=0,x3=0  plus 6

 . . . . . .

Seventh entry

y1  y2  y3   y4  y5  y6  y7 y8
-------------------------------------------
0    0    0    0    0    0    0    1

(x1-> 0) =0
(x2-> 0) =0
(x3-> 0) =0
(x4->x5)=0
(x5->x6)=0
(x6->x7)=0
(x7->x8)=1


We get x1=0,x2=0,x3=0,x4=0,x5=0,x6=0,x7=0  plus 2

9 +9 + 8 + 7 + 6  + 5 + 4 +3 + 2   =  9 + (9*10)/2 -1 = 45 + 8 =53

***********************
Mapping Method
***********************

(x1 -> (x2 * y2)) * (y1 -> y2)=1
(x2 -> (x3 * y3)) * (y2 -> y3)=1
(x3 -> (x4 * y4)) * (y3 -> y4)=1
(x4 -> (x5 * y5)) * (y4 -> y5)=1
(x5 -> (x6 * y6)) * (y5 -> y6)=1
(x6 -> (x7 * y7)) * (y6 -> y7)=1
(x7 -> (x8 * y8)) * (y7 -> y8)=1

Solution VK Informatics Group task #23 as of 14.05.17

   For j =1 to 6
   zj = xj ^ yj

   Split equations. For {zj} we get well known system
   Solutions standard bitmask table for z6,z5,z4,z3,z2,z1.

   z2 -> z1 =1
   z3 -> z2 =1
   z4 -> z3 =1
   z5 -> z4 =1
   z6 -> z5 =1

   z6  z5  z4  z3  z2  z1
  ----------------------------------
   1    1    1    1    1   1
   0    1    1    1    1   1
   0    0    1    1    1   1
   0    0    0    1    1   1
   0    0    0    0    1   1
   0    0    0    0    0   1
   0    0    0    0    0   0


1.  Consider  zj = 0 then xj ^ yj = 0

  So ( xj=1, yj=0); (xj=0, yj=1) ; (xj=0, yj=0)

  Look back into original system. For each j we should have
  (xj v yj) = 1 hence decline third pair.

  Total 2 pairs for zj = 0

2.  Consider  zj = 1  then xj ^ yj =1
    So xj=1 and yj=1
    Just one solution.

  Thus we get :-

   z6  z5  z4  z3  z2  z1
  ----------------------------------
   1    1    1    1    1   1        1
   0    1    1    1    1   1        2^1
   0    0    1    1    1   1        2^2
   0    0    0    1    1   1        2^3
   0    0    0    0    1   1        2^4
   0    0    0    0    0   1        2^5
   0    0    0    0    0   0        2^6

Total  (2^7 -1)/(2-1) = 127


*****************************
Mapping method
*****************************

(x1 v y1)^((x2^y2) => (x1^y1))  = 1
(x2 v y2)^((x3^y3) => (x2^y2))  = 1
. . . . .
(x5 v y5)^((x6^y6) => (x5^y5))  = 1
(x6 v y6) = 1

VK Тренировочный КИМ от 01.05.2017 . Задача 23

Расставим скобки для ясности ( приоритет "^" над  "v")

(x1->x2)^(x2-x3)^(x3->x4) =1
(¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1) =1
(¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2) =1
(¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3) =1
(¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4) =1

Битовая маска для  {x}
x1 x2 x3 x4
-------------------
1   1   1   1
0   1   1   1
0   0   1   1
0   0   0   1
0   0   0   0

Рассмотрим  вхождение {x1,x2,x3,x4} 1,1,1,1 - тогда первая скобка
в каждом уравнении из 4 -ех последних есть 0. Скобки же 2-ая,3-ья
содержат в коньюнкции х[j] = 1, которое можно просто опустить.
Применим отрицание к каждому из этих уравнений,дважды используя закон Де Моргана.

Первый раз :-

 ¬((¬y1 ^ z1) v (y1 ^ ¬z1))  =¬1
 ¬(¬y1 ^ z1) ^ ¬(y1 ^ ¬z1) =0

Второй раз для каждой скобки в коньюнкции :-

(y1 v ¬z1) ^ ( ¬y1 v z1) =0
. . . . . . . .

Исходная система  :-

(¬y1 ^ z1) v (y1 ^ ¬z1) =1
(¬y2 ^ z2) v (y2 ^ ¬z2) =1
(¬y3 ^ z3) v (y3 ^ ¬z3) =1
(¬y4 ^ z4) v (y4 ^ ¬z4) =1

Конвертированная система :-

(y1 v ¬z1) ^ (¬y1 v z1)=0
(y2 v ¬z2) ^ (¬y2 v z2)=0
(y3 v ¬z3) ^ (¬y3 v z3)=0
(y4 v ¬z4) ^ (¬y4 v z4)=0

Следующий шаг замена  ¬AvB на  A->B.
Применяя известную формулу булевой алгебры
мы получаем систему 4-ех тождеств , каждое из
которых имеет два решения.

(z1->y1)^(y1->z1)= (y1 <=> z1) =0
(z2->y2)^(y2->z2)= (y2 <=> z2) =0
(z3->y3)^(y3->z3)= (y3 <=> z3) =0
(z4->y4)^(y4->z4)= (y4 <=> z4) =0

Окончательно получаем  :-

 (y1 <=> z1) =0
 (y2 <=> z2) =0
 (y3 <=> z3) =0
 (y4 <=> z4) =0

Данная система имеет  2^4=16 решений

2. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,1,1,1 , в этом случае
    количество конвертируемых уравнений станет равно 3.
    
y1 ^ z1 = 1
(y2 <=> z2) =0
(y3 <=> z3) =0
(y4 <=> z4) =0

Имеем   2^3 =8 решений

3. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,1,1 , в этом случае
    количество конвертируемых уравнений станет равно 2.


y1 ^ z1 = 1
y2 ^ z2 = 1
(y3 <=> z3) =0
(y4 <=> z4) =0

Имеем 2^2 = 4 решения

3. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,0,1 , в этом случае
    количество конвертируемых уравнений станет равно 1.


y1 ^ z1 = 1
y2 ^ z2 = 1
y3 ^ z3 = 1
(y4 <=> z4) =0

Имеем  2 решения

4. Рассмотрим  вхождение {x1,x2,x3,x4} - 0,0,0,0 , в этом случае
    количество конвертируемых уравнений станет равно 0.
    Их просто нет.

y1 ^ z1 = 1
y2 ^ z2 = 1
y3 ^ z3 = 1
y4 ^ z4 = 1

Одно решение

Ответ :  16 + 8 + 4 + 2 + 1 =31

Решение той же задачи Методом отображений. Построение полного графа следуя Е.А.Мирончик  для системы

(x1->x2)^(x2-x3)^(x3->x4) =1
(¬x1^y1^z1) v (x1^¬y1^z1) v (x1^y1^¬z1) =1
(¬x2^y2^z2) v (x2^¬y2^z2) v (x2^y2^¬z2) =1
(¬x3^y3^z3) v( x3^¬y3^z3) v (x3^y3^¬z3) =1
(¬x4^y4^z4) v (x4^¬y4^z4) v (x4^y4^¬z4) =1

Официальные ответы от 09.05.17

  Well done.