Đề OLP Tin học SV 2005 - Tập thể lều chõng không chuyên

[Nguyễn Hữu Hùng]

Hi! Đây là đề đầu tiên.

Đề OLP Tin học SV 2005 - Tập thể lều chõng không chuyên

Chúng ta cùng làm đề này trước, nó khá là dễ xơi, các bạn thịt nó trong 2h nhé.

[Nguyễn Hữu Hùng]

Hic, không có ai tham gia hết!

[WinnerNeverQuits]

có, t  và Triển đã tham gia giải bài này, nhưng hình thức làm bài này ntn, trao đổi giải thuật, input, output, hay xây dựng 1 cách làm lý tưởng nhất có thể hả c???

Vào 16:24 Ngày 08 tháng 9 năm 2011, Nguyễn Hữu Hùng <unregis...@gmail.com> đã viết:

Hic, không có ai tham gia hết!

--

...>>WNQs<<...

[Luc Bui Van]

T cũng tham gia mak.
________________
Người gửi
Bùi Văn Lực
Email: luc...@gmail.com
Sđt: 01.255.255.266

Vào 16:24 Ngày 08 tháng 9 năm 2011, Nguyễn Hữu Hùng <unregis...@gmail.com> đã viết:

Hic, không có ai tham gia hết!

[Lotus Koder]

Tớ cũng trao đổi vs thắng giải thuật 3 bài này rùi *_* Hùng vs Lực có thể nói sơ qua về giải thuật bài 2 được ko *_* chắc thuộc dạng số lớn. 

[Luc Bui Van]

T thấy đây cũng ko phải dạng bài số lớn vì -1 000 000<= ai <=1 000 000 nên có thể lưu bằng biến bt int, hoặc long. chỉ làm sao để chạy nhanh thôi N<=20 000, thời gian 2 giây.

________________
Người gửi
Bùi Văn Lực
Email: luc...@gmail.com
Sđt: 01.255.255.266

Vào 20:44 Ngày 08 tháng 9 năm 2011, Lotus Koder <smiles...@gmail.com> đã viết:

[WinnerNeverQuits]

vs dk là -1 000 000<= ai <=1 000 000 thì phải khia báo là "long", int ko đc

Vào 21:02 Ngày 08 tháng 9 năm 2011, Luc Bui Van <luc...@gmail.com> đã viết:

--

...>>WNQs<<...

[WinnerNeverQuits]

chưa ai nói đến giải thuật nhẩy, ai đó nói đi chứ

Vào 21:26 Ngày 08 tháng 9 năm 2011, WinnerNeverQuits <ngocva...@gmail.com> đã viết:

--

...>>WNQs<<...

[Luc Bui Van]

Tại sao lại ko dc trong khi kiểu long có độ rộng dữ liệu từ 2^-31 đến 2^31 -1

________________
Người gửi
Bùi Văn Lực
Email: luc...@gmail.com
Sđt: 01.255.255.266

Vào 21:26 Ngày 08 tháng 9 năm 2011, WinnerNeverQuits <ngocva...@gmail.com> đã viết:

[WinnerNeverQuits]

ý c là sao, int chỉ giới hạn trong -32xxx -> 32xxx (-2^16-1->2^16-1) thui
còn long thì tầm -1 tỷ -> 1 tỷ(-2^32-1 -> 2^32-1)
-1 000 000<= ai <=1 000 000, vậy phải khai báo  long, t nghĩ thế

Vào 21:33 Ngày 08 tháng 9 năm 2011, Luc Bui Van <luc...@gmail.com> đã viết:

--

...>>WNQs<<...

[Luc Bui Van]

kiểu int 4 byte bây giờ cũng bằng vs kiểu long -2^31 đến 2^31 -1 

còn int 2 byte từ -32768 đến 32767. Tùy thuộc vào HĐH sử dụng.

________________
Người gửi
Bùi Văn Lực
Email: luc...@gmail.com
Sđt: 01.255.255.266

Vào 21:26 Ngày 08 tháng 9 năm 2011, WinnerNeverQuits <ngocva...@gmail.com> đã viết:

[Luc Bui Van]

