Thảo luận bài tập ôn luyện Olympic- Thuật Toán

[10520180]

hồi còn học phổ thông thì mình có làm bài này nhưng sao giờ làm lại nó chạy không đúng, thôi ráng chờ nha bạn..

[10520180]

Mấy bác xem lại đoạn code sau của em nó sai chỗ nào mà em không biết được, em giải bài stone pile:http://acm.timus.ru/problem.aspx?space=1&num=1005:

#include <stdio.h>
#include <stdlib.h>


const char *INP="STONEPILE.INP";
const char *OUT="STONEPILE.OUT";

long a[105];
int d1[101*101],d2[101*101];
int n,m,sum=0;

void Enter();
void Process();
void Print();

void Enter()
{
     int i;
     FILE *fi=fopen(INP,"r");
     fscanf(fi,"%d",&n);
     for(i=1;i<=n;i++)
     {
                     fscanf(fi,"%d",&a[i]);
                     sum=sum+a[i];
     }
     m=sum/2;
     fclose(fi);
}
void Process()
{
     int i,j;
     for(i=1;i<=101*101;i++) d1[i]=0,d2[i]=0,tr[i]=0;
     d1[0]=1;
     d2[0]=1;
     for(i=1;i<=n;i++)
     {
                      for(j=0;j<=sum-a[i];i++)
                      if(d1[i]&&(d2[j+a[i]]==0) d2[j+a[i]]=1;
                      for(i=0;i<=101*101;i++) d1[i]=d2[i];
     }
}
void Print()
{
     int i;
     FILE *fo=fopen(OUT,"w");
     while (d2[m]==0) m--;
     fprintf(fo,"%d",sum-2*m);
     fclose(fo);
}    
void main()
{
     Enter();
     Process();
     Print();
}

[10520516]

cũng là mảng thui... tốn bộ nhớ thôi rồi...
p/s hix mỗi lần gõ là chú ý tới "Mãng" hix

[10520180]

bạn có thể đưa code lên không??

[10520516]

cách làm hok có hay... bựa lắm... muốn học hỏi thêm ở các huynh

[08520522]

for(i=1;i<=n;i++)
{
for(j=0;j<=sum-a[i];i++)
if(d1[i]&&(d2[j+a[i]]==0) d2[j+a[i]]=1;
for(i=0;i<=101*101;i++) d1[i]=d2[i];
}

Một số cái hơi sai:
- Cái vòng lặp for của j thì phải tăng j chứ sao lại tăng i
- Vòng lặp bên trong sử dụng biến i của vòng lặp bên ngoài

À, mà tiện thể giải thích thêm cái code là nó làm những gì trong đó vậy, chứ vẫn chưa hiểu ý tưởng của tác giả...

[08520059]

Bài Stone Pile trong timus N <= 20, có lẽ sử dụng vét cạn được.

[10520516]

bài stone pile em có thể giải với độ phức tạp N*M và phải lưu với mãng gồm N*M phần tử...với N là số viên đá và M là khối lượng lớn nhất, nên khi đưa N hoặc M lên cao thì em nghĩ bài của em bó tay....đối với N=20 trên timus hoàn toàn pass được...

[08520059]

Cụ thể M là bao nhiêu, lưu "mãng" N*M để làm gì.

[10520516]

ví dụ em có các loại đá với khối lượng như sau... 1 2 4
em sẽ đánh dấu A[i] nếu i được hình thành bằng cách tính tổng các phần tử thuộc 3 số trên. như vậy các tổng được sinh ra:
1, 1+2, 2, 1+4,1+2+4,4
1, 3 , 2, 5 , 7 ,4
như vậy các phần tử A[1],A[3],A[2],A[5],A[7],A[4] được đánh dấu.

[10520180]

các bác xem thế nào, em giải ra test 1 nhưng sao nó bảo lại sai ngay từ test 1, các bác xem góp ý cho em nha(em làm trên pascal, mấy bác thông cảm):

program Stone;
var a:array[1..100] of word;
    d1,d2: array[0..100*100] of byte;
    n:byte;
    m,sum:longint;
procedure Enter;
var i,j:integer;
begin
        write('Nhap so N= ');
        readln(n);
        sum:=0;
        for i:=1 to n do
        begin
                write('nhap vao can nang vien da thu ',i,':');
                readln(a[i]);
                sum:=sum+a[i];
        end;
end;
procedure Process;
var i,j:integer;
begin
        fillchar(d1,sizeof(d1),0);
        d1[0]:=1;
        d2:=d1;
        for i:=1 to n do
        begin
                for j:=0 to sum-a[i] do
                if (d1[j]=1) and (d2[j+a[i]]=0) then d2[j+a[i]]:=1;
                d1:=d2;
        end;
end;
procedure Printf;
begin
        m:=sum div 2;
        while d2[m]=0 do dec(m);
        writeln(sum-2*m);
end;
BEGIN
        Enter;
        Process;
        Printf;
        readln;
END. 

[08520001]

Đây là code giải bài 1005 Stone pile mà không cần dùng vét cạn hay dùng mảng đánh dấu. Mời các bạn xem thử quan ao nam. AC trong 0.093 và bộ nhớ 192KB.

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int a[21], N;

int ABS(int N)
{
    if(N < 0) return -N;
    else return N;
}

int main()
{
//    freopen("input.txt","r",stdin);
    cin >> N;
    int ret = 1000000000;
    int total = 0;
    for(int i = 0; i < N; i++)
    {
        cin >> a[i];
        total += a[i];
    }
    for(int i = 0; i < (1 << N); i++)
    {
        int sum = 0;
        for(int j = 0; j < N; j++)
            if(((i >> j) & 1) == 1) sum += a[j];
        ret = min(ret, ABS(total - 2 * sum));
    }
    cout << ret;
    return 0;
} 

[09520019]

a An gian ghê.......không dùng mảng đánh dấu nhưng dùng dãy nhị phân để đánh dấu =.=

[08520001]

Cách này học được bên TopCoder. quan ao.

[08520059]

Cái này là vét cạn chứ cái gì nữa mạy