Vòng thi thử - Hội thi tin học

[ngtrhieu0011]

Bunch

Cho N ly nhựa, đánh số từ 1 đến N và xếp thành một dãy trên bàn thành một dãy theo thứ tự tăng dần từ trái sang phải tạo thành N chồng ly, mỗi chồng có một ly. Dãy các chồng ly này được gom lại nhờ các phép di chuyển cho dưới dạng a b: xếp chồng ly chứa ly a lên trên chồng có ly b (nếu các ly a và b ở cùng một chồng hoặc a = b thì trạng thái các chồng ly không thay đổi). Ví dụ, với N = 7 và 5 phép di chuyển 13, 26, 16, 47, 42, dãy các chồng ly sẽ thay đổi như sau:
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
1 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * * *
* 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * 2 *
* * 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * 4 5 6 7


* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 4
* * * * 5 6 7

* * * * * 4 *
* * * * * 7 *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * * 5 6 *

Yêu cầu: Cho trước M phép di chuyển. Hãy xác định số ly có trong chồng có nhiều ly nhất sau khi thực hiện một phép di chuyển nào đó rồi thực hiện tiếp M phép di chuyển này (thực hiện cả thảy M+1 phép di chuyển).

Dữ liệu: Vào từ file văn bản BUNCH.INP:
• Dòng đầu tiên chứa lần lượt hai số nguyên N, M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000)
• M dòng sau: mỗi dòng chứa hai số nguyên a, b xác định một phép di chuyển.

Kết quả: Đưa ra file văn bản BUNCH.OUT trên một dòng số nguyên, là số ly tìm được.

Ví dụ:
BUNCH.INP
6 4
5 2
3 3
1 3
6 2
BUNCH.OUT
5
Giải thích
-Đầu tiên ta thực hiện phép di chuyển 61 (hoặc 16)
-Tiếp theo ta thực hiện 4 phép di chuyển như mô tả trong file BUNCH.INP thì được chồng ly có số đĩa nhiều nhất là 5.
-Không còn cách nào khác để có chồng ly với 6 đĩa trở lên.

[bld]

ủa theo quy định là gửi vào email của bgk mà
chạy thử với ct của quang rồi , nhanh đấy ! nhưng ko biết đúng ko

[m2mpro]

Bài này chỉ cần có 1 nhận xét đơn giản là có thuật toán đúng thôi :)

[bld]

@ anh hieu : chừng nào thì hết hạn nộp bài vậy a , bài này khó quá ^^', ko biết cách e làm có đúng ko nữa ... đang code , sẽ nộp code qua tin nhắn của a @ a m2mpro ,

[quangtq]

Sao lại ko biết đúng không. Bạn có test thì test hộ.
Do trình ruồi nên suy nghĩ cũng rất bình thường, ko có sử dụng thuật toán nào hết. Ko qhd, ko quay lui v.v.., chỉ dựa vào đề bài
P/S: quên mất. Post luôn ở đây rồi

[ngtrhieu0011]

yêu cầu bạn Quangtp xóa code đi nhá, nộp wa mail thôy, chép ở đây coi như là share code đó

[=========> Bổ sung bài viết <=========]

nộp qua ngtrhieu0011@gmail.com

[linhhahaduc]

Ko biết mình có hiểu nhầm đề ko! Hình như bài này là tìm thành phần liên thông có nhiều đỉnh nhất hả ?

[=========> Bổ sung bài viết <=========]

P/s : Time limit bài này bao nhiêu vậy ?

[ngtrhieu0011]

không nói jì thì hiểu là 1s nhé ^^

[quangtq]

Đã gửi vào mail. Check đi anh
P/S: Sao anh cứ nhầm chữ p với q thế nhỉ

[linhhahaduc]

Hội thi này bao giờ thi có kết quả nhỉ ? :X hồi hộp ghê

[quangtq]

anh Hiếu ko thấy comment gì lại à? Nhận được chưa, thế nào anh? Hix. Hồi hộp chờ cả ngày!

[bld]

hạn nộp chừng nào vậy >.<'

[=========> Bổ sung bài viết <=========]


Ko biết mình có hiểu nhầm đề ko! Hình như bài này là tìm thành phần liên thông có nhiều đỉnh nhất hả ?

