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