EvenOdd

Nhìn vào dãy số ta sẽ thấy qui luật

• Với n là số chẵn: ta có T = n/2 số lẻ ở phía trước và n/2 số chẵn ở phía sau
• Với n là số lẻ: ta có T = (n+1)/2 số lẻ ở phía trước và n – T số chẵn.

Dựa vào vị trí thứ k cần tìm ta xác định được giá trị của nó bằng cách:

• Nếu k < T (giá trị của k là số lẻ) thì kết quả là 2k -1;
• Nếu k > T (giá trị của k là số chẵn) thì kết quả 2(k-T);

Code:

if (n mod 2 = 0) then T := n div 2

else T :=  (n+1) div 2;

if (k <= T) then write( (2*k) - 1)

else write( 2* (k-T));

 

 

 

 

Find the seat line    

            Để biết vị trí của ghế có nằm trong một hàng trong nào đó hay không bằng cách kiểm tra vị trí của ghế đó có nhỏ hơn hoặc bằng vị trí của ghế cuối của hàng hay không.  

Nhìn vào ta sẽ thấy qui luật:

            Ghế cuối của hàng thứ 2 bằng ghế cuối của hàng 1 cộng 2: 1 + 2 =3

            Ghế cuối của hàng thứ 3 bằng ghế cuối của hàng 2 cộng 3: 3 + 3 =6

            Ghế cuối của hàng thứ 4 bằng ghế cuối của hàng 3 cộng 4: 6 + 4 =10

            .......

Code:

                   soghe:=1;
                   i:=1;
                   while soghe<n do
                   begin
                           inc(i);
                           soghe:=soghe+i;
                   end;
                   if soghe=n then write(i)
                   else write(i);

 

 

 

Power of three not nine

            Nhận thấy 9ⁿ = 3²ⁿ  để một số là luỹ thừa của 3 mà không phải luỹ thừa của 9 thì 2n = 2k +1 (2n là số lẻ).

            Với m,n <= 2^31 Suy ra m,n <= 3^20.  Với việc luỹ thừa của 3 từ 1 đến 20 ta sẽ tìm được số thoã mãn trong đoạn [m, n];

Lưu ý:  Để tránh trường hợp tràn bộ nhớ ta dùng kiểu dữ liệU int64.

Code:

             i:=1;
            dem:=0;
            repeat
                  s1:=1;
                  for k:=1 to i do s1:=s1*3;
                  if (s1>=m) and (s1<=n) then inc(dem);
                  i:=i+2;
            until s1>=n;
            write(dem);

 

 

Number Steps

Ta dùng mảng 1 chiều để lưu lại giá trị nhỏ nhất số bước biến đổi.

Ví dụ: Ta biến đổi số 2 thành số 6 bằng cách +, x các giá trị 2, 3.

                              Số bước tại ô số 2 ban đầu là 0, các ô còn lại sẽ là MAX_INT, nghĩa là biến đổi số 2 thành số 2 thì không cần bước nào cả.

2	3	4	5	6
0	MAX_INT	MAX_INT	MAX_INT	MAX_INT

 

1. Bắt đầu từ ô số 2

Đầu tiên ta chọn số 2 sẽ có hai cách tính với nó là 2 + 2 và 2 * 2;

• Với 2 + 2 = 4: số bước lúc này sẽ bằng a[2] + 1 = 0 +1 = 1; {Từ 2 thành 4 có 1 bước biến đổi}

• Tại ô thứ 4 giá trị sẽ bằng min (số bước, a[4] ) {Số bước nhỏ nhất biến đổi từ số 2 sang số 4 là 1}

2	3	4	5	6
0	MAX_INT	1	MAX_INT	MAX_INT

                                            

 

​

 

• Với 2 * 2 = 4 : số bước lúc này sẽ bằng a[2] + 1 = 0 +1 =1;

• Tại ô thứ 4 giá trị sẽ bằng min(số bước, a[4])  //{Số bước nhỏ nhất biến đổi từ số 2 sang số 4 là min(1,a[4]) = min (1,1) =1}

2	3	4	5	6
0	MAX_INT	1	MAX_INT	MAX_INT

 

Tiếp theo ta chọn số 3 sẽ có hai cách tính với nó là 2 + 3 và 2 * 3;

• Với 2 + 3 = 5: số bước lúc này sẽ bằng a[2] + 1 = 0 +1 =1; {Từ 2 thành 5 có 1 bước biến đổi}

• Tại ô thứ 5 giá trị sẽ bằng min(số bước, a[5]) {Số bước nhỏ nhất biến đổi từ số 2 thành số 5 là 1}

2	3	4	5	6
0	MAX_INT	1	1	MAX_INT

• Với 2 * 3 =6: số bước lúc này sẽ bằng a[2] + 1  = 0 +1 =1; {Từ 2 thành 6 có 1 bước biến đổi}

• Tại ô thứ 6 giá trị sẽ bằng min(số bước, a[6]) {Số bước nhỏ nhất biến đổi từ số 2 thành số 6 là 1}

2	3	4	5	6
0	MAX_INT	1	1	1

 

1. Vì ô số 3 = MAX_INT nên ta bỏ qua thực hiện tiếp tại ô tiếp theo (nghĩa là số 3 ko được tạo ra bằng cách (+*) với 2 hoặc 3)
2. Chọn ô số 4 (số bước biến đổi từ 2 thành 4 ít nhất là 1)

Chọn số 2 ta có hai cách thực hiện với nó là 4 + 2 và 4 *2

• Với 4 + 2 = 6: số bước lúc này sẽ bằng a[4] +1 = 1+1 =2; {Từ 2 thành 6 có 2 bước biến đổi}

• Tại ô thứ 6 giá trị sẽ bằng min(số bước, a[6]) {Số bước ít nhất biến đổi từ 2 thành 6 là min(2,1) = 1 //Từ 2 thành 6 cần 1 bước là được}

2	3	4	5	6
0	MAX_INT	1	1	Min(2,1)

 

• Với 4 * 2 = 8 lớn hơn số cần biến đổi nên không cần xét

Chọn số 3 ta có hai cách thực hiện với nó là 4 + 3 và 4 *3 {Cả 2 trường hợp đều lớn hơn số cần biến đổi nền bỏ qua)

 

1. Tiếp tục chọn ô số 5 (Tương tự như 4)

 

Kết luận: Giá trị tại ô số 6 sẽ là số bước biến đổi từ số 2 thành số 6 bằng cách cộng, nhân 2,3.

---

---

Code:

VAR     n, len, i, m, j, step, MAX_INT : longint;
        a,val: array[1..100000] of longint;

function min(a,b: longint):longint;
var result:longint;
begin
        if (a<b) then result := a
        else result := b;
        min := result;
end;

BEGIN
        MAX_INT := 9999;
        read(n,len);
        for i:= 1 to len do read(a[i]);
        readln(m);
        if (n=m) then begin  write('0'); exit(); end;
        if (m<n) then begin  write('-1'); exit(); end;
        for i:= n to m do val[i] := MAX_INT;
        val[n] := 0;
        for i:= n to m do
        begin
                if (val[i] < MAX_INT) then
                begin
                        step := val[i]+1;
                        for j:=1 to len do
                        begin
                                val[i*a[j]] := min(step, val[i*a[j]]);
                                val[i+a[j]] := min(step, val[i+a[j]]);
                        end;
                end;
        end;
        write(val[m]);
END.