a duc đừng comment gì chứ , câu này gợi nhiều ý tưởng cho ng # lắm ^^

[ngtrhieu0011]

chắc fải đến cn tuần sau mới có kq, dạo này đang chuẩn bị thi kt chất lượng đầu năm và hội diễn chú ve con

[linhhahaduc]

"hội diễn chú ve con" nào vậy nghe hay quá , cho mình xem với :x

[quangtq]

Èo. Lâu dzậy ta. >1 tuần nữa là thi òy. HIx

[ngtrhieu0011]

là hội thi văn nghệ giữa các trường cấp 3, tổ chức trong hè ở đầm sen, trường mình thứ 7 này thi vòng 1 nè... ^^
ai có ý kiến thuật giải bài này thì comment đi

[quangtq]

Thuật giải của em quá ngu, ko biết đúng không.
Gọi chiều cao của cột i là H[i];
Với i:=1 -> m đặt Chiều cao của cột b[i]+=h[a[i]], gán lại h[a[i]] = 0.
Tìm max của h, loại max ra, tìm tiếp max của h.
Kq là tổng 2 cái này.
Chắc sai lòi tĩ.

[bld]

tò te rồi nhé quang :
đặt là h[a[i]]=0 ?chỗ này nghiêm trọng đây , đọc kĩ lại đề chỗ chuyển ly : chuyển cột có ly A sang cột có ly B ,
giả sử inp thế này
4 2
1 3
1 2
thì biểu diễn các bước
* * * *
* * * *
1 2 3 4
...
* * * *
* * 1 *
* 2 3 4
...
* 1 * *
* 3 * *
* 2 * 4
.. vậy thì lúc đầu ta chuyển 42 hay 24 thì được max = 4
còn quang :
1 3 :h[3]=1+1=2 h[1]=0
1 2 :h[2]=1+0=1 h[1]=0
có được dãy h : 0 1 2 1 , vậy max=3 , ---> nhầm ...

à , anh hiếu : sao chưa đến hạn mà đã comment về lời giải rồi , e còn đang code

[=========> Bổ sung bài viết <=========]

thêm 1 thắc mắc về đề nữa , 2 ly a & b có nhất thiết đang ở trên cùng của chồng chứa nó không ? trong đề không nói đến chuyện này , vậy cái vd của anh có thể ngoài cách 16 hay 61
còn có 63 36 51 15 53 35 21 12 23 32 nữa ... ? không biết đúng không

[quangtq]

Nhục vãi chưởng. Kéo phải giấu mặt 1 tuần trên 4rum mất.

[ngtrhieu0011]

hạn là 1 ngày àh, bài này là bài thi chọn đội tuyển olimpiad 30/4 khối 10 trường LHP đó.

hướng giải: nếu thực hiện bước di chuyển của mình rồi thực hiện thêm M bước nữa thì cũng như thực hiện M bước đó rồi mới làm bước của mình. ^^

[bld]

trời , vậy a hieu : e không được nộp bài nữa à ! huhu

[=========> Bổ sung bài viết <=========]

biết vậy nộp sớm , khỏi chỉnh sửa cũng ăn dc vài test roài huhu

[=========> Bổ sung bài viết <=========]

hay a kéo dài hạn nộp ra , a cứ cho hạn nộp là 1 ngày thì cuối cùng cuộc thi cũng chỉ cho mình quang thi chớ mấy ^^, mem khác bận túi bụi

[=========> Bổ sung bài viết <=========]

code của e nè , quái là chạy với m, n =10000 thì 1s, còn 100000 thì lên tới 15s , kì lạ thật
a hieu có code nào chạy 1s với M=N=100000 thì chỉ giùm cái thuật toán với


type bld=-2..100000;
var h,ax:array[1..100000] of bld;
free:array[1..100000] of boolean;
f:text;
m,n:bld;
max1,max2:bld;

procedure init;
var i:bld;
begin
for i:=1 to n do begin free[i]:=true; h[i]:=1; ax[i]:=i; end;
max1:=-1;
max2:=-2;
end;

procedure find(var a,b:bld);
begin
while ax[a]<>a do a:=ax[a];
while ax[b]<>b do b:=ax[b];
end;

procedure nhap;
var i,a,b:bld;
begin
assign(f,'bunch.inp');
reset(f);
readln(f,n,m);
init;
for i:=1 to m do
begin
readln(f,a,b);
find(a,b);
if a<>b then
begin
free[a]:=false;
h[b]:=h[b]+h[a];
ax[a]:=b;
end;
end;
close(f);
end;

procedure findmax;
var i:bld;
begin
for i:=1 to n do if free[i] then
if h[i]>max1 then
begin
max2:=max1;
max1:=h[i];
end
else if h[i]>max2 then max2:=h[i];
end;

procedure ghi;
begin
assign(f,'bunch.out');
rewrite(f);
write(f,max1+max2);
close(f);
end;

BEGIN
nhap;
findmax;
ghi;
END.

[quangtq]

Do đang bận ôn nên mình làm bài thi có trong 1 tiếng. Thấy đúng cái test đầu là nộp, đi làm mấy bài hình (do limit bài, toàn bài khó).
Bao giờ bắt đầu vòng 2? Cho hạn thêm đi chứ. Em dạo này bận tóe khói.
Thuật toán của bld là gì vậy. Thấy hơi giống của mình.

[bld]

bài này tìm 2 thành phần liên thông lớn nhất , cứ xem mỗi thành phần có 1 nút gốc , nút đó mang độ lớn của thành phần đó và có ax của nó = chính nó , free của nó = true , các nút phụ thuộc khác có ax nối tới 1 nút khác và free = false , sau khi thực hiên hết thì tìm max1,max2 của các nút có free=true , công lại,....

[quangtq]

Vậy ăn được mấy test?????????

[bld]

mình đâu có test , đề anh hieu test thử chứ

[m2mpro]

Hiếu đã nói hướng giải rồi đó :

(1) : Thực hiện 1 bước của mình trc.
(2) : Thực hiện M bước theo yêu cầu.

Nhận xét : Do tất cả các chồng lúc đầu đều có 1 ly => (1)->(2) <=> (2)->(1).

Bây giờ, ta thực hiện M bước theo đề bài, tất nhiên ta sẽ có dễ dàng tính đc chồng lớn nhất có bao nhiêu ? Bây giờ có 2 trường hợp xảy ra :

- Tất cả các chồng đều bị ảnh hưởng của M phép biến đổi : thì ta sẽ lấy 1 ly từ một chồng nào đó ko ảnh hưởng trong việc biến đổi tạo ra chồng lớn nhất chồng lên chồng lớn nhất

- Tồn tại 1 chồng ko bị ảnh hưởng của M phép biến đổi : vẫn đơn giản lấy 1 ly của chồng này chổng lên chồng lớn nhất :)

[linhhahaduc]

Cách làm của mình là coi mỗi a b là đỉnh a và b có đg nối , rồi qua m bước , tìm 2 thành phần liên thông có nhiều đỉnh nhất . Từ đó lấy 1 a và 1 b bất kì nào đó trong 2 thành phần liên thông đó ---> kết quá . :D chả biết có đúng ko ? =))

[=========> Bổ sung bài viết <=========]

P/s : Hình như có 1 nhận xét là M bước đó thực hiện bước nào trước cũng đều ra 1 kq giống nhau :D

[ngtrhieu0011]

bài này chẳng dùng thuật toán nào cả, cứ thực hiện M bước đổi rồi sau đó lấy 2 chồng cao nhất úp lên nhau

[caimongs]

tại sao thi tin học toàn thấy lập trình nhỉ

[linhhahaduc]

Thảo nào thôi xác định luôn bài mình tle

[=========> Bổ sung bài viết <=========]

Có được đóng góp đề cho BGK đề làm đề thi ko nhỉ ? ;)) mình còn cả đống bài khó , đang bí :))

[m2mpro]

bài này chẳng dùng thuật toán nào cả, cứ thực hiện M bước đổi rồi sau đó lấy 2 chồng cao nhất úp lên nhau

Mình nghĩ bạn nhận xét sai vấn đề, khi bạn thực hiện 1 phép biến đổi ban đầu, có nghĩa các chồng chỉ bị thay đổi +1 hoặc -1, còn nếu bạn lấy 2 chồng cao nhất úp lên nhau thì cái thay đổi này là sai hoàn toàn :)

