Vòng thi thử - Hội thi tin học

[ngtrhieu0011]

Bunch

Cho N ly nhựa, đánh số từ 1 đến N và xếp thành một dãy trên bàn thành một dãy theo thứ tự tăng dần từ trái sang phải tạo thành N chồng ly, mỗi chồng có một ly. Dãy các chồng ly này được gom lại nhờ các phép di chuyển cho dưới dạng a b: xếp chồng ly chứa ly a lên trên chồng có ly b (nếu các ly a và b ở cùng một chồng hoặc a = b thì trạng thái các chồng ly không thay đổi). Ví dụ, với N = 7 và 5 phép di chuyển 13, 26, 16, 47, 42, dãy các chồng ly sẽ thay đổi như sau:
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
1 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * * *
* 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * 2 *
* * 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * 4 5 6 7


* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 4
* * * * 5 6 7

* * * * * 4 *
* * * * * 7 *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * * 5 6 *

Yêu cầu: Cho trước M phép di chuyển. Hãy xác định số ly có trong chồng có nhiều ly nhất sau khi thực hiện một phép di chuyển nào đó rồi thực hiện tiếp M phép di chuyển này (thực hiện cả thảy M+1 phép di chuyển).

Dữ liệu: Vào từ file văn bản BUNCH.INP:
• Dòng đầu tiên chứa lần lượt hai số nguyên N, M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000)
• M dòng sau: mỗi dòng chứa hai số nguyên a, b xác định một phép di chuyển.

Kết quả: Đưa ra file văn bản BUNCH.OUT trên một dòng số nguyên, là số ly tìm được.

Ví dụ:
BUNCH.INP
6 4
5 2
3 3
1 3
6 2
BUNCH.OUT
5
Giải thích
-Đầu tiên ta thực hiện phép di chuyển 61 (hoặc 16)
-Tiếp theo ta thực hiện 4 phép di chuyển như mô tả trong file BUNCH.INP thì được chồng ly có số đĩa nhiều nhất là 5.
-Không còn cách nào khác để có chồng ly với 6 đĩa trở lên.

[bld]

ủa theo quy định là gửi vào email của bgk mà
chạy thử với ct của quang rồi , nhanh đấy ! nhưng ko biết đúng ko

[m2mpro]

Bài này chỉ cần có 1 nhận xét đơn giản là có thuật toán đúng thôi

[bld]

@ anh hieu : chừng nào thì hết hạn nộp bài vậy a , bài này khó quá ^^', ko biết cách e làm có đúng ko nữa ... đang code , sẽ nộp code qua tin nhắn của a @ a m2mpro ,

[quangtq]

Sao lại ko biết đúng không. Bạn có test thì test hộ.
Do trình ruồi nên suy nghĩ cũng rất bình thường, ko có sử dụng thuật toán nào hết. Ko qhd, ko quay lui v.v.., chỉ dựa vào đề bài
P/S: quên mất. Post luôn ở đây rồi

[ngtrhieu0011]

yêu cầu bạn Quangtp xóa code đi nhá, nộp wa mail thôy, chép ở đây coi như là share code đó

[=========> Bổ sung bài viết <=========]

nộp qua ngtrhieu0011@gmail.com

[linhhahaduc]

Ko biết mình có hiểu nhầm đề ko! Hình như bài này là tìm thành phần liên thông có nhiều đỉnh nhất hả ?

[=========> Bổ sung bài viết <=========]

P/s : Time limit bài này bao nhiêu vậy ?

[ngtrhieu0011]

không nói jì thì hiểu là 1s nhé ^^

[quangtq]

Đã gửi vào mail. Check đi anh
P/S: Sao anh cứ nhầm chữ p với q thế nhỉ

[linhhahaduc]

Hội thi này bao giờ thi có kết quả nhỉ ? :X hồi hộp ghê