Thảo luận về các chủ đề trên UVA

Mấy hôm trước anh Tân có kêu gọi mọi người giải trí bằng cách lặp trình các bài lặp trình trên UVA, nhưng không thấy ai phản ứng hết. Vì vậy, em lặp ra topic này mong mọi người có thắc mắc gì zô đây chúng ta cùng chia sẽ...(Cùng giúp đỡ nhau đê)..

Sẳn đây em cũng xin mở màng bằng bài [You must be registered and logged in to see this link.]. bài này khá hay nhưng làm ra rồi lại submit sai...

Mọi người xem giùm và cho ý kiến nghe...

[You must be registered and logged in to see this link.]

Code:

#include <iostream.h>

int main(){
    char a[100][100];
    int b[100][100];
    int n, m;
    int k=1;
    while(1){
            cin>>n>>m;
            if(n==0 && m==0) break;
            cin.getline(a[0], 101);
            for(int i=0; i<n; i++){
                    cin.getline(a[i], m+1);
            }
                   
            for(int i=0; i<n; i++)
                    for(int j=0; j<m; j++)
                            b[i][j]=0;
                           
            for(int i=0; i<n; i++)
                    for(int j=0; j<m; j++){
                        if(a[i][j]=='*'){
                                      for(int k=-1; k<2; k++)
                                              for(int t=-1; t<2; t++)
                                                      if(a[i+k][j+t]!='*') b[i+k][j+t]++;
                                      b[i][j]=-1;
                        }
                    }
            cout<<"Field #"<<k<<":\n";
            for(int i=0; i<n-1; i++){
                    for(int j=0; j<m; j++){
                            if(b[i][j]==-1) printf("*");
                            else printf("%d", b[i][j]);       
                    }
                    printf("\n");
            }
            k++;
    }
}

Bài làm của em khá tốt nhwng vẫn còn sai một số chổ cơ bản.
Anh không post lời giải lên được vì sẽ vi phạm 1 vài nguyên tắc.
Những chổ mà em có thể sai:
- char a[100][100]; Chổ này đề bài nói là tối đa 100, nhưng khi đưa 1 bộ test 100x100 phần tử vào sẽ bị sai (do mỗi dòng còn có kí tự '\0' ở cuối nữa). Do đó, đối với những bài UVA nói chung em nên khai báo kích thướ lớn hơn đề cho ít nhất là 2. ma trận b[][] cũng vậy.
- if(n==0 && m==0) break; Trường hợp này em nên dùng lệnh return 0; thay vì break; . Chương trình của em nếu không có return trong một số trường hợp sẽ dễ bị hệ thống bắt là lỗi kể cả khi em ra kết quả đúng.
-

Code:

 for(int i=0; i<n; i++)
                    for(int j=0; j<m; j++){
                        if(a[i][j]=='*'){
                                      for(int k=-1; k<2; k++)
                                              for(int t=-1; t<2; t++)
                                                      if(a[i+k][j+t]!='*') b[i+k][j+t]++;

Chổ này rất dễ gây ra lỗi Run Time Error. Bởi vì nếu i=0 và k=-1 thì sẽ truy xuất tới phần tử a[-1][] ==> lỗi. j,k,t tương tự. Em nên bắt lỗi trong trường hợp nhỏ hơn 0 và >=n (hoặc m) trong cả chiều ngan và dọc.
Hint: Những trường hợp như thế này, em nên dùng biện pháp (.....Tên gì anh quên rồi....). Nhưng nguyên tắt là em sẽ để mảng của em trong một cái khung tương tự như:

Code:

**********
*oooooooo*
*oooooooo*
*oooooooo*
**********

Với các ô dấu * là các ô rìa, ô 'o' là ô nội dung của chúng ta. Lúc đó em sẽ for từ 1 đến <=n thay vì từ 0 đến <n.

- There must be an empty line between field outputs. (sau mỗi output sẽ có 1 dòng trống). em thêm vào if (k>1) cout<<endl; nên đọc đề kỹ hơn. đề UVA chuyên gia gài bẫy những chổ không ngờ như vậy đó.

-

Code:

for(int i=0; i<n-1; i++){
                    for(int j=0; j<m; j++){
                            if(b[i][j]==-1) printf("*");

Tại sao là i<n-1;? Phải là i<n; mới đúng chứ.

Anh đã thử và đã AC. Nên tập tính kỹ một chút!

hok ai tham gia trên UVA hết sao...buồn thế...admin ddtan ui, có bài nào hay không post lên chơi..^^

Nếu thích thì làm bài này đi.

Anh chưa có ý tưởng bài này: 10483 - The Sum Equals the Product

Code:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1424

Bài này nói chung là người ta cho mình 1 số k.
Tìm 3 số sao cho tổng của 3 số này và tích của 3 số này đều bằng k.
nghe đơn giản lắm mà chưa có hướng đi.

Trời ơi, bài đó mà dể...

hui thảo luận bài khác đi..bài [You must be registered and logged in to see this link.] này đi...
bài này dể thiệt, nhưng bị time limit... anh có giải thuật nào cho chạy nhanh không?

Tóm tắc: nhập vào n, đếm các số mà chia không hết n. (Ước chung lớn nhất của nó là 1);

Em lại đọc sai đề rồi. Không phải là các số mà không chia hết n hay n không chia hết gì đó mà là lấy số đó tạo thành phân số vớ n (n làm mẫu số) thì không thể rút gon nữa. em chỉ đúng chổ là gcd(i,n)=1 thôi hà.
Có nghĩa là tìm các số không có trùng bất kì thừa số nguyên tố nào với thừa số nguyên tố của n.

Theo anh được biết thì bài này phải dùng công thức Euler's Phi function.
Công thức này sẽ trả về số lượng số nguyên nhỏ hơn n và không có bị trùng với n bất kì thừa số nguyên tố nào.
Công thức chỉ tính được với n>1;
trường hợp n=1, sẽ in ra 1 vì 0/1 không thể rút gọn được nữa.

có thể tham khảo công thức này tại:

Code:

http://www.algorithmist.com/index.php/Euler's_Phi_function

Sư phụ ui lở rồi giúp đệ tử bài này nữa đi... sao làm thấy chạy cũng lẹ lắm chứ...kết quả ra 7 số mà chỉ trong khoảng 2s là ra rồi..zj mà nó bảo time limit.

Code:

#include <iostream.h>
unsigned long UCLN(unsigned long a,unsigned long b)
{
        return (b==0)?a:UCLN(b, a%b);
}
int main(){
    unsigned long t, a, b, c, boi;
    unsigned long i;
    cin>>t;
    for(unsigned int k=0; k<t; k++){
            cin>>a>>c;
            if(a==1 || a==c) cout<<c<<endl;
            else if(c%a) cout<<"NO SOLUTION\n";
            else{
                for(i=2; i<=c; i++){
                        if(c%i==0){
                                    boi=(a*i)/UCLN(a,i);
                                    if(boi==c) break;
                        }
                }
                cout<<i<<endl;
            }
    }
    return 0;
}

chỉ biết có cách này hà, anh có giải thuật nào cho nó chạy le hơn không zj?