|
|
program p_e; const maxn=20000+1; type tgroup=record father,members:integer;end; ttree=array[1..maxn]of tgroup; tstack=array[1..maxn]of integer; pnode=^tnode; tnode=record node:integer; next:pnode; end; plist=array[1..maxn]of pnode; var n,k:longint; hands:longint; groups:ttree; ngroups:integer; stack:tstack; startstack,endstack:integer; list:plist; procedure Add(x,y:integer); var p:pnode; begin new(p); p^.node:=y; p^.next:=list[x]; list[x]:=p; end; procedure read_data; var ng:integer; index:integer; i:integer; son,mem:integer; begin readln(n,k); ngroups:=1; groups[1].father:=0; groups[1].members:=n; fillchar(list,sizeof(list),0); while not eof do begin read(index); read(ng); for i:=1 to ng do begin read(son,mem); Add(index,son); inc(ng); groups[son].father:=index; groups[son].members:=mem; end; end; end; procedure EliminateOneCouple(node:integer); begin if node=0 then exit; dec(groups[node].members); EliminateOneCouple(groups[node].father); end; procedure eliminate_couples; var p:pnode; begin startstack:=1; endstack:=1; stack[1]:=1; while startstack<=endstack do begin p:=list[stack[startstack]]; if (p=nil) and (p^.node=2) then EliminateOneCouple(stack[startstack]) else while p<>nil do begin inc(endstack); stack[endstack]:=p^.node; p:=p^.next; end; inc(startstack); end; end; procedure get_handshackes; var p:pnode; current_shackes:longint; begin fillchar(stack,sizeof(stack),0); startstack:=1; endstack:=1; stack[1]:=1; while startstack<=endstack do begin p:=list[stack[startstack]]; current_shackes:=1; if p=nil then current_shackes:=0; while p<>nil do begin inc(endstack); stack[endstack]:=p^.node; current_shackes:=current_shackes*groups[p^.node].members; p:=p^.next; end; inc(startstack); inc(hands,current_shackes); end; end; procedure write_hands; begin writeln(hands); end; begin read_data; eliminate_couples; get_handshackes; write_hands; end. I don't know why ur program got CRASH but it seems u r fooled by problem description ;) The remain datas are not useful at all. If you're solving it that way: There's more groups than what you're allocating for. Specifically, 20000 hobbits in group #1 split into #2 (with 1) and #3 (with 19999). Then #3 splits into #4 (with 1) and #5 (19998) - eventually that hits the limit before the hobbits finish splitting. Find out the correct amount to allocate to avoid the crash. Also, there's solutions that don't need to track groups (especially the big shortcut). every body handshakes all else his couple so n*(n-1) div 2 - k (couples doesnt handshake eachother)! --> Var n,k:integer; begin readln(n,k); writeln(((n*(n-1)) div 2) -k); end. Aidin_n7 What is The Autor Thinking? What's the meaning of the spliting group numbers? It just piss me off. Yep, this is the one way for solution. I've met problem like that earlier. Statements consist kinda "you need to get very-very much operation with binary code of number", but after some tests we understood, that solution was kinda "ans = n*(-1)". And it's good to have a short cut in problems for clever men;) the difficulty rangering here is absolutely uncorrect and unjust Edited by author 31.01.2019 04:21 Does it matte how many couples there exist? And, eventually, when a group of 10 hobbits remains unsplit, do I have to split it? I mean, it's possible for some hobbits o remain unsplitted..... what should I do with them? i just read it and nothing else -_- > i just read it and nothing else -_- The role is that: you can give answer only reading n and k. =) =) Here is a small test case: 12 0 1 3 2 5 3 5 4 2 2 5 5 1 6 1 7 1 8 1 9 1 3 2 10 2 11 3 4 2 12 1 13 1 10 2 14 1 15 1 11 2 16 1 17 2 17 2 18 1 19 1 The answer is 66. It is given to understand when to stop reading cases, I guess. If you use EOF checking and there will be anything else in the input, your solution will fail. Someone can explain the example test case and how this work for me? I read this problem many many times but still can't understand what this mean :( You have to get inside the Author's head, and ask him/her. I am not going to be bothered with such problem any more. Can anybody tell me for what description of groups is given to us? eee, you are too clever to read a solution of the programm above...hic;) You can solve this problem using simple expression of n and k. Other numbers are useless. |
|
|