Võ đường quán: Tuyển tập đề thi các kì thi Olympic tin học

[AlexBlack]

buổi tối mình không ol được.
ý tưởng mình là ma trận hóa từng ô
nơi nào có rada thì gán là 1
nơi nào nằm trong vùng rada quan sát được thì gán =2
nơi nào rada không quan sát được thì là 0;
kiểm tra chỗ nào không bằng 0 lấy tổng.
đây là demo code của mình.

#include<stdio.h>#define input "water.txt"typedef struct Rada{    int n,m;    int **Array;    int nrada;}; void Init(Rada &r){    for(int i=0;i<r.m;i++)        for(int j=0;j<r.n;j++)            r.Array[i][j]=0;}int Nhap(Rada &r){    FILE *f=fopen(input,"rt");    if(f==NULL)        return 0;    fscanf(f,"%d",&r.m);    fscanf(f,"%d",&r.n);    r.Array=new int*[r.m];    for(int i=0;i<r.n;i++)    {        r.Array[i]=new int[r.n];    }    Init(r);    fscanf(f,"%d",&r.nrada);    int p,q;    while(!feof(f))    {        fscanf(f,"%d",&p);        fscanf(f,"%d",&q);        r.Array[p][q]=1;    }    fclose(f);    return 1;} void ChanHoa(Rada &r){    for(int i=0;i<r.m;i++)        for(int j=0;j<r.n;j++)        {            if(r.Array[i][j]==1)            {                if(i-1>-1)                {                    if(j-1>-1)                        r.Array[i-1][j-1]=2;                    r.Array[i-1][j]=2;                    if(j+1<r.m)                        r.Array[i-1][j+1]=2;                }                if(j-1>-1)                    r.Array[i][j-1]=2;                if(j+1<r.m)                    r.Array[i][j+1]=2;                if(i+1<r.n)                {                    if(j-1>-1)                        r.Array[i+1][j-1]=2;                    r.Array[i+1][j]=2;                    if(j+1<r.m)                        r.Array[i+1][j+1]=2;                }            }        }} void XuatAnToan(Rada r){    ChanHoa(r);    int sum=0;    for(int i=0;i<r.m;i++)        for(int j=0;j<r.n;j++)        if(r.Array[i][j]!=0)            sum+=1;    printf("Tong so o an toan: %d",sum);} //hủy vùng nhớ cấp phátvoid Detroy(Rada &r){    for(int i=0;i<r.m;i++)        delete []r.Array[i];    delete []r.Array;}int main(){    Rada r;    if(!Nhap(r))    {        printf("Khong mo duoc file.");        return 0;    }    XuatAnToan(r);    Detroy(r);    return 0;}

[hienclubvn]

@dkcnn...., @Tadius, @Pannaruto...
Nói rõ giải thuật nha..
1. Bài này áp dụng giải thuật nào
2. Giải thuật này đc dùng như thế nào?
3. Áp dụng cho những loại bài nào
4. Giải thích cụ thể vào bài toán trên

P/S: Thay mặt các Mem tham gia Topic thanks các bác

[dkbcnncb11]

mình bỏ qua bước nhập và kiểm tra nha.
b1:vì màng chưa có giá trị , mình cho tất cả các phần tử =1.
b2:cho nhập i,j (cho giống với đề bài mình cho i-1 , j-1) là tọa độ của rada .mình tính tổng các phần tử(nếu =1) của rada trong phạm vi 3*3.( khỏi lo biên vì biên không có giá trị) . Sau đó cho tất cả phần tử =0(nếu rada khác có trong phạm vi này thì cũng không cộng vô được);

@hienclubvn: sao bạn không up code của bạn lên cho mọi người cùng share và trao đổi.

