//
you're reading...
Bài tập huấn luyện, Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: Chia nhóm văn nghệ

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


Chọn đội tuyển dự thi quốc gia – 2015 – Bài 5


Đề bài


Để chào đón ngày Nhà giáo Việt Nam 20/11 sắp tới, một trường THPT trên địa bàn Đồng Tháp đang ráo riết tập dượt tổ chức biểu diễn văn nghệ. Sau khi tuyển chọn được n em học sinh từ các khối lớp của trường, thầy thể dục định chia họ thành các nhóm 3 người để thực hiện tiết mục múa (giả sử n là số chia hết cho 3) và mỗi học sinh phải thuộc về đúng một nhóm. Tuy nhiên, trong n em này, có một số học sinh quen nhau và thầy muốn rằng, nếu có hai học sinh nào đó quen nhau thì bắt buộc họ phải thuộc cùng một nhóm (chú ý rằng theo điều kiện này thì một nhóm không nhất thiết phải có học sinh đếu quen biết nhau). Thầy bèn đánh số các học sinh từ 1 đến n và ghi chú lại cá cặp họa sinh quen biết nhau, mỗi cặp xuất hiện không quá một lần trong danh sách của thầy. Tất nhiên A quen B thì B cũng sẽ quen A. Sau khi nhận được danh sách các cặp học sinh quan nhau này, thầy đang rất đau đấu để chia nhóm cho họ. Việc chia có thể không khó nhưng trước hết, thầy muốn biết rằng có tồn tại cách chia như vậy không. Bạn hãy giúp thầy nhé!

 

Yêu cầu: Hãy xác định xem với danh sách các cặp học sinh quen nhau đã có, thầy giáo có thể chia được tất cả học sinh này thành các nhóm 3 người mà các học sinh quen nhau đều sẽ thuộc cùng một nhóm được hay không.

 

Dữ liệu vào: Trong file CHIANHOM.INP, dòng thứ nhất gồm các số n,m cách nhau bởi một khoảng trắng chỉ số học sinh trong đội văn nghệ và số cặp học sinh quen biết nhau trong danh sách. Điều kiện 0<n<50, n chia hết cho 3 và 0≤mn(n-1)/2.

 

Trong m dòng tiếp theo, mỗi dòng gồm một cặp số nguyên dương a,b cách nhau bởi một khoảng trắng với 1≤a,bn cho biết hai học sinh có số thứ tự a,b quen biết nhau.

 

Kết quả: In vào file CHIANHOM.OUT một dòng duy nhất là “YES” nếu tồn tại cách chia thỏa mãn và “NO” nếu không tồn tại cách chia nào.

 

Ví dụ.

CHIANHOM.INP CHIANHOM.OUT
6 0 YES
6 7

1 2

2 3

3 1

1 4

2 4

3 4

5 6

NO
6 2

1 2

3 4

YES

 

Giải thích. Trong tes thứ nhất, có 6 học sinh và giữa họ, không có học sinh nào quen biết nhau nên không có sự ràng buộc, thầy giáo có thể sắp tùy ý. Trong test thứ 2, cũng có 6 học sinh, học sinh 1, 2 qien nhau nên sẽ cùng nhóm, học sinh 2, 3 quen nhau nên cũng cùng nhóm, học sinh 3, 4 quen nhau nên cùng nhóm; dẫn đến bắt buộc các học sinh 1, 2, 3, 4 phải cùng nhóm; điều này là không được do mỗi nhóm chỉ có 3 người. Trong test thứ 3, có thể chia thàh nhóm (1, 2, 5), (3, 4, 6) thì thỏa mãn điều kiện đề bài (chú ý rằng học sinh 5 không quen học sinh 1 và 2, học sinh 6 không quen học sinh 3 và 4 nhưng họ vẫn chung nhóm được).


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 210,510 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: