<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>Sơ đồ Tractenberg</b>

Giáo s Jacob Tractenberg xây dựng một sơ đồ cho phép tính một cách nhanh chóng và
đơn giản tích 2 số ngun. Ví dụ, để tính 23*14 ta phải dựa trên bộ dữ liệu trung gian
12, 11 và 2. Các số trung gian này đợc gọi là bộ dữ liệu Tractenberg. Từ bộ dữ liệu
này, ta có thể dễ dàng suy ra tớch cn tỡm l 322.

Để hiểu về bộ dữ liệu Tractenberg, ta xÐt thªm mét sè vÝ dơ:

241304 ´ 32 => 8 12 6 11 11 16

6 => 7721728

527 ´ 463 => 21 48 55 38 20

=> 244001

3214 ´ 5643 => 12 19 34 43 29 28 15

=> 18136602

1245 ´ 8 => 40 32 16 8

=> 9960

Hãy xác định cách xây dựng bộ dữ liệu Tractenberg và từ bộ dữ liệu này xác định các
cặp thừa số cũng nh tớch ca chỳng.

<i>Dữ liệu: vào từ file văn bản MULTP.INP các số của 1 bộ dữ liệu Tractenberg, số lợng </i>

số không quá 50, ghi trên 1 hoắc nhiều dòng, các số trên 1 dòng cách nhau ít nhất 1

dấu cách.

<i>Kết quả: đa ra file văn bản MULTP.OUT thông tin dạng:</i>
<i><b>Thừa số I * Thừa số II = TÝch</b></i>

Mỗi dịng ứng với một kết quả khác nhau tìm đợc. Các thừa số khơng chứa số 0 khơng
có nghĩa ở đầu. Hai kết quả đợc coi là giống nhau, nếu chỉ khác nhau ở trình tự các
thừa số trong tích.

<i>VÝ dơ: </i>

MULTP.INP MULTP.OUT

8 12 6 11 11 16 6 _{241304*32=772172}

8

<b>chu kú tuÇn hoµn</b>

Xét hàm F xác định trên tập các số nguyên từ 1 đến M ( M  32767) Giá trị của hàm
cũng nằm trong khoảng đó. Cho N số nguyên x1, x2, . . ., xN ( 1 < N  1000, 1  xi 

M, i). Ngêi ta xây dựng các véc tơ Vj nh sau:

V0 = x1, x2, . . ., xN

V1 = F(X1), F(X2), . . ., F(XN)

V2 = F(F(X1)), F(F(X2)), . . ., F(F(XN))

V3 = F(F(F(X1))), F(F(F(X2))), . . ., F(F(F(XN)))

. . . .

Vì tập giá trị của F là hữu hạn, nên đến một lúc nào đó dãy Vi sẽ lặp lại các giá trị của

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

<i>D÷ liệu: vào từ file CYCLE.INP:</i>

Dòng đầu tiên chứ số nguyên M,

Dòng thứ 2 chứa M số nguyên F(1), F(2), . . . , f(M),
 Dßng thứ 3 chứa số nguyên N,

Dòng thứ 4 chứa N số nguyên x1, x2, . . ., xN

Các số trên 1 dòng cách nhau ít nhất 1 dấu cách.

<i>Kt quả: đa ra file văn bản CYCLE.OUT độ dài trớc chu trỡnh v chu k trờn mt </i>

dòng, các số c¸ch nhau Ýt nhÊt 1 dÊu c¸ch

<i>VÝ dơ:</i>

CYCLE.INP CYCLE.OUT

10 2 6

5 6 4 3 2 5 1 1 5 4
4

1 10 8 1

<b>D y số</b>Ã

Ngời ta xây dựng dÃy vô hạn các số A[1], A[2], . . . . theo quy t¾c sau:
 A[1] = 0,

 Giả thiết đã xây dựng đợc dãy A[1], A[2], . . ., A[3M_{]. Khi đó, các số A[3}M_+1],

A[3M_{+2], . . . ,A[3}M+1_{] sẽ nhận các giá trị tơng ứng là A[3}M_{] + 3}M_{, A[3}M_-1]+3M_{, . . .}

., A[1]+3M_{, A[1]+2*3}M_{, A[2]+2*3}M_{, . . . , A[3}M_]+2*3M_.

Với số nguyên N cho trớc ( 1  N  1 000 000 000) hãy xác định A[N].

<i>Dữ liệu: vào từ file văn bản NUMBER.INP, gồm không quá 50 dòng, mỗi dòng một số</i>

nguyên N.

<i>Kt qu: a ra file văn bản NUMBER.OUT các số A[N] tìm đợc, mỗi số trên 1 dịng.</i>

VÝ dơ:

NUMBER.INP NUMBER.OUT

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

<b>Đục lỗ</b>

Cho tờ giấy kẻ ca rô kích thớc 2N_{* 2}N_{ô mỗi chiều ( 3 N  500). Ngêi ta gËp tê}

giấy này N-3 lần, mỗi lần gập nh sau: gấp mép dới lên mép trên để mặt trớc đè lên