#include <conio.h>#include <string.h>#include <iostream>using namespace std;int rada(int a[][50],int i,int j){    int s=0;    for(int l=i-1;l<=i+1;l++)        for(int k=j-1;k<=j+1;k++)            if(a[l][k]==1)            {                s++;                a[l][k]=0;            }    return s;}void main(){    int a[50][50],i,j,n,m,k=0,s=0;    do{        cout<<"RADAR.INP\n";        cin>>m>>n;    }while(m<1||n<1||n>50||m>50);    for(int l=0;l<m;l++)        for(int h=0;h<n;h++)            a[l][h]=1;    while(k<1||k>m*n)        cin>>k;    while(k--!=0)    {        do{            cin>>i>>j;        }while(i<1||i>m||j<1||j>n);        s=s+rada(a,i-1,j-1);    }    cout<<"RADAR.OUT\n"<<s;    getch();}

[hienclubvn]

Chém 2 của HienClub nèk
Ý tưởng: Cái nào an toàn cho bằng 1, OK
CODE Full

#include<stdio.h>#include<conio.h>#include<stdlib.h>#define INPUT "RADAR.INP"#define OUTPUT "RADAR.OUT"int **B,n,m;int dx[3]={-1,0,1};int dy[3]={-1,0,1};void Rada(int x,int y){     int i,j,u,v;    for(i=0;i<3;i++)    {        u=x+dx[i];                    for(j=0;j<3;j++)        {           v=y+dy[j];                        if((u>=1&&u<=n)&&(v>=1&&v<=m))           {              B[u-1][v-1]=1;           }        }    }}void Print(){     int i,j;     for(i=0;i<m;i++)     {         for(j=0;j<m;j++)         printf("%d  ",B[i][j]);         printf("\n");                  }}int SumSafe() // Tổng các ô an toàn{    int i,j,temp=0;    for(i=0;i<m;i++)      for(j=0;j<n;j++)      if(B[i][j]==1)temp++;    return temp;}int main(){    //Read File    FILE *fin;    fin=fopen(INPUT,"r");    // Cap phat bo nho    fscanf(fin,"%d %d\n",&m,&n);    B=(int**)malloc(m*sizeof(int));    for(int i=0;i<m;i++)    {        B[i]=(int*)malloc(n*sizeof(int));        for(int j=0;j<n;j++) B[i][j]=0;    }    int temp,x,y;    fscanf(fin,"%d\n",&temp);    for(int i=0;i<temp;i++)    {        fscanf(fin,"%d %d\n",&x,&y);           Rada(x,y);     }    fclose(fin);    //Xuat ra man hinh    Print();    printf("Tong Cell Safe = %d",SumSafe());    //Ghi vao File    FILE *fout;    fout=fopen(OUTPUT,"w");    fprintf(fout,"%d",SumSafe());    fclose(fout);    getch();}

[dkbcnncb11]

@AlexBlack: code của bạn không ổn .
ví dụ:
lúc đầu mảng co dạng
0 0 0 0
0 1 1 0
0 0 0 0
sau khi chuẩn hóa có dạng:
2 2 2 0
2 2 2 0
2 2 2 0
vì bạn đã đổi số 1 ở ô (3,3) thành số 2 rồi. nên nó không xét được số 1 ô (3,3) .

[AlexBlack]

@AlexBlack: code của bạn không ổn .
ví dụ:
lúc đầu mảng co dạng
0 0 0 0
0 1 1 0
0 0 0 0
sau khi chuẩn hóa có dạng:
2 2 2 0
2 2 2 0
2 2 2 0
vì bạn đã đổi số 1 ở ô (3,3) thành số 2 rồi. nên nó không xét được số 1 ô (3,3) .

í quên chỗ này rồi. đợi tí mình sẽ sửa ngay.
cảm ơn bạn dkbcnncb11 rất nhiều. mình đề nghị để code lỗi trên kia luôn để mọi người biết chỗ sai
mình làm lại như sau
xét những chỗ không phải là rada kiểm tra xem chỗ đó có phải là vùng an toàn hay không
ở đây mình sử dụng mảng từ 1-m,1-n để bỏ qua việc kiểm tra điều kiện biên.

#include<stdio.h>
#define input "water.txt"
typedef struct Rada
{
    int n,m;
    int **Array;
    int nrada;
};

void Init(Rada &r)
{
    for(int i=0;i<=r.m;i++)
        for(int j=0;j<=r.n;j++)
            r.Array[i][j]=0;
}
int Nhap(Rada &r)
{
    FILE *f=fopen(input,"rt");
    if(f==NULL)
        return 0;
    fscanf(f,"%d",&r.m);
    fscanf(f,"%d",&r.n);
    r.m++;
    r.n++;
    r.Array=new int*[r.m+1];
    for(int i=0;i<=r.n;i++)
    {
        r.Array[i]=new int[r.n+1];
    }
    Init(r);
    fscanf(f,"%d",&r.nrada);
    int p,q;
    while(!feof(f))
    {
        fscanf(f,"%d",&p);
        fscanf(f,"%d",&q);
        r.Array[p+1][q+1]=1;
    }
    fclose(f);
    return 1;
}

void ChanHoa(Rada &r)
{
    for(int i=1;i<r.m;i++)
        for(int j=1;j<r.n;j++)
        {
            if(r.Array[i][j]==0)
            {
                if(r.Array[i-1][j-1]==1||r.Array[i-1][j]==1||r.Array[i-1][j+1]==1)r.Array[i][j]=2;
                if(r.Array[i][j-1]==1||r.Array[i][j+1]==1)r.Array[i][j]=2;
                if(r.Array[i+1][j-1]==1||r.Array[i+1][j]==1||r.Array[i+1][j+1]==1)r.Array[i][j]=2;

            }
        }
}

void Xuat(Rada r)
{
    for(int i=1;i<r.m;i++)
    {
        for(int j=1;j<r.n;j++)
            printf("%d ",r.Array[i][j]);
        printf("\n");
    }
}

void XuatAnToan(Rada r)
{
    ChanHoa(r);
    int sum=0;
    for(int i=1;i<r.m;i++)
        for(int j=1;j<r.n;j++)
        if(r.Array[i][j]!=0)
            sum+=1;
    printf("Tong so o an toan: %d",sum);
}

//hủy vùng nhớ cấp phát
void Detroy(Rada &r)
{
    for(int i=0;i<r.m+1;i++)
        delete []r.Array[i];
    delete []r.Array;
}


int main()
{
    Rada r;
    if(!Nhap(r))
    {
        printf("Khong mo duoc file.");
        return 0;
    }
    XuatAnToan(r);
    Detroy(r);
    return 0;
} 

[hienclubvn]

mình đề nghị để code lỗi trên kia luôn để mọi người biết chỗ sai

Rất đồng tình với quan điểm của bạn AlexBlack
Mặc dù mình ko biết về Struct (Ko chủ ý học cái này, chủ yếu học cơ bản + giải thuật) nhưng rất hoan nghênh

Tạm lắng Bài chém 2 đi, để tiếp tục cho Topic sôi nỗi (Hướng đến Hot Topic), chúng ta gác mọi sự kiện (Nếu ai thắc mắc về 2 chém trước thì cứ Comment nha - cái này ko cấm )

BÀI CHÉM SỐ 3: Tìm đặc trưng ảnh (Ko chuyên 2005)

Một nhóm nghiên cứu xử lý ảnh của trường ĐH Khoa học tự nhiên, ĐHQG Tp.HCM đang
giải quyết bài toán nhận dạng mặt người trong ảnh. Ảnh chụp mặt người sau khi đã xử lý là
một bảng vuông A kích thước N x N (10 ≤ N ≤ 800) với mỗi ô (I,J) (1 ≤ I, J ≤ N) có giá trị từ
0 đến 255 là mức xám của ảnh tại ô này (trong đó 0 là màu nền). Để xác định vị trí có thể là
mặt người, nhóm cần thống kê các đặc trưng có dạng hình vuông kích thước K x K (1 ≤ K ≤
40) trong đó tất các các giá trị trong hình vuông đều phải khác 0.
Yêu cầu : Từ một ảnh chụp mặt người, hãy giúp nhóm nghiên cứu đếm tất cả các đặc trưng
có trong ảnh đó.
Dữ liệu : Vào từ file văn bản FEATURE.INP trong đó :
• Dòng đầu chứa hai sô N và K
• Dòng thứ I trong N dòng tiếp theo chứa tương ứng dòng thứ I của bảng A.
Các số ghi trên một dòng được ghi cách nhau bởi ít nhất một khoảng trắng. Mỗi dòng có N số
nguyên. Dòng thứ I là các giá trị của N phần tử trong dòng thứ I-1 trong bảng vuông A
Kết quả : Ghi ra file văn bản FEATURE.OUT số lượng đặc trưng tìm được.



