ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1194. Handshakes

Why Am i getting Crash (ACCESS_VIOLATION) ?
Posted by Costel::icerapper@k.ro 3 Mar 2002 23:07
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;

var
p:pnode;
begin
new(p);
p^.node:=y;
p^.next:=list[x];
list[x]:=p;
end;

var
ng:integer;
index:integer;
i:integer;
son,mem:integer;
begin
ngroups:=1;
groups[1].father:=0;
groups[1].members:=n;
fillchar(list,sizeof(list),0);
while not eof do
begin
for i:=1 to ng do
begin
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
eliminate_couples;
get_handshackes;
write_hands;
end.
...
Posted by I have answers to all your questions :) 4 Mar 2002 00:24
I don't know why ur program got CRASH but it seems u r fooled by
problem description ;)
Maybe... maybe u can explain it to me better
Posted by Costel::icerapper@k.ro 4 Mar 2002 03:26
This problem can be solved by an simple expression using only n and k.
Posted by Song Chao (ECUST Mutistar) 7 Mar 2002 14:59
The remain datas are not useful at all.
Re: This problem can be solved by an simple expression using only n and k.
Posted by Yuan 16 Mar 2002 12:21
n(n-1)/2-k
Re: Why Am i getting Crash (ACCESS_VIOLATION) ?
Posted by Raymond Martineau 11 Jan 2022 10:25
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).