Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

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

    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 .
    Last edited by 09520281; 12-07-2012, 09:50.
    Facebook: Kiều Thắng
    Google Plus: Kiều Thắng
    Thông tin về du học các nước: Du học.


  • #2
    ps: giống như tìm chuỗi con vậy ?
    :funny::brick::beauty::what:

    Comment


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

      Comment


      • #4
        Đâ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:
        University of Information Technology
        Cao Văn Nhàn _ CE10520355
        SĐT: 0188 403 4943

        Email: caovannhan2002@gmail.com

        Comment


        • #5
          Originally posted by 10520355 View Post
          Đâ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 ?

          Comment


          • #6
            Ý 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.
            Don't depend too much on anyone in this world. Because even your shadow leaves you when you're in darkness.

            Comment


            • #7
              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
              University of Information Technology
              Cao Văn Nhàn _ CE10520355
              SĐT: 0188 403 4943

              Email: caovannhan2002@gmail.com

              Comment


              • #8
                Ố, 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

                Comment


                • #9
                  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:
                  Don't depend too much on anyone in this world. Because even your shadow leaves you when you're in darkness.

                  Comment


                  • #10
                    :d Để biết chỉ có cách làm thử thôi :d
                    University of Information Technology
                    Cao Văn Nhàn _ CE10520355
                    SĐT: 0188 403 4943

                    Email: caovannhan2002@gmail.com

                    Comment


                    • #11
                      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:
                      Don't depend too much on anyone in this world. Because even your shadow leaves you when you're in darkness.

                      Comment

                      LHQC

                      Collapse
                      Working...
                      X