Gia sư Cần Thơ, Dạy Kèm Cần Thơ

VỮNG TIN - TIẾP BƯỚC - THÀNH CÔNG


Thử giải đề cho vui. "Có thưởng đấy"

Share

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Wed Dec 23, 2009 1:24 pm

Bài 1.
- Có một số cây có chiều dài cho trước. Cần bắt qua những con kênh có chiều rộng cho trước (không quá 100 cây và 100 con kênh).
- Điều kiện: + Nếu cây dài quá thì bạn có thể chặt nó ra thành vài khúc xài cũng được
+ Chỉ được dùng 1 khúc cây để bắt qua 1 con kênh
+ Khúc cây được dùng để bắt qua con kênh phải có chiều dài lớn hơn chiều rộng của con kênh ít nhất là 1m.
- Bài toán đặt ra là bắt như thế nào để số cây còn lại phải là nhiều nhất (chú ý chỉ tính những cây mà bạn chưa chặt ra).
- Test thì bạn cứ tuỳ ý cho thế nào cũng được.

Giải thưởng: Nếu các bạn hoàn thành bài này trước tết tây thì tôi sẽ nhờ thầy AlPha chuyển cho các bạn một phần quà có giá trị. OK

Bài 2
Bài này khó hơn 1 chút thời gian hoàn thành là trước tết nguyên đáng
-Cho ma trận cấp AmXn. Là ma trận số. m,n và a[i,j] đều nhỏ hơn 100. Hãy sắp xếp các phần tử trên mỗi dòng lại sao cho ma trận thu được các phần tử trên mỗi cột đôi một khác nhau.

Chú ý các test đều không chạy quá 5s
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  admin on Wed Dec 23, 2009 2:41 pm

Cám ơn thầy qvluom, 2 bài toán khá thú vị. Thầy cho các bạn sinh viên vài cái test mẫu nhé! Nghe có quà là bài toán trở nên cực kỳ hấp dẫn.
Các bạn ơi cố lên!

---------------
Không có gì là khó cả

nor_ghost2003
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 5
Join date : 23/12/2009

GIAI CO THUONG!!!

Bài gửi  nor_ghost2003 on Wed Dec 23, 2009 7:33 pm

nói cho ngắn gọn thế này: số đo của cây cho trước , số đo của kênh cho trước thì suy ra số cây không phải chặt nhiều nhât là 100 cây, nếu số đó của tất cả cây choi trước phải bằng số đo của kênh + 2m dư.........suy ra là số cây còn nguyên vẹn nhiều nhất là 100 cây hay theo công thức sau:
số đo cây trước khi chặt = số đo Kênh + 2m dư

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Wed Dec 23, 2009 10:55 pm

nor_ghost2003 đã viết:nói cho ngắn gọn thế này: số đo của cây cho trước , số đo của kênh cho trước thì suy ra số cây không phải chặt nhiều nhât là 100 cây, nếu số đó của tất cả cây choi trước phải bằng số đo của kênh + 2m dư.........suy ra là số cây còn nguyên vẹn nhiều nhất là 100 cây hay theo công thức sau:
số đo cây trước khi chặt = số đo Kênh + 2m dư

Đúng là càng ngày mình càng kém nhạy bén rồi. Đọc hoài vẫn không hiểu bạn muốn nói gì. Có thể lập luận của bạn là đúng, nhưng tại mình không biết thôi. Sorry nhé.

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Wed Dec 23, 2009 11:29 pm

Cơ cấu giải thưởng.
Giải đúng một câu tặng 1 tên miền quốc tế (duy trì 1năm).
Giải đúng hai câu tặng thêm 1 host Việt Nam (6 tháng).
Giải đúng câu thứ 3 (vài ngày nữa sẽ ra tiếp) tặng thêm 1 source code diễn đàn viết bằng ASP, ASP.NET hoặc PHP có bản quyền (đã trả tiền rồi) bảo hành 3 năm. Nâng cấp miễn phí Very Happy Very Happy Very Happy flower

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Thu Dec 24, 2009 3:59 pm

