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

[spamsink]

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

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

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

Comments

[spamsink]

После нескольких минут фигения от этих задачек я понял, что по крайней мере конкретно задача G про гида и группу паломников - простая как мычание, и может быть спрограммирована минут за 20, и поразительные (относительно остальных) результаты российских команд объясняются тем, что у них математическая подготовка лучше. Как и часто в ЧГК, мастерство заключается в умении отбросить мишуру, облекающую простую математическую задачку (своякоподобный вопрос) в программистскую (ЧГКшную) форму, быстренько решить ее, как положено математикам, а потом быстренько запрограммировать (подогнать ответ под пуант).

[ex-java-duk.livejournal.com]

Я только не понимаю, какое отношение это все имеет к ПРОГРАММИРОВАНИЮ.
Математика - это хорошо, и даже прекрасно, ты же знаешь, я всегда за, но тем не менее....

[spamsink]

Чтобы оно в конце концов работало, программировать тоже надо уметь. Как, в таком случае, ты себе представляешь программистский конкурс?

[ex-java-duk.livejournal.com]

Ой, не знаю :) Наверное - собрать толпу программеров, поставить много пива, и победителем будет тот, кто сумеет больше всех выпить и после этого суметь с одной попытки набрать find / -name \* -exec sudo rm -rf {} \;

[spamsink]

Вот всегда так - чуть что, так сразу речь о пиве, и программистов с сисадминами путают.
Чемпионат по сисадминству, наверное, выглядел бы примерно так, как ты сказал, а вот по программированию...

[theraphim.livejournal.com]

А спрограммируй?

[spamsink]

Программировать лень, я на пальцах могу рассказать.

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

[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"; }