nhau, sau đó gấp mép phải đè lên trên mép trái. Nh vậy, sau mỗi lần gấp kích thớc mỗi
chiều của tờ giấy giảm đi một nữa. Kết quả cuối cùng ta có xếp giấy kích thớc 8*8.
Bằng máy dập, ngời ta đục một số ô của xếp giấy đồng thời ở tất cả các lớp. Hãy xác
định, sau khi mở lại tờ giấy, ta có bao nhiêu phần rời nhau, biết rằng 2 ơ dính với nhau
khi chúng có ít nhất 1 cạnh chung.

<i>D÷ liệu: vào từ file LIST.INP:</i>

Dòng đầu tiên chứa số nguyªn N,

 8 dịng sau, mỗi dịng chứa 8 số 0 hoặc 1, trong đó 1 là ơ bị đục. Cỏc s cỏch nhau
1 du cỏch.

<i>Kết quả: đa ra file LIST.OUT 1 số nguyên cho biết có bao nhiêu phần rêi nhau.</i>
<i>VÝ dô: </i>

LIST.INP LIST.OUT

4 11

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

<b>Đẳng cấu</b>
Xét một đồ thị có hớng N đỉnh với các tính chất sau:

 Giữa 2 đỉnh u và v khác nhau tồn tại đúng 1 cung có hớng nối chúng,

 Khơng tồn tại cung nối trực tiếp một đỉnh với chính nó, tức là khơng tồn tại đỉnh
kiểu u  u.

Các đỉnh của đồ thị đợc đánh số từ 1 đến N. P là một hoán vị của các số từ 1 tới N.
Hoán vị P gọi là đẳng cấu với 2 đỉnh u và v, nếu hớng của cung (u,v) trùng với hớng

của cung (P(u), P(v)) trong đồ thị này.

Với một đồ thị và một hoán vị P cho trớc, ta có T đồ thị đẳng cấu đối với P.

Ví dụ: với N = 4 và P(1) = 2, P(2) = 4, P(3) = 3, P(4) = 1, tồn tại 4 đồ thị đẳng cấu ( T
= 4):

<i>Yêu cầu: Với một đồ thị và một hoán vị P cho trớc, hãy xác định T mod 100.</i>

<i>Dữ liệu: vào từ file văn bản AUT.INP:</i>

Dòng đầu tiên chứa số nguyên N, ( 0 < N 10 000),

Các dòng sau chứa các số nguyªn P(1), P(2), . . . ,P(N), ghi trên 1 hoặc nhiều
dòng, các số trên 1 dòng cách nhau ít nhất 1 dấu cách.

<i>Kết quả: đa ra file văn bản AUT.OUT phần d của phép chia T cho 100.</i>
<i>VÝ dô: </i>

AUT.INP AUT.OUT

4 4

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

<b>Cây nhị phân</b>

Xột cõy nh phõn. Cõy cú th rng hoặc có một số đỉnh. Mỗi đỉnh của cây có không
quá 2 cây con. Đỉnh không thuộc một cây con nào đợc gọi là gốc. Mỗi đỉnh chứa một
chữ cái tiếng Anh khác nhau. Cây đợc gọi là Cây nhị phân tìm kiếm ( BST), nếu nó
thoả mãn điều kiện sau: với cây đã cho và cây con bất kỳ các nút ở cây con trái của nó
đều chứa chữ cái trớc chữ cái ở nút gốc và các các nút ở cây con phải đều chứa chữ cái

sau chữ cái ở nút gốc. Tập các chữ cái của cây có thể rỗng (nếu cây rỗng) hoặc là K
chữ cái đầu tiên, nếu cây có K nút. Mỗi cây BST tơng ứng với 1 xây K ký tự. Xâu đợc
xây dựng theo thứ tự giữa: đầu tiên là ký tự ở nút gốc, sau đó là các ký tự biểu diễn
cây con trái và cuối cùng là các ký tự biểu diễn cây con phải. Các xâu này đợc sắp xếp
theo thứ tự từ điển và cây đợc đánh số theo thứ tự từ điển của xâu. Mã (N, K) ký hiệu
xâu tơng ứng với cây thứ N trong các cây BST có đúng K nút.

VÝ dơ, víi K = 4, ta có 14 cây, tơng ứng với các x©u:

abcd, abdc, acbd, adbc, adcb, bacd, badc, cabd, cbad, dabc, dacb, dbac, dcab, dcba
M· (7, 4) lµ badc, tơng ứng với cây:

Yờu cu: t N v K cho trớc, xác định có bao nhiêu cây BST và mó (N,K), 0<K 26.

<i>Dữ liệu: vào từ file văn bản BST.INP, gồm nhiều dòng, mỗi dòng một cặp N, K, kết </i>

thúc là dòng chứa 2 số 0. Các số trên 1 dòng cách nhau 1 dấu cách.

<i>Kết quả: đa ra file văn bản BST.OUT, mỗi dòng tơng ứng với một cặp N, K khác 0 của </i>

dữ liệu vào, chứa số lợng cây (số nguyên ) và mà (N,K).

<i>VÝ dô:</i>

BST.INP BST.OUT

2 3
7 4

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6></div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7></div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8></div>


<!--links-->