Программистам среди нас

[spamsink]

Порадуйтесь задачкам чемпионата мира по программированию среди студентов:

http://icpc.baylor.edu/icpc/Finals/2006WorldFinalProblemSet.pdf

Обратите внимание на задачу G. Isn't it sweet?

Comments

Вы этого хотели, вот вам

[spamsink]

На собственно программирование ушло 15 минут, еще 15 - на борьбу с Перлом.
Комментарии писал потом.

#!/usr/bin/env perl

# Sentinel is PAY because first/last PAY means nothing
push @elts, 'PAY';
push @vals, 0;

# Converting IN/OUT into SIZE and collapsing, dropping useless COLLECT,
# collapsing PAY

while(<>) {
if (/^IN (\d+)/) {
if ($elts[$#elts] eq 'SIZE') { $vals[$#elts] += $1; }
else { push @elts, 'SIZE'; push @vals, $1; }
next;
}
if (/^OUT (\d+)/) {
if ($elts[$#elts] eq 'SIZE') { $vals[$#elts] -= $1; }
else { push @elts, 'SIZE'; push @vals, -$1; }
next;
}
if (/^PAY (\d+)/) {
if ($elts[$#elts] eq 'PAY') { $vals[$#elts] += $1; }
else { push @elts, 'PAY'; push @vals, $1; }
next;
}
}

# Last 'PAY' is useless
if ($elts[$#elts] eq 'PAY') { pop @elts; pop @vals; }

# Returns divisors of $val, including 1 and $val
sub divs {
my ($val) = @_;
my %res;
my $lim = int(sqrt($val));
for ($i = 1; $lim >= $i; $i++) {
if ($val % $i == 0) { $res{$i} = 1; $res{$val/$i} = 1; }
}
return %res;
}

# Intersects %a, %b and {x : x >= $lim}
sub intersect {
my ($lim) = @_;
my %res;

foreach $i (keys %a) {
$res{$i} = 1 if $i >= $lim && defined $b{$i};
}
return %res;
}

# Adjusts elements of %a by $amt
sub incdec {
my ($amt) = @_;
my %res;
foreach $i (keys %a) {
$res{$i+$amt} = 1;
}
return %res;

}

$lim = 1;

# Each PAY must be a multiple of the current number of people which is
# bounded by the SIZEs

while ($#elts > 0) {
$type = $elts[$#elts];
$val = $vals[$#elts];

pop @elts;
pop @vals;

if ($type eq 'SIZE') {
if (defined (%set)) {
%a = %set;
%set = &incdec(-$val);
}
$lim -= $val;
$lim = 1 if 1 > $lim;
} else {
my %divs = &divs($val);
if (defined(%set)) {
%a = %set; %b = %divs;
%set = &intersect($lim);
} else {
%a = %divs; %b = %divs;
%set = &intersect($lim);
}
}
}

if (!defined(%set)) { print "SIZE >= $lim\n"; }
elsif (%set) { print join(' ', keys %set), "\n"; }
else { print "IMPOSSIBLE\n"; }