[ngtrhieu0011]

@linhhahaduc: xin bạn đọc lại cách tham gia đóng góp đề
@m2mpro: xin đọc kĩ lại đề

[=========> Bổ sung bài viết <=========]



Program Bunch;

Const Fin = 'Bunch.Inp';
Fou = 'Bunch.Out';
MaxArr = 100000;

Type Arr = Array [1..MaxArr] of Word;

Var A,B : Arr;
N, M : Longint;
i : Longint;
u,v : Longint;
Max1, Max2 : Longint;
F : Text;

Begin
Assign(F, Fin);
Reset(F);
Max1 := 1;
Max2 := 1;
Readln(F, N,M);
For i:=1 to N do
Begin
A[i] := i;
B[i] := 1;
End;
For i:=1 to M do
Begin
Readln(F, u,v);
While A[v] <> v do
v := A[v];
A[u] := v;
If u <> v then
B[v] := B[v] + B[u];
If B[v] > Max1
then Max1 := B[v]
else
If B[v] > Max2
then Max2 := B[v];

End;
Close(F);
Assign(F, Fou);
Rewrite(F);
Write(F, Max1+Max2);
Close(F);
End.

[m2mpro]

N = 6
Các phép di chuyển
1 -> 3
2 -> 4
4 -> 6

Theo cách của bạn sẽ ra là 5, bạn nghĩ bạn thực hiện phép biến đổi nào trc rồi thực hiện 3 phép biến đổi trên sẽ cho ra 5 ?

[bld]

sao ra 5 được ! anh m2m nói thử anh chuyển thế nào mà ra 5 ?
a hieu test giùm bài của e thử được bao nhiêu điểm ?

[quangtq]

Nếu 2 chồng cao nhất úp lên nhau thì chẳng nhẽ em lại đúng à.

[bld]

ko phải , bài của quang sẽ sai trong lúc tính chiều cao của các chồng , nên sẽ ko bước dc tới bước tìm 2 chồng lớn nhất, -> nên kq ko đúng , thường ra kq thấp hơn bình thường do bạn đặt lại h[a[i]]=0

[ngtrhieu0011]

theo test m2mpro:


1 -> 3
2 -> 4
4 -> 6

thì bước thực hiện của ta là:
3 -> 6
vậy thì 4 bước chuyển:


3 -> 6
1 -> 3
2 -> 4
4 -> 6






1 2 3 4 5 6


3
1 2 _ 4 5 6


1
3
_ 2 _ 4 5 6



1
2 3
_ _ _ 4 5 6


2
4
1
3
_ _ _ _ 5 6



Bạn còn gì thắc mắc?

[bld]

bài này bản chất là tìm 2 thành phần liên thông lớn nhất như a linhhahaduc nói ,chồng ly chỉ là lớp vỏ ngoài thôi

[ngtrhieu0011]

mọi người có thể hiểu như vậy, nhưng tác giả viết bài này chủ yếu để đánh đố mọi người thôy.
nếu bạn nhìn ra hướng giải, thì code quá là đơn giản phải không? (tôi code 42dòng, tính lun các dòng thừa)

[quangtq]

Chuẩn. Cứ phức tạp hóa vấn đề lên.
Đi thi nếu ko nghĩ ra thuật toán nào thì nghĩ gì làm nấy :D

[bld]

a hieu nói thuật toán của mình đi
xin đừng nói mấy từ "làm như bình thường " nhé , vì "làm như bình thường cũng có 1 số vấn đề " ... như của quang í

[m2mpro]

(1) //Trạng thái ban đầu
1 2 3 4 5 6

(2) //Theo bạn chuyển từ 3 -> 6
3
1 2 _ 4 5 6

(3) //Làm theo M, bước 1 đâu có chuyển từ 1 -> 6 mà mình nói chuyển từ 1 -> 3 mà ?
1
3
_ 2 _ 4 5 6


(4)
1
2 3
_ _ _ 4 5 6

(5)
2
4
1
3
_ _ _ _ 5 6


Sai ở bước biến đổi thứ 3, mình đưa ra là từ 1 -> 3 chứ đâu có từ 1 -> 6.

