Announcement

Collapse
No announcement yet.

Về bài K - ACM Miền Trung 10/10/2015

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

  • [C++] Về bài K - ACM Miền Trung 10/10/2015

    Đề:
    a.png

    Em chạy hết mọi ngóc ngách rồi, tuy code hơi bựa nhưng không thể nào sai được, vậy mà submit cứ bị Wrong Answer :surrender:

    Ai giúp em tìm ra test hiểm và bug trong code em với ạ, em cảm ơn nhiều!


    Ý tưởng: Chạy từ đầu đến cuối dãy, ở mỗi lượt chạy, tính tổng các dãy con tạo bởi phần từ đang xét và các phần tử theo sau nó, khi gặp
    dãy con có tổng >= k thì thoát ra, trước khi thoát có ghi nhận độ dài để tìm min độ dài nhằm làm kết quả cuối cùng. Ở cuối hàm main là
    một loạt if để bắt các test hiểm.

    // biến trong bài: n <-> N, k <-> S, s là biến tạm để tính tổng mỗi dãy con, l là chiều dài tạm của mỗi dãy con, m là kết quả cần xuất.

    Code em:
    Code:
    #include <iostream>
     
    using namespace std;
     
    int main() {
        int n, k;
        cin >> n >> k;
        int a[100000];
        for (int i = 0; i < n; i++)
            cin >> a[i];
        a[n++] = 0;
        int m = n, s, l;
        for (int i = 0; i < n; i++) {
            s = a[i], l = 1;
            for (int j = i + 1; j < n; j++) {
                if (s >= k) {
                    if (l < m)
                        m = l;
                    break;
                }
                s += a[j];
                l++;
            }
        }
        if (m > n - 1 || n - 1 == 1 && a[0] < k) {
            cout << 0 << '\n';
            return 0;
        }
        if (n - 1 == 1 && a[0] >= k) {
            cout << 1 << '\n';
            return 0;
        }
        cout << m << '\n';
        return 0;
    }
    Last edited by 15520878; 10-10-2015, 15:34. Reason: bổ sung thông tin

  • #2
    À đọc nhầm đề, thôi rút kinh nghiệm lần sau
    Last edited by 14520848; 11-10-2015, 09:40.

    Comment


    • #3
      À còn nữa, cấp phát biến dùng long long n. Int không đủ bộ nhớ thì phải ( nói chung khai báo biến cứ quất long long cho chắc cứ )

      Comment


      • #4
        em canh hết rồi anh :beauty: bảo đảm chạy đúng yêu cầu đề, ngon lành cành đào ko TLA được :embarrassed: mà cái này là dãy con liên tiếp mà anh chơi sort thì hỏng hết thứ tự rồi :brick:

        anh còn rảnh thì tìm hộ em test hiểm với ạ, chứ em bao hết rồi mà vẫn còn thủng :doubt:

        Comment


        • #5
          Thật ra mình nghĩ ko phải do code mà là do bạn đọc ko kĩ đề, Input có ghi rõ là "multiple test case", chương trình của bạn khi submit chỉ chạy được mỗi 1 test nên sẽ bị trả về WA.

          Comment


          • #6
            Originally posted by 13520469 View Post
            Thật ra mình nghĩ ko phải do code mà là do bạn đọc ko kĩ đề, Input có ghi rõ là "multiple test case", chương trình của bạn khi submit chỉ chạy được mỗi 1 test nên sẽ bị trả về WA.
            Không đâu anh, thi ACM dạng đề này mình chỉ cần viết 1 trường hợp đơn lẻ, khi chấm nó sẽ tự chạy lại ở mỗi test, còn dạng nữa là nó cho sẵn số case khi đó mới như anh nói. Hồi trước em đã thử lặp vô hạn rồi nhét code vào nhưng bị TLA, sau khi sửa lại dạng chạy đơn thì mới submit thành công.

            Comment


            • #7
              Originally posted by 14520848 View Post
              Bài này mình nghĩ bạn nên sort list từ to đến nhỏ. Sau đó cộng từ từ tử đầu đến cuối đến khi to hơn thoát ra và trả về kết quả. Vì nếu dãy không sắp xếp mà cộng thì với các dãy có trăm ngàn thì chạy hết là không khả thi và có thể time out :v :v .
              Mà thi xong có giáo viên hướng dẫn sao không hỏi trực tiếp luôn :beatbrick: . Lần trước mình tham gia và bị cái lỗi cấp phát bộ nhớ, code block chạy sai visual chạy đúng cũng đi hỏi :v :v
              chắc bạn chưa đọc kỹ đề, "Bài này mình nghĩ bạn nên sort list từ to đến nhỏ. Sau đó...." :go:

              Comment


              • #8
                tắt máy đi ngủ:shot:

                Comment


                • #9
                  Originally posted by 15520878 View Post
                  Không đâu anh, thi ACM dạng đề này mình chỉ cần viết 1 trường hợp đơn lẻ, khi chấm nó sẽ tự chạy lại ở mỗi test, còn dạng nữa là nó cho sẵn số case khi đó mới như anh nói. Hồi trước em đã thử lặp vô hạn rồi nhét code vào nhưng bị TLA, sau khi sửa lại dạng chạy đơn thì mới submit thành công.
                  Theo anh thì em nhầm ở chỗ này rồi. Theo kinh nghiệm của a thì bài này trong 1 test sẽ có thể có nhiều test case luôn. Trong khi chương trình của em chỉ đúng cho trường hợp 1 test có 1 test case thôi.

                  Nói 1 cách đơn giản khi chạy bạn copy 4 dòng trong sample input vào console, nếu chương trình của bạn in ra 2 dòng như trong sample output thì mới đúng.

                  Comment


                  • #10
                    Code đã AC :funny:
                    PHP Code:
                    #include <stdio.h>
                    #include <stdlib.h>

                    unsigned long long minSubArray(int s,inta,unsigned long long n)
                    {
                        
                    unsigned long long sum=a[0],head=0,tail=0,min=n+1;
                        while(
                    tail<n)
                        {
                            if(
                    tail-head+1<min && sum>=smin=tail-head+1;
                            if(
                    sum>=ssum-=a[head++];
                            else 
                    sum+=a[++tail];
                            if(
                    head>tailtail=head;
                        }
                        return 
                    min==n+1?0:min;
                    }

                    int main()
                    {
                        
                    unsigned long long n,s;
                        while(
                    scanf("%llu%llu",&n,&s)==2)
                        {
                            
                    inta;
                            
                    a=(int*)calloc(sizeof(int),n);
                            
                    unsigned long long i;
                            for(
                    i=0;i<n;i++) scanf("%d",&a[i]);
                            
                    printf("%llu\n",minSubArray(s,a,n));
                        }
                        return 
                    0;

                    Last edited by 13520803; 11-10-2015, 00:18.

                    Comment


                    • #11
                      Originally posted by 15520878 View Post
                      Không đâu anh, thi ACM dạng đề này mình chỉ cần viết 1 trường hợp đơn lẻ, khi chấm nó sẽ tự chạy lại ở mỗi test, còn dạng nữa là nó cho sẵn số case khi đó mới như anh nói. Hồi trước em đã thử lặp vô hạn rồi nhét code vào nhưng bị TLA, sau khi sửa lại dạng chạy đơn thì mới submit thành công.
                      Dạng đề nào thì dạng nhưng paste cái ví dụ vô nó phải ra giống mới đúng em ơi. Anh Cao Văn An có nói ở trên rồi đó, cái này chắc em xui

                      Comment


                      • #12
                        Originally posted by 14520820 View Post
                        chắc bạn chưa đọc kỹ đề, "Bài này mình nghĩ bạn nên sort list từ to đến nhỏ. Sau đó...." :go:
                        Originally posted by 15520878 View Post
                        Đề:
                        [ATTACH=CONFIG]17845[/ATTACH]

                        Em chạy hết mọi ngóc ngách rồi, tuy code hơi bựa nhưng không thể nào sai được, vậy mà submit cứ bị Wrong Answer :surrender:

                        Ai giúp em tìm ra test hiểm và bug trong code em với ạ, em cảm ơn nhiều!


                        Ý tưởng: Chạy từ đầu đến cuối dãy, ở mỗi lượt chạy, tính tổng các dãy con tạo bởi phần từ đang xét và các phần tử theo sau nó, khi gặp
                        dãy con có tổng >= k thì thoát ra, trước khi thoát có ghi nhận độ dài để tìm min độ dài nhằm làm kết quả cuối cùng. Ở cuối hàm main là
                        một loạt if để bắt các test hiểm.

                        // biến trong bài: n <-> N, k <-> S, s là biến tạm để tính tổng mỗi dãy con, l là chiều dài tạm của mỗi dãy con, m là kết quả cần xuất.

                        Code em:
                        Code:
                        #include <iostream>
                         
                        using namespace std;
                         
                        int main() {
                            int n, k;
                            cin >> n >> k;
                            int a[100000];
                            for (int i = 0; i < n; i++)
                                cin >> a[i];
                            a[n++] = 0;
                            int m = n, s, l;
                            for (int i = 0; i < n; i++) {
                                s = a[i], l = 1;
                                for (int j = i + 1; j < n; j++) {
                                    if (s >= k) {
                                        if (l < m)
                                            m = l;
                                        break;
                                    }
                                    s += a[j];
                                    l++;
                                }
                            }
                            if (m > n - 1 || n - 1 == 1 && a[0] < k) {
                                cout << 0 << '\n';
                                return 0;
                            }
                            if (n - 1 == 1 && a[0] >= k) {
                                cout << 1 << '\n';
                                return 0;
                            }
                            cout << m << '\n';
                            return 0;
                        }
                        Nó có bắt chọn dãy con hay không thì đáp án xuất ra vẫn y như cách làm của mình n . Thế thì tạo sao lại phải đi chọn dãy con trong khi mình chỉ cần xuất đáp án là độ dài của dãy

                        Comment


                        • #13
                          Originally posted by 14520848 View Post
                          Nó có bắt chọn dãy con hay không thì đáp án xuất ra vẫn y như cách làm của mình n . Thế thì tạo sao lại phải đi chọn dãy con trong khi mình chỉ cần xuất đáp án là độ dài của dãy
                          mình đã bảo là bạn xem kỹ lại đề đi rồi mà "a subsequence of a list is defined as a non-empty sequence of contiguous numbers from the list" :tire:
                          Last edited by 14520820; 11-10-2015, 09:39.

                          Comment


                          • #14
                            Originally posted by 14520820 View Post
                            mình đã bảo là bạn xem kỹ lại đề đi rồi mà "a subsequence of a list is defined as a non-empty sequence of contiguos numbers from the list" :tire:
                            :stick::stick::stick::stick::stick:
                            Mình không hiểu ý bạn lắm, chọn 10 6 5 với chọn 5 10 6 thì đều xuất đáp án là 3 mà. Mà già sử bạn có muốn tìm đãy con liên tiếp đi nữa, chỉ việc lấy dãy tối ưu nhất ( đã tìm ra sau khi sort) rồi so với dãy ban đàu để rút ra thứ tự chính xác của dãy tối ưu.
                            (Vd 10 6 5 là dãy tối ưu, dãy ban đầu là 5 3 10 2 6. Thì so từng phần tử sẽ ra thứ tự dãy tối ưu thành 5 10 6, nhưng đó là không cần thiết vì đề không yêu cầu ta xuất ra dãy con tối ưu)

                            Comment


                            • #15
                              Originally posted by 14520848 View Post
                              :stick::stick::stick::stick::stick:
                              Mình không hiểu ý bạn lắm, chọn 10 6 5 với chọn 5 10 6 thì đều xuất đáp án là 3 mà. Mà già sử bạn có muốn tìm đãy con liên tiếp đi nữa, chỉ việc lấy dãy tối ưu nhất ( đã tìm ra sau khi sort) rồi so với dãy ban đàu để rút ra thứ tự chính xác của dãy tối ưu.
                              (Vd 10 6 5 là dãy tối ưu, dãy ban đầu là 5 3 10 2 6. Thì so từng phần tử sẽ ra thứ tự dãy tối ưu thành 5 10 6, nhưng đó là không cần thiết vì đề không yêu cầu ta xuất ra dãy con tối ưu)
                              dãy này nhá 10 1 5 3 4 1 9; cho s = 12 nhá
                              cách bạn là sort phải k. vậy là : 10 9 5 4 3 1 1-> chiều dài 2 phải k
                              nhưng bạn chọn liên tiếp có dãy nào 2 số mà tổng nó >= 12 không ???:go:

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X