0.Phân loại lịch sử


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Nhiều vấn đề trong Khoa học Máy tính liên quan đến tối đa hóa một số biện pháp theo các khó khăn. Xem xét một kỳ thi lịch sử, trong đó sinh viên được yêu cầu đưa một số sự kiện lịch sử vào lịch trình- Thứ tự ical.

Sinh viên đặt hàng tất cả các sự kiện một cách chính xác sẽ nhận được tín dụng đầy đủ, nhưng làm thế nào nên một phần Tín dụng được trao cho những sinh viên không xếp hạng chính xác một hoặc nhiều sự kiện lịch sử?

Một số khả năng cho tín dụng một phần bao gồm: 1. 1 điểm cho mỗi sự kiện có xếp hạng phù hợp với thứ hạng chính xác của nó 2. 1 điểm cho mỗi sự kiện trong chuỗi sự kiện dài nhất (không nhất thiết phải tiếp nối) Đúng thứ tự tương đối với nhau.

Ví dụ

Nếu bốn sự kiện được đặt chính xác 1 2 3 4 thì lệnh 1 3 2 4 sẽ nhận được một điểm số Của 2 sử dụng phương pháp đầu tiên (các sự kiện 1 và 4 được xếp hạng chính xác) và 3 điểm bằng cách sử dụng thứ hai (Các chuỗi sự kiện 1 2 4 và 1 3 4 đều đúng thứ tự so với nhau). Trong vấn đề này bạn được yêu cầu viết một chương trình để ghi các câu hỏi như vậy bằng cách sử dụng phương pháp thứ hai.

Cho trình tự thời gian chính xác của n sự kiện 1 , 2 , ..., n như c 1 , c 2 , ... c n trong đó 1 ≤ c i ≤ n biểu thị Thứ hạng của sự kiện i đúng thứ tự thời gian và một chuỗi câu trả lời của học sinh r 1 , r 2 , ..., r n Trong đó 1 ≤ r i ≤ n biểu thị thứ tự thời gian được đưa ra bởi sinh viên với sự kiện i ; Xác định chiều dài Của các chuỗi dài nhất (không nhất thiết phải tiếp nối) các sự kiện trong các phản hồi của sinh viên được trong Đúng thứ tự thời gian tương đối so với nhau.

Đầu vào

Tệp nhập chứa một hoặc nhiều trường hợp thử nghiệm, mỗi tệp này đều được mô tả dưới đây.

Dòng đầu tiên của đầu vào sẽ bao gồm một số nguyên n cho biết số sự kiện với 2 ≤ N ≤ 20.

Dòng thứ hai sẽ chứa n số nguyên, cho biết trình tự thời gian chính xác của n sự kiện.

Các dòng còn lại sẽ bao gồm n số nguyên với mỗi dòng đại diện cho một niên đại của học sinh Đặt hàng của n sự kiện.

Tất cả các dòng sẽ chứa n số trong dải [1 ... n ], với mỗi số Xuất hiện chính xác một lần trên mỗi dòng, và với mỗi số được tách ra từ các con số khác trên cùng một đường Bằng một hoặc nhiều không gian.

Đầu ra

Đối với mỗi trường hợp thử nghiệm, đầu ra phải tuân theo mô tả dưới đây Đối với mỗi xếp hạng của sinh viên về các sự kiện, chương trình của bạn sẽ in ra số điểm cho bảng xếp hạng đó.

Có Nên là một dòng đầu ra cho mỗi bảng xếp hạng của sinh viên. Cảnh báo: Đọc cẩn thận mô tả và xem xét sự khác biệt giữa 'đặt hàng' và 'xếp hạng'.

VÍ DỤ

INPUT

4

4 2 3 1

1 3 2 4

3 2 1 4

2 3 4 1

10

3 1 2 4 9 5 10 6 8 7

1 2 3 4 5 6 7 8 9 10

4 7 2 3 10 6 9 1 5 8

3 1 2 4 9 5 10 6 8 7

2 10 1 3 8 4 9 5 7 6

OUTPUT

1

2

3

6

5

10

9


Comments

There are no comments at the moment.