qvluom đã viết:
Bài 2
Bài này khó hơn 1 chút thời gian hoàn thành là trước tết nguyên đáng
-Cho ma trận cấp AmXn. Là ma trận số. m,n và a[i,j] đều nhỏ hơn 100. Hãy sắp xếp các phần tử trên mỗi dòng lại sao cho ma trận thu được các phần tử trên mỗi cột đôi một khác nhau.

A[i,j] có mang giá trị âm không vậy thầy? Question

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Thu Dec 24, 2009 7:54 pm

Chỉ là các số nguyên dương thôi. Very Happy Very Happy
Cố lên nhé

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Thu Dec 24, 2009 10:40 pm

Thầy ơi! thầy không cho test làm sao tụi em biết code của mình có đạt yêu cầu không?
Em giải bài 2 rồi! nhưng dùng vét cạn, chưa biết có đáp ứng được yêu cầu "các test đều chạy không quá 5s" của thầy không?

Code:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define fi "D:\\bai2.inp"
#define fo "D:\\bai2.out"

int error=0,
    m,n,A[100][100],
    DD[100][100];

void input(){
   FILE *f;
   int s;
   f = fopen(fi,"r");

   if (f!=NULL){
      if (fscanf(f,"%d",&s))
         m=s;
      else {error=1; exit;}
      if (fscanf(f,"%d\n",&s))
         n=s;
      else {error=1; exit;}

      for (int i=0; i<m; i++){
         for (int j=0; j<n; j++)
            if (fscanf(f,"%d",&s))
               A[i][j]=s;
            else {error=1; exit;}
         fscanf(f,"\n");
      }
   }
   else error=1;
   fclose(f);
}

void output(){
   FILE *f;
   f = fopen(fo,"w");
   for (int i=0; i<m; i++){
      for (int j=0; j<n; j++)
         fprintf(f,"%3d",A[i][j]);
      fprintf(f,"\n");
   }
   fclose(f);
}

void khoi_tao(){
   for (int i=0; i<100; i++)
   for (int j=0; j<100; j++)
      DD[i][j]=0;
   for (i=0; i<n; i++)
      DD[i][A[0][i]]=1;
}

void swap(int dong, int cot1, int cot2){
   int temp=A[dong][cot1];
   A[dong][cot1]=A[dong][cot2];
   A[dong][cot2]=temp;
}

void chon(int d, int c){
   if (d==m){
      output();
      exit(1);
   }
   else{
      for (int i=c; i<n; i++)
         if (DD[c][A[d][i]]==0){
            DD[c][A[d][i]]=1;
            swap(d,c,i);
            if (c==n-1)
               chon(d+1,0);
            else   chon(d,c+1);
            swap(d,c,i);
            DD[c][A[d][i]]=0;
         }
   }
}

void Xuli(){
   khoi_tao();
   chon(1,0);
   FILE *f;
   f = fopen(fo,"w");
   fprintf(f,"Du lieu nay thi phai bo tay thoi! hi hi! \nGhe tham site em nha thay: \"Http://DuongTanThanh.Net\"");
   fclose(f);
}

void main(){
   clrscr();
   input();
   if (!error)
      Xuli();
   else{
      printf("\n\nLoi khong tim thay file input hoac noi dung file input sai cu phap");
      getch();
   }
}

Dữ liệu vào cho trong file D:\Bai2.inp với dạng:
- Dòng đầu là 2 số m, n (0- m dòng tiếp theo, mỗi dòng là n số nguyên không âm và <100.

nếu có bộ test mà làm cho nó chạy quá 5s thì thầy có thể vui lòng cho em xin bộ test được không ạh? Laughing

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Thu Dec 24, 2009 11:27 pm

àh em quên nữa!
ở em học, đi thi mà trên 5đ là coi như đậu.

Bài này nếu em chạy đúng 50% số test thì coi như đúng nha thầy! Laughing

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Fri Dec 25, 2009 12:07 am

ztanzzthanhz đã viết:àh em quên nữa!
ở em học, đi thi mà trên 5đ là coi như đậu.

Bài này nếu em chạy đúng 50% số test thì coi như đúng nha thầy! Laughing

Cũng là một ý kiến hay. Ok chấp nhận ý kiến này. Nhưng tạm thời mình sẽ không cho bạn biết là bài của bạn đúng hay sai đâu nhé. Đến tết tây mình sẽ chỉ ra cho bạn một vài cái mà bạn đã nhằm lẫn trong thuật toán này (nếu có).
Bây giờ mà nói bạn giải đúng thì người khác sẽ không tham gia giải nữa đâu. Laughing thế thì buồn lắm.
Chúc bạn noel vui vẻ Very Happy

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Fri Dec 25, 2009 12:30 am

Very Happy Thồi dù sao thì cũng khích lệ bạn đôi chút
Bạn biết hút thuốc không. Mình tặng bạn 2 gói thuốc, vừa hút vừa đợi kết quả
Hãy thử với bộ test kích thước 15 nha. Nếu đúng bạn sẽ được 1 điểm rưỡi. OK
15 15
1 2 3 4 5 6 7 8 9 10 12 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad Evil or Very Mad

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Fri Dec 25, 2009 12:40 am

Sau khi hoàn chỉnh lại bạn cứ sử dụng bộ test này và tăng dần lên xem được bao nhiêu. Chúc bạn thành công.
Còn trang web của bạn http://duongtanthanh.net/trangchu/index.php?lang=vi mình đã vào rồi. Rất tuyệt, phải nói là rất tuyệt. Nhưng hình như bạn đang sử dụng host nước ngoài thì phải, nếu đợt này bạn giải được câu 2 mình sẽ tặng bạn 1 host Việt Nam. Very Happy
avatar
bedongdong
Nhập môn
Nhập môn

Tổng số bài gửi : 4
Points : 8
Join date : 25/12/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  bedongdong on Fri Dec 25, 2009 12:59 am



Được sửa bởi bedongdong ngày Fri Dec 25, 2009 9:59 pm; sửa lần 2.

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Fri Dec 25, 2009 6:01 am

qvluom đã viết:Very Happy Thồi dù sao thì cũng khích lệ bạn đôi chút
Bạn biết hút thuốc không. Mình tặng bạn 2 gói thuốc, vừa hút vừa đợi kết quả

Em không biết hút thuốc! thôi thầy tặng em 2 hộp nhang muỗi để em mò em sửa nó lại đi thầy! Very Happy
Tại vì code đó em biết là chạy không nổi chắc ùi! tại vì trường hợp lớn nhất tính ra nó có đến 99!^99! trường hợp lận Razz

Giờ đến Tết âm lịch còn lâu mà há thầy! để em kiếm cách khác! Laughing Host của thầy khó lấy quá! Rolling Eyes
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  admin on Fri Dec 25, 2009 7:55 am

Nghe trao đổi hấp dẫn quá!
E suy nghỉ đưa nó về đồ thì giải xem sao!!!

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Fri Dec 25, 2009 9:03 pm

Câu 3 nè, mời các bạn giải, nói trước là bài này thuộc loại khó.

Câu 3: Cho trước sơ đồ mạng lưới giao thông. Trên sơ đồ có thể hiện vị trí của các bến xe, số lượng xe khách trên bến và số ghế ngồi của từng xe. Trên sơ đồ cũng thể hiện rõ vị trí của một số địa phương có khả năng bị sóng thần đe doạ đến tính mạng người dân và cũng thể hiện rõ số hộ gia đình sinh sống cùng với số nhân khẩu trong từng hộ. Trên sơ đồ cũng thể hiện rõ vị trí của những điểm tạm gọi là trại tập trung lánh nạn và cũng thể hiện rõ sức chứa (bao nhiêu người) của những trại tập trung đó.
Yêu cầu: Lập phương án vận chuyển người dân đến các trại tập trung (bạn được quyền tuỳ ý điều động bất kỳ xe nào) trong khoảng thời gian nhanh nhất có thể được. Chú ý các thành viên trong một hộ gia đình phải được ở cùng tại một trại tập trung, các xe không được chở quá số người cho phép, được tuỳ ý điều động bao nhiêu lần cũng được, các trại tập trung không được chứa quá số người cho phép.

Cố lên các bạn, phần thưởng hấp dẫn đang chờ các bạn. Very Happy Very Happy

nor_ghost2003
Nhập môn
Nhập môn

Tổng số bài gửi : 2
Points : 5
Join date : 23/12/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  nor_ghost2003 on Sat Dec 26, 2009 11:09 pm

Đây là 1 bài toán ko khó. nếu các bạn thực hiện tốt bước phân tích bài toán sẽ thấy nó vô cùng đơn giản..... như việc cho con voi vào trong tủ lạnh vậy

Phân tích bài toán :
vấn đề 1 :
1 x x x x
1 1 1 1 1
x x x x x
x x x x x

=> vậy phải ức chế việc nhập rồi....


Vấn đề chính
tiếp theo bạn thấy đó. để các phẩn từ trên các cột lần dôi 1 khác nhau (khi điều 1 trên được bảo đám) chính là việc ta xắp xếp các phần tử tăng dần theo chiều hướng sau bảo đảm rằng nó ko bao giờ có sự trùng nhau trên các cột cả :
1 1 1 2 2
2 2 3 3 4
5 6 7 8 9
9 9 9 9 10
hoặc theo chiều ngược lại
9 9 9 9 8
8 8 8 8 7
7 7 6 6 5
4 3 2 1 1

từ 2 ma trận gốc này tôi có thể biến đổi ra rất nhiều ma trận con bảo đám tính đúng đắn của bài toán qua các phép biến đổi :
+ đổi 2 hàng cho nhau
+ đổi 2 cột cho nhau
+ đổi 2 phần tử cùng 1 cột cho nhau.
//ko thể tùy tiện đổi 2 phần tử khác cột

tại sao lại nghĩ đến phương pháp này : đơn giản thôi, các phần từ giống nhau ko có trong các cột , vậy tôi nghĩ đến việc đặt nó nằm ngay cạnh nhau trên các hàng.
sau đó tôi lại nhận thấy thay đổi 2 hàng cho nhau vẫn bảo đảm tính đúng đắn
rồi mở rộng ra đổi 2 phần tử cùng cột cho nhau cũng ok.
......

Về code . phân tích đến đây thì việc code chắc là quá đơn giản.

nếu bạn nắm vững về con trỏ đa cấp và mảng 2 chiều. bạn sẽ thấy vấn đề còn đơn giản hơn nữa. Chỉ là việc xắp xếp 1 cái dãy số. ( trong con mắt tôi thì mảng 2 chiều cũng chỉ là 1 mảng bộ nhớ + bộ nhớ chỉ có 1 chiều => matran cũng chỉ là mảng 1 chiều. he he. )

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Sun Dec 27, 2009 12:10 am

nor_ghost2003 đã viết:Đây là 1 bài toán ko khó. nếu các bạn thực hiện tốt bước phân tích bài toán sẽ thấy nó vô cùng đơn giản..... như việc cho con voi vào trong tủ lạnh vậy... he he.

Thật quá bất ngờ về bài phân tích của bạn. Tôi không biết nói gì hơn nữa. Tôi không dám nói rằng bạn đã phân tích sai (vì tôi sợ bạn sẽ phản kháng mạnh). Tôi chỉ xin nói một câu thôi: Tôi đã từng giải bài này một cách rất nghiêm túc trong hơn 2 năm mới được đấy Very Happy Very Happy . Thân chào bạn, rất mong nhận được code do đích tay bạn viết.

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Sun Dec 27, 2009 1:13 am

nor_ghost2003 đã viết:
Phân tích bài toán :
vấn đề 1 :
1 x x x x
1 1 1 1 1
x x x x x
x x x x x

=> vậy phải ức chế việc nhập rồi....


Vấn đề chính
tiếp theo bạn thấy đó. để các phẩn từ trên các cột lần dôi 1 khác nhau (khi điều 1 trên được bảo đám) chính là việc ta xắp xếp các phần tử tăng dần theo chiều hướng sau bảo đảm rằng nó ko bao giờ có sự trùng nhau trên các cột cả :
1 1 1 2 2
2 2 3 3 4
5 6 7 8 9
9 9 9 9 10
hoặc theo chiều ngược lại
9 9 9 9 8
8 8 8 8 7
7 7 6 6 5
4 3 2 1 1

từ 2 ma trận gốc này tôi có thể biến đổi ra rất nhiều ma trận con bảo đám tính đúng đắn của bài toán qua các phép biến đổi :
+ đổi 2 hàng cho nhau
+ đổi 2 cột cho nhau
+ đổi 2 phần tử cùng 1 cột cho nhau.
//ko thể tùy tiện đổi 2 phần tử khác cột

Tin hay không cũng được! nhưng em xin nói rằng: 2 ngày cách đây em đã nghĩ theo hướng này, y như thế này! có lẽ là ý tưởng lớn gặp nhau thì phải? Rolling Eyes

Nhưng theo em, đến đây chưa phải là sắp kết thúc đâu! đến đây chỉ mới là bắt đầu mà thôi! hi hi! có lẽ phải đi theo hướng khác thôi! Very Happy

qvluom
Sơ cấp
Sơ cấp

Tổng số bài gửi : 23
Points : 29
Join date : 26/11/2009

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  qvluom on Sun Dec 27, 2009 6:11 pm

ztanzzthanhz đã viết:Phân tích bài toán :
Tin hay không cũng được! nhưng em xin nói rằng: 2 ngày cách đây em đã nghĩ theo hướng này, y như thế này! có lẽ là ý tưởng lớn gặp nhau thì phải? Rolling Eyes
Nhưng theo em, đến đây chưa phải là sắp kết thúc đâu! đến đây chỉ mới là bắt đầu mà thôi! hi hi! có lẽ phải đi theo hướng khác thôi! Very Happy

Sad Sad Tôi rất tin lời của bạn, vì theo kinh nghiệm của tôi cho thấy rằng hễ có 10 người giải bài này thì có hết 8 người suy nghĩ như vậy rồi. Rất may là bạn đã không đi theo con đường ấy Very Happy Very Happy
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  admin on Tue Mar 30, 2010 8:28 pm

Sao lâu quá k thấy bạn nào giải bài hết vậy ta. Các bạn nên cố gắng hơn tí nữa, các bạn sẽ thành công!

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  ztanzzthanhz on Fri Apr 02, 2010 10:24 am

thầy Lượm mà còn phải giải 2 năm mới được thì tụi em gấp gì chứ thầy? Laughing Laughing
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  admin on Fri Apr 02, 2010 11:30 am

Tuổi trẻ thì phải tiến bộ hơn chứ "sóng sau vồ sóng trước mà" Razz , nên chắc em sẽ thành công hơn. Hãy tự tin vào chính mình. Razz
avatar
admin
Admin
Admin

Tổng số bài gửi : 1207
Points : 3010
Join date : 11/11/2009
Age : 37
Đến từ : Cần Thơ

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  admin on Fri Jun 03, 2011 3:39 pm

Khơi lại chủ đề này, có ai giải bài toán này không. Có thưởng lớn đấy.

ztanzzthanhz
Trung cấp
Trung cấp

Tổng số bài gửi : 60
Points : 100
Join date : 13/11/2009
Age : 27
Đến từ : Bến Tre

Trả lời: BÀI 1

Bài gửi  ztanzzthanhz on Wed Jun 08, 2011 6:20 pm

Đề bài:
qvluom đã viết:Bài 1.
- Có một số cây có chiều dài cho trước. Cần bắt qua những con kênh có chiều rộng cho trước (không quá 100 cây và 100 con kênh).
- Điều kiện: + Nếu cây dài quá thì bạn có thể chặt nó ra thành vài khúc xài cũng được
+ Chỉ được dùng 1 khúc cây để bắt qua 1 con kênh
+ Khúc cây được dùng để bắt qua con kênh phải có chiều dài lớn hơn chiều rộng của con kênh ít nhất là 1m.
- Bài toán đặt ra là bắt như thế nào để số cây còn lại phải là nhiều nhất (chú ý chỉ tính những cây mà bạn chưa chặt ra).
- Test thì bạn cứ tuỳ ý cho thế nào cũng được.

Ý tưởng:

- Do "Khúc cây được dùng để bắt qua con kênh phải có chiều dài lớn hơn chiều rộng của con kênh ít nhất là 1m". Ta tăng chiều rộng của mỗi con kênh lên 1m để dễ làm việc.

- Điều kiện cơ bản để bài toán có lời giải là TỔNG ĐỘ DÀI CỦA CÁC CÂY phải lớn hơn hoặc bằng TỔNG CHIỀU RỘNG CỦA CÁC KÊNH; và CHIỀU RỘNG CỦA KÊNH RỘNG NHẤT không lớn hơn CHIỀU DÀI CỦA CÂY DÀI NHẤT

- Sắp xếp các cây và các con kênh theo thứ tự giảm dần của chiều dài (chiều rộng)

- Thử chọn 1 cây để bắc qua các con kênh (chọn cây đầu tiên, cũng tức là cây dài nhất)

- Nếu kiểm tra (*) thỏa mãn thì kết thúc. Ngược lại ta sẽ tăng dần lên 2 cây, rồi 3 cây,... Chú ý: ta chỉ chọn những cây có độ dài lớn nhất, vì yêu cầu đặt ra chỉ là số cây còn lại là nhiều nhất, chứ không phải tổng độ dài của các cây còn lại là lớn nhất!

- Nếu tăng lên đến số lượng cây tối đa, mà vẫn không thỏa mãn thì kết luận không có đáp án thỏa mãn yêu cầu.

(*) kiểm tra

- Ta cần kiểm tra TỔNG ĐỘ DÀI CỦA CÁC CÂY ĐƯỢC CHỌN phải lớn hơn hoặc bằng TỔNG CHIỀU RỘNG CỦA CÁC KÊNH.

- Bắc cầu lần lượt cho các con kênh từ lớn đến bé (theo thứ tự đã sắp xếp)

- Với mỗi con kênh, ta sẽ chọn cây có độ dài nhỏ nhất để thử, nếu không đủ dộ dài thì chọn cây dài hơn. Nếu không có cây nào thỏa thì không thể bắc cầu VỚI SỐ CÂY ĐƯỢC CHỌN TRÊN.

- Với mỗi cây sau khi đem bắc cầu thì độ dài còn lại sẽ là độ dài ban đầu trừ đi độ rộng con kênh, sau đó ta sắp xếp lại độ dài của các cây cho theo thứ tự. Nếu độ dài của cây ngắn nhất bằng 0 thì loại hẳn cây đó ra.

- Nếu bắc cầu được hết cho các con kênh, coi như bài toán đã hoàn thành. Xuất ra SỐ CÂY ĐÃ SỬ DỤNG, SỐ CÂY CÒN LẠI.

Code C++:

Code:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define fi "C:\\bai1.inp"
#define fo "C:\\bai1.out"

int SoCay, SoKenh, error;
int Cay[100], Kenh[100];

void DocFile()
{
   FILE *f;
     int i, s;
     f = fopen(fi,"r");

     if (f!=NULL)
   {
            if (fscanf(f,"%d",&s))
                 SoCay=s;
      else {error=1; exit;}

      fscanf(f,"\n");
      for (i=0; i<SoCay; i++)
      {
         if (fscanf(f,"%d",&s))
            Cay[i] = s;
         else {error=1; exit;}
      }

            if (fscanf(f,"%d\n",&s))
                 SoKenh=s;
            else {error=1; exit;}

           fscanf(f,"\n");
      for (i=0; i<SoKenh; i++)
      {
         if (fscanf(f,"%d",&s))
            Kenh[i] = s;
         else {error=1; exit;}
      }
     }
     else error=1;
     fclose(f);
}

long Tong(int A[], int n)
{
   long temp = 0;
   for (int i=0; i<n; i++)
      temp += A[i];
   return temp;
}

int GTLonNhat(int A[], int n)
{
   int m = 0;
   for (int i=0; i<n; i++)
      if (m < A[i])
         m = A[i];
   return m;
}

void BubbleSort(int A[], int n, int index) // index = 1 : sap xep tang;   index = 0 : sap xep giam;
{
   for (int i=n-1; i>0; i--)
      for (int j=0; j<i; j++)
         if ((A[j] > A[j+1]) == index)
         {
            int temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
         }
}

void ChuanHoa(int C[], int &sC, int index)
{
   while (index<sC-1 && C[index]<C[index+1])
   {
      int temp = C[index];
      C[index] = C[index+1];
      C[index+1] = temp;

      index++;
   }

   if (C[sC-1] == 0) sC --;
}

int Try(int C[], int sC, int K[], int sK)
{
   for (int i=0; i<sK; i++)
   {
      int j = sC - 1;
      while (j>=0 && C[j]<K[i]) j--;
      
      if (j>=0)
      {
         C[j] = C[j] - K[i];
         ChuanHoa(C, sC, j);
      }
      else
         return 0;
   }

   return 1;
}

void XuLy()
{
   int i, j, temp[100], sl, flag=0;

   for (i=0; i<SoKenh; i++)
      Kenh[i] += 1;

   long TongChieuRongKenh=Tong(Kenh, SoKenh);
   
   if ((TongChieuRongKenh > Tong(Cay, SoCay)) || (GTLonNhat(Kenh, SoKenh) > GTLonNhat(Cay, SoCay)))
   {
      FILE *f;
        f = fopen(fo,"w");
        fprintf(f,"Khong co ket qua nao thoa man du lieu nay!");
        fclose(f);
   }
   else
   {
      BubbleSort(Kenh, SoKenh, 0);
      BubbleSort(Cay, SoCay, 0);

      i=0;
      while (i<SoCay && !flag)
      {
         sl = i+1;
         for (j=0; j<sl; j++)
         {
            temp[j] = Cay[j];
         }

         if (TongChieuRongKenh <= Tong(temp, sl))
         {
            if (Try(temp, sl, Kenh, SoKenh))
            {
               FILE *f;
                 f = fopen(fo,"w");
               fprintf(f,"So cay da dung la: %d \n", sl);
                 fprintf(f,"So cay con lai la: %d", SoCay-sl);
                 fclose(f);
               flag = 1;
            }
         }

         i++;
      }
   
      if (!flag)
      {
         FILE *f;
           f = fopen(fo,"w");
           fprintf(f,"Khong co ket qua nao thoa man du lieu nay!");
           fclose(f);
      }
   }
}

void main()
{
   DocFile();
   XuLy();
}

Cấu trúc TEST
- Dòng 1: số cây
- Dòng 2: Danh sách các chiều dài của các cây (mỗi số cách nhau ít nhất 1 khoảng trắng)
- Dòng 3: số kênh
- Dòng 4: Danh sách các chiều rộng của các kênh (mỗi số cách nhau ít nhất 1 khoảng trắng)

Ví dụ:
Code:

6
3 2 5 4 7 8
4
4 3 6 2

Bài này đã quá hạn giải lâu lắm rồi, nhưng em rất mong nhận xét của thầy!

(Dương Tấn Thành)

Sponsored content

Re: Thử giải đề cho vui. "Có thưởng đấy"

Bài gửi  Sponsored content


    Hôm nay: Thu Sep 20, 2018 1:30 am