Theo đề :



sau khi thực hiện một phép di chuyển nào đó rồi thực hiện tiếp M phép di chuyển này

Giả sử bước đầu tiên biến đổi là a -> b, ta chỉ đưa 1 ly a -> chồng b. Chứ theo bạn là tất cả các ly nếu đc chuyển tới chồng a đều đc chuyển tới chồng b ?

Mình nghĩ 1 là bạn đánh sai đề
2 là bạn bị ngộ nhận đề, đọc đề ko kĩ dẫn đến thuật toán sai :)

[bld]

tất cả
................................
mới là đúng đề

[lehang_gb1]

Phần đề ở ví dụ mình thấy thiếu phải là các phép di chuyển (1,3), (2,6), (3,6),(1,6),(1,7),(4,2) nhưng ở đề lại không có phép chuyển (3,6) nên mình ko hiểu từ bước 4 xuống bước 5 là thế nào
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
1 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * * *
* 2 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * * *
* * * * * * *
* * 1 * * 2 *
* * 3 4 5 6 7

* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * 4 5 6 7


* * * * * * *
* * * * * * *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 4
* * * * 5 6 7

* * * * * 4 *
* * * * * 7 *
* * * * * 1 *
* * * * * 3 *
* * * * * 2 *
* * * * 5 6 *

[=========> Bổ sung bài viết <=========]

ĐỌc xong chẳng hiểu đề ra sao nữa
(nếu các ly a và b ở cùng một chồng hoặc a = b thì trạng thái các chồng ly không thay đổi). chưa hiểu

[=========> Bổ sung bài viết <=========]

CHuyển thế nào mà chẳng được số đĩa nhiều nhất

[bld]

bước di chuyển 3 6 là ở hình thứ 4 đó
bạn đọc kĩ lại đề : chuyển cột có chứa ly a lên cột chứa ly b :
tức chuyển cột có chứa ly 3 lên cột cói chứa ly 6 , bạn hiểu chứ ?

như vậy nếu 2 ly a và b cùng 1 chồng thì việc gì phải chuyển ly chứa chồng a lên ly chứa chồng b (cũng là ly chứa chồng a ) nữa ? và a=b dĩ nhiên chẳng chuyển gì cả

[linhhahaduc]

rút cục là ban tổ chức chắc có solution chuẩn mới dám cho thi chứ B-) :)) cãi làm gì , mệt lắm . Cứ suy nghĩ kĩ rùi hẵng post

[lehang_gb1]

Hình thứ 4 trong ví dụ cho la (1 6) mà có phải là (3 6) đâu bld

[=========> Bổ sung bài viết <=========]

Nhưng mình thấy chuyển 5 lần thì chuyển như thế nào vấn được chồng 6 đĩa

[=========> Bổ sung bài viết <=========]

Như ví dụ Với N=7 và 5 phép chuyển thì mình chuyển đơn giản như (1,2), (3,2), (4,2), (5,2),(6,2) cũng được chứ sao.

[ngtrhieu0011]

bạn nào có thắc mắc test nào thì post lên tớ sẽ demo chạy thử ^^
mấy bạn thấy đề hay hok :">

[bld]

ax, 1 6 có khác gì với 3 6 . vì 1 và 3 cùng 1 chồng mà !

[ngtrhieu0011]

kq bài chấm bạn:
linhhahaduc: 2/10tests
quangtp: 1/10 tests

[bld]

thế còn e ?????
tuy nộp trễ , a cứ chấm , ko cộng vào điểm thi cũng dc

[ngtrhieu0011]

hok thấy bài em :|
__________________________________________________
bài này coi bộ không ai nhìn ra hướng giải cả >_<

[bld]

sặc, bài e pót trong topic này chứ có gửi cho a đâu , đằng nào cũng nộp trễ, hình như ở trang 2 hay sao í

[quangtq]

Ahahaha. Giải thuật sai cũng được 1/10 à.
Tại thời gian gấp quá nên làm bừa. Lần sau anh cho hạn nhiều hơn đi.

[linhhahaduc]

=)) biết ngay mà . Hôm đấy đầu quay cuồng , copy code nguồn rồi sửa thành bài này :) . hik hik . Lần sau rút kinh nghiệm :D