Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Một bài toán trên spoj

  1. #1
    Ngày gia nhập
    03 2015
    Bài viết
    16

    Unhappy Một bài toán trên spoj

    Xét các số nguyên từ 1 đế N. Các số này được sắp xếp theo thứ tự từ điển. Ví dụ với N=11, ta có dãy số sau khi sắp xếp là 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

    Ký hiệu QN,K là vị trí của số K trong dãy được sắp xếp theo cách nói trên. Ví dụ Q11,2=4 Cho các số nguyên K và M. Hãy tìm số nguyên N nhỏ nhất thỏa mãn QN, K=M
    Dữ liệu vào
    Dòng đầu tiên chứa số nguyên t cho biết số bộ test.
    Mỗi bộ test bao gồm 1 dòng duy nhất chứa 2 số nguyên K và M (1<=K,M<=10^9)
    Kết qủa
    Với mỗi bộ test xuất ra số N, hoặc 0 nếu không tồn tại N

    Bài này em ý tưởng thế này, giả sử k = apap-1...a1, nếu:
    1. k = 10i i>= 0 thì vị trí của k là bất biến
    2. chỉ có các số sau là đứng trước k trong dãy từ 1..n
    +) 1 ... a1
    +) 10 ... a1a2
    ...........................
    +)10^(p-1) ... k -1
    +) 10^p...10*k-1
    .............
    +)10^(p+i) ... s, với i là số tự nhiên lớn nhất thỏa mãn 10^(p+i) < n và s = n nếu s< 10^(p+i) * k -1, và s = 10^(p+i) * k -1, nếu n >= 10^(p+i) * k -1
    Nói hơn khó hiểu ví dụ đơn giản là nếu k = 4567, n = 3421342, thì các số đứng trước k là
    +) 1..4
    +) 10..45
    +) 100..456
    +) 1000...4566
    +)10^4...45670-1
    +)10^5..456700-1
    +)10^6...3421342
    từ đó suy ra q(n, k) = 4 + 36+(456-100+1) + (4566 - 1000+1) + (45670-10^4) + (456700-10^5) + (3421342 - 10^6 +1) + 1 = 2817678
    Cho hỏi em làm thế có đúng không mà nộp bài toàn bảo sai
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi QuangTrung93 : 01-02-2016 lúc 12:11 PM.

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    474

    trước hết em viết 1 hàm duyệt trâu sắp xếp theo thứ tự từ 1 tới N để tìm Q(N,K), rồi kiểm tra Q(N,K) này với hàm mới chạy nhanh hơn của mình.

    C++ Code:
    1. #include <iostream>
    2. #include <string>
    3. #include <set>
    4.  
    5. int main()
    6. {
    7.     int n = 3421342;
    8.     int k = 4567;
    9.    
    10.     std::set<std::string> s;
    11.     for (int i = 0; i < n; s.insert(std::to_string(++i)));
    12.     std::cout << std::distance(s.begin(), s.find(std::to_string(k))) + 1 << "\n";
    13. }
    http://ideone.com/qAdxOX
    kết quả là 2817678 chính xác mà
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn