[Lập trình newbie] Mỗi ngày một bài toán (số 5)

[09520281]

Hi các bạn, dường như trải qua 4 bài toán các bạn cũng đã làm quen dần rồi phải không :sogood:. Sau đây là một bài toán mình cho khá là hay, hi vọng các bạn tiếp tục thảo luận sôi nổi như những số trước. Sau này đây sẽ là kho tư liệu bổ ích cho các bạn khóa dưới :shy:.
Bài toán số 5:

Viết các số thập phân 1,2, ... liên tiếp thu được dãy số như sau :
12345678910111213141516171819202122 ...etc.
Viết chương trình tìm vị trí xuất hiện đầu tiên của số N trong dãy trên.
Time limit 1s. Memory: 5MB

Input

Gồm duy nhất 1 số N, 1 ≤ N ≤ 100,000.

Output


Số duy nhất là vị trí xuất hiện đầu tiên của số N trong dãy.

Sample
input
15
output
20
input
34
output
3
input
142
output
73
Have fun .

[10520237]

ps: giống như tìm chuỗi con vậy ?

[10520490]

bài toán này dùng công thưc toán thôi k cần quy hoạch động đâu

[10520355]

Đây là cách của mình, mong các bạn góp ý.
Vì N <= 100 000 nên dãy số cần xét có độ dài tối đa là (1.9 + 2.90 + 3.900 + 4.9000 + 5.90000 + 6) = 488 895 <= 500 000.
Bài toán này có thể qui về thành bài toán tìm 1 chuỗi con St (độ dài <= 6) trong 1 chuỗi S (có độ dài <= 500 000). Do đó nếu dùng thuật toán tìm chuỗi con bình thường (duyệt qua chuỗi S, xét St có xuất hiện trong chuỗi S tại vị trí i hay không) thì độ phức tạp khoảng O(length(S).length(St)) ~ 3000 000, thời gian chạy sẽ dưới 1s => OK.
:happy:

[11520132]

Đây là cách của mình, mong các bạn góp ý.
Vì N <= 100 000 nên dãy số cần xét có độ dài tối đa là (1.9 + 2.90 + 3.900 + 4.9000 + 5.90000 + 6) = 488 895 <= 500 000.
Bài toán này có thể qui về thành bài toán tìm 1 chuỗi con St (độ dài <= 6) trong 1 chuỗi S (có độ dài <= 500 000). Do đó nếu dùng thuật toán tìm chuỗi con bình thường (duyệt qua chuỗi S, xét St có xuất hiện trong chuỗi S tại vị trí i hay không) thì độ phức tạp khoảng O(length(S).length(St)) ~ 3000 000, thời gian chạy sẽ dưới 1s => OK.
:happy:

còn thời gian tạo chuỗi với lại 500000 từ đó chiếm nhiu MB ta ?

[quoctinvn]

Ý tưởng của em là thế này : Gọi xâu trong input là st.
Gọi nSpace là số lượng chữ số còn lại của số đã bị cắt mất 1 phần đầu (ví dụ 1223 mà st là 223 thì nSpace = 1), còn nDigit là số chữ số hoàn chỉnh của số đó (theo như ví dụ là 2).
N ≤ 100,000 nên độ dài st không quá 6.
Xét nSpace từ 0 đến length(st), với mỗi nSpace xét nDigit từ nSpace đến length(st)-nSpace, ta lần lượt tách xâu st thành các số có nDigit chữ số, và xét xem xâu con mới tách và xâu con đã tách liền trước có là 2 số liên tiếp hay không. Nếu tất cả đều thỏa mãn, ta xác định được đây là dãy số liên tiếp nằm trong khoảng các số có nDigit chữ số, từ đó tìm được vị trí đầu tiên xuất hiện.
Chú ý là khi tách xâu st, cần để ý xem số lượng chữ số có tăng lên hay không (99 -> 100 chẳng hạn) để tách cho đúng.

[10520355]

Thời gian tạo chuỗi 500k kí tự không bao nhiêu (vì mình đã từng làm 1 bài tạo 1 triệu kí tự vẫn rất nhanh), 500k kí tự thì khoảng 1000000 byte ~ 1MB

[11520132]

Ố, vậy thì hóa ra bài này đơn giản đến zậy à :shot:
mà hiện tại em cũng chưa nghĩ ra cách nào tốt hơn

[quoctinvn]

Có lẽ bài này đơn giản như vậy thật :amazed:
ném gạch cho chủ thớt :brick::brick::brick:
nếu giới hạn lớn hơn thì có lẽ cách em ổn :sure:

[10520355]

:d Để biết chỉ có cách làm thử thôi :d

[quoctinvn]

Dạo này em bị bệnh nhác ps: cứ nghĩ thuật xong là để đấy, k check lại nữa :nosebleed: cũng may là có anh Kiều Thắng lập ra cái chủ đề này, k thì cũng lượn lượn chả biết làm gì khi onl :dreaming: