bài 1: đảo tham lam
trên đường đi tìm cha thì cậu bé gon bị 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 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 N thẻ có mã số đôi một cách khác nhau (tức là có mã số 1,2,..,N) đổi lấy vé tàu.
gon có 2 cách để kiếm thẻ ở trên đảo:
1: nhặt thẻ mà người khác đánh rơi.
2: Trao đổi với ngân hàng của đảo: dùng 1 thẻ cùng mình đổi lấy 1 thẻ khác của ngân hàng, lệ phí 1lần 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 tốt bụng tặng cho N thẻ chỉ còn phải ra ngân hàng đổi thẻ. Vì chuyến đi còn dài nên gon phải tiết kiệm vàng. Bạn hãy giúp gon, lập trình tiềm cách đổi để tốn ít vàng nhất mà vẫn đổi được vé tàu 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 GREED.INP:
1: dòng thứ nhất chứa số nguyên N( N<100)
2:dòng thứ 2 ghi N số nguyên là mã số của N thẻ mà Gon có.
3: 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 là của gon lấy mã thể có mã số v của ngân hàng và ngược lại.
KẾT QUẢ: ghi ra file GREED.OUT:
1: ghi tổng số vàng ít nhất phải trả khi đổi thẻ.
các dữ liệu số trên cùng một số dòng được ghi cách nhau ít nhất một dấu cách.
vd:
| GREED.INP | GREED.OUT |
|
4 1 1 1 1 1 2 2 3 1 4 3 4 |
4 |
các bạn có thể làm bằng các ngôn ngữ như {pascal, c++, python, java}
MONG các chuyên viên tin học ở học 24 và cô @Nguyễn Minh Lệ mong các bạn giúp mình làm bài này
Có thể nhậy 4 cặp u,v hay có thể nhiều hơn hoặc ít hơn vậy bạn?
