Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

V8ORG - Tổ chức đối lập

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/v8org


Ở một đất nước nọ, lực lượng an ninh vừa phát hiện một tổ chức đối lập. Tổ chức đối lập này được tổ chức chặt chẽ, bao gồm mạng lưới thành viên và chỉ huy ở các cấp bậc khác nhau. Các thành viên của tổ chức được đánh số từ 1 đến N. Tổ chức có một chỉ huy tối cao, luôn được đánh số 1. Mỗi thành viên chỉ biết viên chỉ huy trực tiếp của mình (có duy nhất một viên chỉ huy trực tiếp) chứ không biết các chỉ huy cấp cao hơn.

Khi tiến hành việc bắt giữ các thành viên, tổ chức sẽ bị phân rã thành các nhóm nhỏ không liên kết với nhau, ví dụ sau khi bắt giữ thành viên số 2 (hình 1), tổ chức bị phân rã thành 4 nhóm. Lực lượng an ninh khẳng định, một nhóm chứa ít hơn K thành viên sẽ không còn là mối đe dọa cho đất nước. Để không làm giảm hình ảnh của đất nước trước dư luận quốc tế, các nhà lãnh đạo an ninh muốn bắt giữ một số lượng ít nhất phần tử đối lập, sao cho các nhóm bị phân rã đều không còn gây nguy hại cho đất nước.

Cho biết cấu trúc của tổ chức đối lập, việc chương trình giúp các nhà lãnh đạo an ninh xác định số lượng phần tử đối lập ít nhất cần bắt giữ.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên K (1 ≤ K ≤ 10000).
  • Dòng thứ hai chứa số nguyên N (1 ≤ N ≤ 10000).
  • Dòng thứ ba chứa N-1 số nguyên cách nhau bởi khoảng trắng, chỉ số của chỉ huy trực tiếp của mỗi phần tử của tổ chức (trừ chỉ huy tối cao): số đầu tiên cho biết chỉ huy của phần tử thứ hai, số thứ hai cho biết chỉ huy của phần tử thứ ba,...

Kết qủa

In ra một số nguyên duy nhất là số phần tử đối lập ít nhất cần bắt giữ.

Ví dụ

Dữ liệu Kết quả Mô tả
3
14
1 1 2 2 3 2 3 6 6 6 7 4 7
Hình 1
4
Có thể bắt giữ 4 phần tử 6, 2, 7 và 8.

Được gửi lên bởi:Jimmy
Ngày:2008-03-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Russian Training / vCoder08

hide comments
2014-08-31 18:25:27 Thcs Ðặng Chánh Kỷ
@@@ clgt duyệt thôi bạn ơi, đừng nghĩ phức tạp quá
2014-08-31 18:18:25 càng code càng buồn ðời
làm kiểu khác phức tạp hơn cuối cùng cũng
điểm cũng = cách bạn Võ Đài Dũng
2014-08-23 20:29:06 Thcs Ðặng Chánh Kỷ
có nhiều bài tưởng chừng là dễ nhưng thực chất là rất dễ, bài này là 1 ví dụ , ngồi duyệt cũng ăn được, vãi bài
2014-02-21 15:48:42 Anh Duc Le
DFS + tham lam
2013-11-11 11:50:43 dffff
chỉ cần write((n-1)div k) là được 45.45 điểm
2013-10-29 15:13:55 Phạm Vãn Huân
Bài này có gì đâu, từ cái dãy số kia quy về được ma trận kề của đồ thị, từ đó tính được bậc của mỗi đỉnh. Đỉnh nào có bậc >=K thì "bắt" nó => phá vỡ được tổ chức
2013-06-27 14:29:38 Bitagi97
Nghĩ đơn giản cho đời thanh thản :v :v
2013-05-19 05:00:37 a;slkfjasl;fkj
cũng hay :)

Last edit: 2013-06-25 15:56:23
2013-02-24 15:39:40 @Love@
Bạn NTQ code có 5 dòng á @@
2011-08-29 04:04:51 St.VDQD
bài này hình như còn sắp xếp theo Tôpô nữa chứ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.