Tùy thuộc vào HĐH thui. Đa số kiểu int giờ là 4 byte rùi

từ (-2^31) đến (2^31) - 1.

________________
Người gửi
Bùi Văn Lực
Email: luc...@gmail.com
Sđt: 01.255.255.266

Vào 21:43 Ngày 08 tháng 9 năm 2011, WinnerNeverQuits <ngocva...@gmail.com> đã viết:

[Luc Bui Van]

Thảo luận chút bài 3:

Giải thuật của t là tính cứ tính tổng diện tích của HCN1 + diện tích HCN2

sau đó tính diện tích của HCN bao (có tọa độ lần lượt trái dưới là x bé nhất, y bé nhất, phải trên là x lớn nhất y lớn nhất) nếu tổng (diện tích HCN1 + diện tích HCN2) > diện tích HCN bao thì hai HCN có phần chung, và tạo thành 1 vùng. ngc lại thì 2 HCN không có phần chung và tạo thành 2 vùng riêng biệt.

[Nguyễn Hữu Hùng]

Hi, cứ tưởng không bạn nào tham gia hết cơ :P

Ý tớ là tham gia thảo luận về giải thuật, code từng bài, ai có ý tưởng hay thì trình bày cho mọi người.

Theo ý kiến của tớ:

- Đề thi này không khó, cũng có thể nói là "hơi dễ".

- Đề bài gồm 3 bài, mỗi bài một dạng:

 + Bài 1: Xử lý chuỗi

 + Bài 2: Sắp xếp

 + Bài 3: Hình học

* Phân tích cụ thể:

- Bài 1: Ta thấy số mà không là kết quả mã hóa của số nào khác (số M cần tìm) phải có số các chữ số là một số lẻ. Vậy ta chỉ cần thao tác ngược lại qui trình mã hóa đến khi nhận được số có số các chữ số là một số lẻ thì đó là KQ. Ta cần đưa về dạng chuỗi thao tác cho đơn giản.

VD (test trong đề) 21322113 -> 11222113 -> 122113 -> 2113 -> 113 là kết quả vì nó có 3 chữ số (3 là số lẻ).

- Bài 2 thực chất không phải bài về big number, việc phải làm là sắp xếp N số cho trước theo thứ tự tăng dần rồi kiếm tra xem nó có tạo thành dãy cấp số cộng không. Với N = 20,000 thì việc sắp xếp theo cách thông thường mất khá nhiều thời gian. Vì thế bài này nên chọn cách sắp xếp nhanh như Quick Sort. Hoặc nếu không làm theo quick sort thì nên kết hợp việc kiểm tra với việc sắp xếp để rút ngắn thời gian chạy.

- Bài 3 là bài dạng hình học cụ thể liên quan tới HCN. Bài này giải thuật có tớ như sau:

Bước 1:

- Vẽ HCN bất kỳ vào hệ trục tọa độ, S bao = S HCN này

Bước 2:

- Vẽ HCN bất kỳ khác vào.

Bước 3:

+ Nếu HCN này nằm ngoài các HCN nào đang có => S bao = S bao + S HCN này.

+ Nếu HCN này cắt 1 HCN khác có sẵn

- Tạo HCN bao 2 HCN này, S bao mới = S bao cũ - S của 1 HCN con cắt nhau.

- Quay lại B3 với HCN mới là HCN bao này

Bước 4:

- Nếu còn HCN thì quay lại B2

Bước 5:

- In KQ là S bao.

VD (test cho sẵn):

- Vẽ HCN 1: S = 8

- Vẽ HCN 2: S = 8 + 1 = 9

- Vẽ HCN 3: S = 9 - 8 = 1

Quay lại B3: S = 1 - 1 =0

Quay lại B3: S = 25

- Vẽ HCN 4: S = 25 + 6 = 31

- Vẽ HCN 5: S = 31 + 6 = 37

- Vẽ HCN 6: S = 37 - 6 = 31

Quay lại B3: S = 31 + 18 = 49

Với giải thuật này code rất ngắn, chỉ cần 2 vòng lặp lồng nhau, vòng lặp thứ nhất vẽ từng HCN vào trục tọa độ (Bước 2 -> Bước 4), vòng lặp 2 xử lý các HCN lồng nhau (Bước 3).

[Luc Bui Van]

Bài 1 thì như Hùng nói, thao tác ngược lại đến khi độ dài mã hóa là số lẻ thì dừng. 

Bài 2 t thấy việc sắp xếp rồi sau đó tìm xem có phải là cấp số cộng hay không thì vẫn khá lâu với N=20 000 và 

 -1 000 000<=ai<=1 000 000,dù nó là dãy cấp số cộng hay không thì vẫn phải sắp xếp.

    

    Cách của t là tìm phần tử bé nhất trong dãy đấy (việc này có thể thực hiện ngay lúc nhập dữ liệu vào, cho min=1 000 001 khi nhập một phần tử vào thì so sánh với min nếu bé hơn thì cập nhật cho min dùng thêm một biến nữa để lưu vị trí của phần tử bé nhất), sau đó dùng một mảng dánh dấu để đánh dấu phần tử bé nhất đã đc sử dụng.

    Tiếp theo tìm phần tử bé thứ hai, chính là phần tử chưa được đánh dấu và bé nhất (tìm được thì đánh dấu là đã dùng). Hiệu phần tử bé thứ 2 - phần tử bé thứ nhất chính là cơ số của cấp số cộng.

    Tìm phần tử bé thứ 3 chính là phần tử chưa được đánh dấu và bé nhất (tìm được thì đánh dấu là đã dùng) rồi tính hiệu phần tử bé thứ 3 - phần tử bé thứ 2. Nếu hiệu này bằng cơ số thì tiếp tục. không thì in ra -1 và thoát 

    Chú ý:

Nếu xét xem phần tử đã được đánh dấu hay chưa rồi mới so sánh tìm min thì tránh được trường hợp so sánh với cả những phần tử đã dùng rồi mới kiểm tra xem nó đã được dùng hay chưa, càng về cuối phần tử phải so sánh càng ít đi

Cách này có thể coi là vừa sắp xếp vừa so sánh, nếu không tạo thành dãy cấp số cộng thì thoát luôn, không phải sắp xếp hết dãy.

Còn bài 3: T vẫn chưa hiểu ý của Hùng lắm.

[Nguyễn Hữu Hùng]

Mình hiểu ý của lực, bài 2 nếu làm như vậy gọi là vừa sắp xếp vừa kiểm tra, độ phức tạp O(N^2) còn nếu sắp xếp xong mới kiểm tra thì là O(N^2+N), nếu dùng Quick Sort thì khoảng O(2N*LnN + N). Từ đó thấy cách dùng Quick sort vẫn tốt hơn một chút :D

[Nguyễn Hữu Hùng]

Test thử với test max N=20000 riêng thao tác sắp xếp.

- Sắp xếp theo cách thông thường (2 vòng for i,j) tốn 2.594 giây

- Sắp xếp bằng quick sort tốn 0.015 giây

Tốc độ cải thiện quá kinh khủng =))

[WinnerNeverQuits]

ok,bài 1 và 2 t đã hiểu cách làm...(giải thuật QuickSort)
bài 3: t xin nói cái ý tưởng lúc đầu trong đầu t khi giải bài này
t dùng đệ quy + điều kiện của bài hcn lồng nhau
Quy trình làm của t là: hàm đệ quy sẽ làm nhiệm vụ là cập nhât số hcn có lồng nhau hay ko, nếu có 2 hay nhiều hcn lồng nhau thì t sẽ dùng 1 hcn bao trùm lên 2 hay nhiều hcn đó, sau hàm đệ quy này, từ n hcn ban đầu đề bài cho, h t chỉ còn m hcn(m<=n), t tiếp tục làm công việc này đến khi ko còn hcn nào lồng nhau nữa thì thui,, thoát, và tính diện tích các hcn sau xử lí trên.
Chắc cách này ko ai làm, :), vì nó là đệ quy mà
Cách của Hùng, nói rõ hơn tí cho mọi ng hiểu vs, cái đoạn cộng trừ kìa

Vào 16:28 Ngày 09 tháng 9 năm 2011, Nguyễn Hữu Hùng <unregis...@gmail.com> đã viết:

--

...>>WNQs<<...

[Nguyễn Hữu Hùng]

Thực chất cách của t cũng là đệ quy nhưng thay vì dùng đệ quy tớ dùng vòng lặp. Nói rõ ra thì nó thế này:

- Khi bắt đầu vẽ thêm một hình chữ nhật vào ta xem nó có cắt HCN nào khác hay không (ở đây chỉ cần xét cắt hoặc không chứ không xét cắt bao nhiêu hình).

 + Nếu không cắt ta lưu HCN này vào một mảng riêng

 + Nếu HCN A mới vẽ cắt một HCN B đã vẽ trước đó thì ta tạo hình chữ nhật bao cho 2 HCN này gọi là HCN C, rồi loại HCN B ra khỏi mảng đã lưu vì HCN bao này chứa cả HCN A và B (thao tác trừ diện tích mà tớ đã nói) rồi ta lại gán HCN A thành HCN C và quay lại bước vẽ.

- Thao tác cứ lặp lại như vậy cho tới khi HCN mới vẽ không còn cắt với HCN nào nữa.

[Nguyễn Hữu Hùng]

Đây là ví dụ hình ảnh cụ thể mà tớ làm, các cậu tải về rồi xem nhé :D

[Nguyễn Hữu Hùng]

//Đây là code bài 3 của mình:
/////////////////////////////////////////////////////////////////////////////////
#include <fstream>
#include <iostream>
#include <math.h>
using namespace std;
struct point
{
int x,y;
};
struct rect
{
point td,pt;
};
ifstream fi;
ofstream fo;
int n,m;
long S = 0;
rect A[101],B[101];
/////////////////////////////////////
void input();
void solve();
void output();
long DienTich(rect X);
double KhoangCach(point P,point Q);
bool CatNhau(rect P,rect Q);
rect HCNBao(rect P,rect Q);
//////////////////////////////////////

rect HCNBao(rect P,rect Q)
{
point TD,PT;
rect KQ;
TD.x=(P.td.x<Q.td.x)?P.td.x:Q.td.x;
TD.y=(P.td.y<Q.td.y)?P.td.y:Q.td.y;
PT.x=(P.pt.x>Q.pt.x)?P.pt.x:Q.pt.x;
PT.y=(P.pt.y>Q.pt.y)?P.pt.y:Q.pt.y;
KQ.td=TD;
KQ.pt=PT;
return KQ;
}
//----------------------
bool CatNhau (rect P,rect Q)
{
if (P.pt.y<=Q.td.y || P.td.y>=Q.pt.y || P.td.x>=Q.pt.x ||
P.pt.x<Q.td.x) return false;
else return true;
}
//----------------------
double KhoangCach(point P,point Q)
{
return sqrt((P.x-Q.x)*(P.x-Q.x)+(P.y-Q.y)*(P.y-Q.y));
}
//----------------------
long DienTich(rect X)
{
point tt;
tt.x=X.td.x;
tt.y=X.pt.y;
return long(KhoangCach(tt,X.td)*KhoangCach(tt,X.pt));
}
//----------------------
void solve()
{
int i,j;
S = 0;
m = 0;
for (i=0;i<n;i++)
{
if (i>0)
{
B3:
for (j=0;j<m;j++)
{
if (CatNhau(A[i],B[j]))
{
S = S - DienTich(B[j]);
A[i] = HCNBao(A[i],B[j]);
for (int k=j;k<m;k++) B[k]=B[k+1];
j--;
m--;
goto B3;
}
}
}
S = S + DienTich(A[i]);
B[m]=A[i];
m++;
}
}
//----------------------
void input()
{
fi >> n;
for (int i=0;i<n;i++)
{
fi >> A[i].td.x >> A[i].td.y;
fi >> A[i].pt.x >> A[i].pt.y;
}
}
//----------------------
void output()
{
fo << S;
}
//----------------------
int main()
{
fi.open("FENCE.INP");
fo.open("FENCE.OUT");
input();
solve();
output();
fo.close();
fi.close();
return 0;
}
/////////////////////////////////////////////////////////////////////////////////