Một bài toán rất hay

**MrPaint** · 25-06-2004 05:23

Có 1 băng giấy tròng trên đó ghi dãy các số 0 và 1. Có thể cắt băng giấy ở một vị trí bất kỳ để thu được 1 số gồm toàn các chữ số 0 và 1.

Ví dụ: Với dãy số ở trên băng giấy là 010010110001100 nếu cắt ở vị trí sau số 1 cuối cùng từ trái sang ta thu được số 000100101100011.

Yêu cầu: tìm vị trí cắt băng giấy để số thu được là nhỏ nhất.

Dữ liệu: vào từ file văn bản 01NUMBER.INP gồm 1 dòng chứa dãy số 0,1 viét trên băng giấy (số lượng chữ số trên băng giấy không quá 30000).

Kết quả: ghi ra file văn bản 01NUMBER.OUT vị trí cắt tìm được (các vị trí của các chữ số trên băng giấy được đánh số theo thứ tự xuất trong file dữ liệu, bắt đầu từ 1). Nếu có nhiều lời giải thì chỉ cần đưa ra 1 trong số chúng.

Ví dụ: 01NUMBER.INP - 010010110001100 --> 01NUMBER.OUT - 13

**Junior IT** · 25-06-2004 08:11

Bài này giống bài Password trên VNOPSC nhỉ
http://www.mg9h.5chau.com/contest/PASSWORD.DOC

Cách đơn giản nhất là bạn nhân 2 cái dãy đó lên rồi duyệt thôi

**MrPaint** · 25-06-2004 17:57

Mình vẫn chưa thực sự hiểu ý của bạn.
Bạn có thể nói rõ hơn một chút được không?

**consoilangthang** · 25-06-2004 21:57

1. search phân đoạn có nhiều số 0 liên tiếp nhất, cắt ngay trước số 0 đầu tiên. Ở ví dụ của bạn

Ví dụ: 01NUMBER.INP - 010010110001100 --> 01NUMBER.OUT - 13

thì dãy số 0 liên tiếp dài nhất có 3 số 0 (in đậm).
2. trường hợp có nhiều phân đoạn 0 dài nhất bằng nhau thì xét tiếp xem đoạn sau, trường hợp nào xuất hiện số 0 sớm nhất là trường hợp cần tìm. Vd.
00010101***XX <--- cái này bé hơn nè
00011011***XX

không biết có hiểu sai ý bạn không chứ bài này... đâu có hay gì

.