[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Trên đường đi tìm cha, cậu bé Gon lạc đến đảo Tham Lam. Hòn đảo này rất kỳ quái, người dân không dùng tiền mà dùng thẻ để trao đổi. Trên mỗi thẻ ghi một số nguyên nằm trong khoảng [1,N] và được gọi là mã số của thẻ. Chỉ có một cách duy nhất để ra khỏi đảo là đem được n thẻ có mã đôi một khác nhau (từ mã 1,2,..,N) đổi lấy vé tàu.
Gon có 2 cách để kiếm thẻ ở trên đảo:
· Nhặt thẻ mà người khác đánh rơi
· Trao đổi với ngân hàng của đảo: dùng 1 thẻ của mình đổi lấy 1 thẻ khác của ngân hàng, lệ phí 1 lần đổi là 1 cục vàng (ngân hàng dùng để đúc thẻ mới)
Rất may là Gon được một người bạn tốt bụng tặng cho n thẻ nên chỉ còn phải ra ngân hàng đổi thẻ (để được n thẻ khác nhau đôi một). Vì chuyến đi dài nên Gon phải tiết kiệm vàng. Bạn hãy giúp Gon tìm cách đổi để tốn ít vàng nhất mà vẫn đổi được vé tùa đi ra khỏi đảo. Biết rằng luôn tồn tại ít nhất một cách đổi.
Dữ liệu vào: Cho từ tệp văn bản GREED.INP
· Dòng thứ nhất ghi số nguyên N (N≤100)
· Dòng thứ hai ghi N số nguyên là mã số của N thẻ mà Gon có
· Tiếp theo là một số dòng, trên mỗi dòng chứa hai số u, v có nghĩa là có thể đổi thẻ có mã số u của Gon lấy thẻ có mã số v của ngân hàng và ngược lại.
Các dữ liệu số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản GREED.OUT một số nguyên duy nhất là tổng số vàng ít nhất phải trả khi đổi thẻ
Ví dụ:
GREED.INP
4
1 1 1 1
1 2
2 3
1 4
3 4
GREED.OUT
4
Gon có 2 cách để kiếm thẻ ở trên đảo:
· Nhặt thẻ mà người khác đánh rơi
· Trao đổi với ngân hàng của đảo: dùng 1 thẻ của mình đổi lấy 1 thẻ khác của ngân hàng, lệ phí 1 lần đổi là 1 cục vàng (ngân hàng dùng để đúc thẻ mới)
Rất may là Gon được một người bạn tốt bụng tặng cho n thẻ nên chỉ còn phải ra ngân hàng đổi thẻ (để được n thẻ khác nhau đôi một). Vì chuyến đi dài nên Gon phải tiết kiệm vàng. Bạn hãy giúp Gon tìm cách đổi để tốn ít vàng nhất mà vẫn đổi được vé tùa đi ra khỏi đảo. Biết rằng luôn tồn tại ít nhất một cách đổi.
Dữ liệu vào: Cho từ tệp văn bản GREED.INP
· Dòng thứ nhất ghi số nguyên N (N≤100)
· Dòng thứ hai ghi N số nguyên là mã số của N thẻ mà Gon có
· Tiếp theo là một số dòng, trên mỗi dòng chứa hai số u, v có nghĩa là có thể đổi thẻ có mã số u của Gon lấy thẻ có mã số v của ngân hàng và ngược lại.
Các dữ liệu số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.
Kết quả: Ghi ra tệp văn bản GREED.OUT một số nguyên duy nhất là tổng số vàng ít nhất phải trả khi đổi thẻ
Ví dụ:
GREED.INP
4
1 1 1 1
1 2
2 3
1 4
3 4
GREED.OUT
4