KHIÊU VŨ

Một làng quê có m chàng trai đánh số từ 1 tới m và n cô gái đánh số từ 1 tới n. Chàng trai thứ i có chiều cao a_i (i = 1,2 ,…,m), cô gái thứ j có chiều cao b_j ( j = 1, 2, …n).

Trong một buổi khiêu vũ, người ta muốn chọn ra một số cặp nhảy. Mỗi cặp nhảy gồm đúng 1 chàng trai và 1 cô gái và trong cặp đó, chàng trai phải cao hơn cô gái. Mỗi chàng trai, cô gái trong làng không được tham gia quá 1 cặp nhảy.

Yêu cầu: Tìm một số nhiều nhất các cặp nhảy thỏa mãn yêu cầu trên.

Dữ liệu: Vào từ file văn bản DANCE.INP

·         Dòng 1 chứa hai số nguyên dương m,n < 10⁵

·         Dòng 2 chứa m số nguyên dương a_1, a₂, …, a_m  (a[i] < 10⁹)

·         Dòng 3 chứa n số nguyên dương b_1, b₂, …, b_m  (b[i] < 10⁹)

Kết quả: Ghi ra file văn bản DANCE.OUT một số nguyên duy nhất là số cặp nhảy theo phương án tìm được.

Ví dụ:

DANCE.INP	DANCE.OUT
3 2 1 2 3 2 3	1

Chú ý: Ít nhất 50% số điểm ứng với các test có m,n < 1000.

TEST

DÃY SỐ FIBONACCI

Dãy số nguyên a₁, a₂, . . ., a_m được gọi là dãy số Fibonacci nếu thoả mãn một trong các điều kiện sau:

• m = 2,
• a_i+1 = a_i + a_i-1 với m > i ≥ 2.

Ví dụ: Các dãy số sau là dãy số Fibonacci:

            5,-2

            5,-2,3,1,4,5,9,14,23

Với dãy số nguyên  cho trước b₁, b₂, . . ., b_n (n ≥ 2) người ta luôn luôn có thể gạch bỏ một số phần tử của dãy để dãy còn lại (giữ nguyên thứ tự trong dãy ban đầu) là một dãy số Fibonacci.

Ví dụ, từ dãy số cho trước

            5,-2,50,3,1,4,5,60,9,14,23

ta có thể nhận được dãy Fibonacci bằng cách gạch bỏ khỏi dãy các phần tử thứ tám (số 60) và phần tử thứ ba (số 50).

Yêu cầu: Cho số nguyên dương n và dãy số nguyên b₁, b₂, . . ., b_n. Hãy tìm cách gạch bỏ ít nhất các phần tử của dãy để nhận được dãy Fibonacci.

Dữ liệu: Vào từ file văn bản GFIB.INP:

• Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 1 000);
• Dòng thứ hai chứa n số nguyên b₁, b₂, . . ., b_n (|b_i| ≤ 10⁶_, 1 ≤ i ≤ n ).

Các số trên một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản GFIB.OUT số lượng ít nhất các phần tử cần gạch bỏ.

GFIB.INP	GFIB.OUT
11 5 -2 50 3 1 4 5 60 9 14 23	2

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 2 ≤ n ≤ 100.

TEST

SO SÁNH

Cho hai số thực A và B, hãy so sánh hai số thực và đưa ra thông báo “>”, “<” hoặc “=”.

Input

-          Dòng 1: là số A (có không quá 20000 ký tự)

-          Dòng 2: là số B (có không quá 20000 ký tự)

Output

-          Đưa ra thông báo “>”, “<” hoặc “=”.

COMPARE.INP	COMPARE.OUT
2.39 3.61	<
123 12.3	>
12345678 12345678.0	=

 TEST

ĐƯỜNG NGUYÊN TỐ

Cho hai số nguyên tố khác nhau có bốn chữ số. Người ta cho rằng hoàn toàn có thể biến đổi từ số này thành số kia sau một số bước theo quy tắc: Tại mỗi bước ta chỉ thay đổi một chữ số trong số trước đó sao cho số tạo được trong mỗi bước đều là một số nguyên tố có bốn chữ số. Một cách biến đổi như vậy gọi là một “đường nguyên tố”.

Bài toán đặt ra là với một cặp số nguyên tố đầu vào, hãy tính ra số bước của đường nguyên tố ngắn nhất. Giả sử đầu vào là hai số 1033 và 8179 thì đường nguyên tố ngắn nhất sẽ có độ dài là 6 với các bước chuyển là: 1033 ->  1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179

Dữ liệu vào: Từ tệp văn bản DUONGNT.INP

Gồm 2 số nguyên tố u và v, mỗi số có đúng 4 chữ số cõ nghĩa.

Dữ liệu ra: ghi vào tệp văn bản DUONGNT.OUT

Số bước của đường nguyên tố ngắn nhất của 2 số nguyên u và v.

Ví dụ:

DUONGNT.INP	DUONGNT.OUT
1033 8179	6

BỘ BA CAO THỦ

Nguồn: http://vn.spoj.com/problems/NKTRIO

Ở thời loạn, giang hồ có rất nhiều cao thủ võ lâm, mỗi người trong số họ lại có những tuyệt chiêu. Nếu 2 cao thủ giang hồ so tài với nhau thì từ những sở trường và sở đoản của họ, ta có thể biết trước được cao thủ nào sẽ thắng. Những cao thủ đang có ở VNOI như conankudo, gothdn, kaiel, nahnhnahk, pirate... đang muốn thi tài để xem ai được chọn làm bộ ba cao thủ.

Để mưu nghiệp lớn, minh chủ võ lâm Nuga cần tìm ra một bộ ba trong số các cao thủ giang hồ hiện tại. Để các cao thủ này quy phục dưới trướng của mình và không làm phản, Nuga muốn bộ ba cao thủ này có thể khắc chế được nhau; điều này có nghĩa là nếu 3 cao thủ được chọn là A, B và C thì A phải thắng được B, B phải thắng được C và C phải thắng được A.

Bạn hãy giúp Nuga chọn ra một bộ ba cao thủ thoả mãn yêu cầu của ông.

Dữ liệu vào: Từ tệp văn bản NKTRIO.INP

Dòng đầu tiên ghi n là số cao thủ trên giang hồ (3 ≤ n ≤ 1000)

Tiếp theo là n dòng, mỗi dòng có n số. A[i,j] = 1 là người i thắng j. Dữ liệu luôn đảm bảo A[i,j] + A[j,i] = 1. A[i,i] = 0 với mọi i.

Dữ liệu ra: ghi vào tệp văn bản NKTRIO.OUT

Ghi ra ba số nguyên A, B và C là thứ tự của ba cao thủ thoả mãn A thắng B, B thắng C và C thắng A. Trong trường hợp có nhiều cách lựa chọn, bạn chỉ cần chỉ ra một cách; trong trường hợp không có cách lựa chọn thoả mãn yêu cầu, ghi ra ba số -1.

Ví dụ:

NKTRIO.INP	NKTRIO.OUT
5 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0	2 3 5
3 0 1 1 0 0 1 0 0 0	-1 -1 -1

TRÒ CHƠI CÁC Ô VUÔNG THẦN BÍ

Xét một bảng có 8 ô vuông trong đó mỗi ô vuông có một màu khác nhau, các mùa được ký hiệu bởi 8 số nguyên dương đầu tiên. Các trạng thái của bảng được cho bởi dãy ký hiệu màu của các ô được viết lần lượt theo chiều kim đồng hồ bắt đầu từ góc trái trên và kết thúc ở góc trái dưới.

1	2	3	4
8	7	6	5

Ví dụ trạng thái của bảng trong hình trên được cho bởi dãy (1, 2, 3, 4, 5, 6, 7, 8). Trạng thái này được gọi là trạng thái khởi đầu.

Có thể dùng 3 phép biến đổi cơ bản có tên là ‘A’, ‘B’, ‘C’  trong đó:

      ‘A’: Đổi chỗ dòng trên và dòng dưới

      ‘B’: thực hiện một phép hoán vị vòng quanh sang phải

      ‘C’ Quay theo chiều kim đồng hồ 4 ô giữa

Biết rằng từ trạng thái khởi đầu luôn có thể chuyển về một trạng thái bất kỳ bằng cách dùng các phép biến đổi cơ bản nói trên. Tác động của 3 phép biến đổi cơ bản được mô tả trong hình sau:

+ Phép A

1	2	3	4		1	2	3	4
1	2	3	4	A →	8	7	6	5
8	7	6	5		1	2	3	4
8	7	6	5		8	7	6	5

+ Phép B

1	2	3	4		1	2	3	4
1	2	3	4	B →	4	1	2	3
8	7	6	5		5	8	7	6
8	7	6	5		8	7	6	5

+ Phép C

1	2	3	4		1	2	3	4
1	2	3	4	C →	1	7	2	4
8	7	6	5		8	6	3	5
8	7	6	5		8	7	6	5

Trong đó các số viết bên cạnh bảng dùng để chỉ các ô vuông của bảng và ô vuông ở vị trí p chứa số i có nghĩa là sau khi áp dụng phép biến đổi tương ứng ô vuông mà vị trí trước khi biến đổi của nó là i được chuyển đến vị trí p

Yêu cầu: Viết chương trình tìm dãy biến đổi cơ bản để chuyển bảng từ trạng thái khởi đầu về một trạng thái cho trước sao cho số phép biến đổi là ít nhất có thể.

Dữ liệu vào: File OVUONG.INP chứa 8 số nguyên liền nhau mô tả trạng thái đích

Dữ liệu ra: ghi vào file OVUONG.OUT

+ Dòng đầu tiên ghi số phép biến đổi của dãy

+ Các dòng tiếp theo ghi dãy các phép biến đổi theo thứ tự, mỗi phép biến đổi ghi trên một dòng

Ví dụ:

OVUONG.INP	OVUONG.OUT
26845731	7 B C A B C C B

TEST - Đề (word)

QUÂN TƯỢNG

Nguồn: http://vn.spoj.com/problems/QBBISHOP/

Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (r_i, c_i), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

Dữ liệu vào: Từ tệp văn bản QBBISHOP.INP

+ Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.

+ Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:  Ghi vào tệp văn bản QBBISHOP.OUT

Gồm 1 dòng duy nhất là số nước đi tìm được

Ví dụ:

QBBISHOP.INP	QBBISHOP.OUT
8 3 7 2 1 4 5 4 3 4 4 7	3

Hạn chế:

Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.