Phân Phối Quà Tặng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có $N$ món quà (đánh số từ $1$ đến $N$ ) cho $N$ con bò (đánh số từ $1$ đến $N$ ). Mỗi con bò có một danh sách ưu tiên, là một hoán vị của $N$ món quà, trong đó quà xuất hiện sớm hơn được ưa thích hơn.

Ban đầu, quà $i$ được trao cho bò $i$ . Các con bò có thể trao đổi quà với nhau, với điều kiện: sau khi trao đổi, mỗi con bò phải nhận được cùng món quà ban đầu hoặc một món quà mà nó ưa thích hơn.

Với mỗi con bò $i$ , hãy tìm món quà được ưa thích nhất mà nó có thể nhận được trong một phân phối hợp lệ bất kỳ.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Dòng thứ $i$ chứa hoán vị biểu diễn danh sách ưu tiên của bò $i$

Dữ liệu ra

$N$ dòng, dòng thứ $i$ chứa món quà được ưa thích nhất mà bò $i$ có thể nhận.

Ràng buộc

$1 \leq N \leq 500$

Ví dụ

Input	Output	Giải thích
4 1 2 3 4 1 3 2 4 1 2 3 4 1 2 3 4	1 3 2 4	Bò 2 và bò 3 có thể đổi quà: bò 2 nhận quà 3 (ưa thích hơn quà 2), bò 3 nhận quà 2 (ưa thích hơn quà 3). Bò 1 và 4 giữ nguyên.

Bình luận

Không có bình luận tại thời điểm này.