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

[MrPaint]

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]

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]

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]

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ì sad .

[Junior IT]

Nhân đôi dãy tức là
S[length(S) + 1] = S[1]
S[length(S) + 2] = S[2]
...

[danceswithwolves]

"nhân đôi dãy" theo kiểu Junior@ hơi phí mem. Duyệt vòng bằng toán tử mod (%) là okie rồi.

[MrPaint]

Hóa ra là thế đó, cám ơn các bạn thật nhiều nhé!