FEATURE.INP
6 2
0 12 15 0 33 30
17 19 23 15 16 0
11 12 0 14 14 0
0 10 11 8 10 0
0 8 7 12 0 0
0 0 11 13 0 0

FEATURE.OUT
7

[aydada]

int main(){    int **a, n, i, j, tongco = 0, tongchua = 0,  dem = 0, nuoccan;     cout << "Nhap so thung: ";    cin >> n;     a = new int *[n];    for(i = 0; i < n; i++)    {        a[i] = new int;        for(j = 0; j < 2; j++)        {            cin >> a[i][j];        }        tongco += a[i][0];        tongchua += a[i][1];    }        for(i = 0; i < n - 1; i++)        for(j = i + 1; j < n; j++)        {            if(a[i][1] < a[j][1])            {                int tam = a[i][1];                a[i][1] = a[j][1];                a[j][1] = tam;            }        }        nuoccan = tongchua - tongco;     int tong = 0;    for(i = 0; i < n; i++)    {            if(nuoccan > tong)            {                tong += a[i][1];                 dem++;            }            else             {                cout << dem << endl;                break;            }    }        for(int j = 0; j < 2; j++)        delete a[j];    delete a[i];     system("pause");    return 0;}

đây là bài chém 1 mình làm.
Tư tưởng của mình là lấy tổng dung tích có thể chứa trong tất cả các bình trừ đi lượng nước các bình đã có sẽ ra số lượng nước cần lấy. Sau đó chỉ cần đem số thùng có tổng dung tích lớn hơn số nước còn thiếu đi là được.

[hienclubvn]

Ok, các bác cứ chém thoải mái, ko hạn chế.
Chém 1, chém 2, ai muốn chém tiếp, vẫn cứ Post nha, ko gần ngại (Miễn sao xoay quanh vấn đề học tập là OK hết)
P/S: em đi nhậu đây, các bác cứ làm việc.... Hì

[AlexBlack]

bài 3
mình duyệt toàn bộ ma trận, kiểm tra những vùng có diện tích KxK xem có phải là mặt người hay không. nếu phải thì tăn biến đếm lên.
demo code.

#include<stdio.h>#define input "FEATURE.INP"typedef struct Anh{    int n;    int k;    int **Array;}; void Init(Anh &a){    for(int i=0;i<a.n;i++)        for(int j=0;j<a.n;j++)            a.Array[i][j]=0;}int Nhap(Anh &a){    FILE *f=fopen(input,"rt");    if(f==NULL)        return 0;    fscanf(f,"%d",&a.n);    fscanf(f,"%d",&a.k);    a.n;    a.Array=new int*[a.n];    for(int i=0;i<a.n;i++)    {        a.Array[i]=new int[a.n];    }    //Init(a);    for(int i=0;i<a.n;i++)        for(int j=0;j<a.n;j++)        {            fscanf(f,"%d",&a.Array[i][j]);        }    fclose(f);    return 1;}int KtMatNguoi(Anh a,int p,int q){    for(int i=p;i<p+a.k;i++)        for(int j=q;j<q+a.k;j++)        {            if(a.Array[i][j]==0)                return 0;        }        return 1;}  int SoMatNguoi(Anh a){    int sum=0;    for(int i=0;i<a.n-a.k+1;i++)        for(int j=0;j<a.n-a.k+1;j++)        {            if(KtMatNguoi(a,i,j))                sum++;        }    return sum;} //hủy vùng nhớ cấp phátvoid Detroy(Anh &r){    for(int i=0;i<r.n;i++)        delete []r.Array[i];    delete []r.Array;} int main(){    Anh a;    if(!Nhap(a))    {        printf("Khong mo duoc file.");        return 0;    }    printf("So mat nguoi trong anh: %d",SoMatNguoi(a));    Detroy(a);    return 0;}