O problema

Um cenário do fim do mundo está descrito por três números em uma única linha, n, m, e p. A seguir a essa linha estão as nlinhas com mvalores por linha. Cada valor representa o total de unidades de água que cada célula pode conter.

As plinhas a seguir descrevem o clima para os próximos pdias. 1 unidade de chuva cai em uma única célula por dia. Se a quantidade de água em uma célula exceder a quantidade que ela pode reter, ela inundará. Se várias células adjacentes estiverem em plena capacidade, elas serão tratadas como uma célula que compartilha vizinhos comuns (pense no Campo Minado quando você clicar em um grupo de espaços em branco).

• Uma única célula do meio tem 4 vizinhos
• Duas células do meio adjacentes, com capacidade total, são tratadas como uma célula que possui 6 vizinhos
• Uma célula de canto único tem 2 vizinhos
• Uma célula de parede única possui 3 vizinhos

Quando uma célula é inundada, ocorre um evento de inundação. Todo o excesso de água é distribuído igualmente aos seus vizinhos. Se isso fizer com que um ou mais vizinhos sejam inundados, outro evento de inundação ocorrerá. Isso continua até que a água se estabilize ou a cidade fique completamente inundada.

Exemplo de entrada

7 5 3
3 2 3 4 5
2 2 0 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3

• 0 0 significa que choveu na linha 1, col 1
• 1 2 significa que choveu na linha 2, coluna 3 (que pode reter água zero e inundar imediatamente!)

Após pdias de chuva, se a cidade estiver completamente inundada, produza Sink . Caso contrário, saída Swim .

Saída de exemplo

Nadar

Suposições

• A entrada pode ser fornecida através do stdin, lida em "city.txt" ou aceita como argumento. Todos os três são permitidos para não invalidar nenhuma resposta já publicada.
• As capacidades de água serão números inteiros não negativos.

Mais de 40 equipes de estudantes universitários de graduação (de A&M, UT, LSU, Rice, Baylor etc.) competindo em um concurso de programação com uma variedade de idiomas disponíveis não conseguiram resolver esse problema em 5 horas. Por causa disso, não posso deixar de mencionar que há um problema nesse quebra-cabeça que torna a solução trivial. O código mais curto ainda vence, porque tenho certeza de que o código mais curto também resolverá o quebra-cabeça.

Golfscript, 37 30 caracteres

Novo e aprimorado, graças a PeterTaylor por dicas:

~](\(@*\(@@<{+}*>"SwimSink"4/=

Explicação :

Code                     -                                            - Stack
~]                       - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
@                        - bring array out                            - 3 35 []
<                        - take first 35 elements out of array.
                           this extracts just the capacities and 
                           consumes the rest                          - 3 []
{+}*                     - fold the array using plus - this sums the
                           entire thing                               - 3 86
<                        - greater-than comparison: 3 > 86?           - 0
"SwimSink"4/             - push a string and split it to groups of 4  - 0 ["Swim" "Sink"]

=                        - index into the array using the result of
                           the comparison. if rain > capacity, then
                           sink, else swim                            - "Swim"

O programa então termina, produzindo a pilha.

Versão antiga + explicação:

[~](\(@*\(@{\(@\-}*\;0>"Sink""Swim"if

Mesma abordagem que Fors , apenas Golfscripted =). Provavelmente pode se tornar mais eficiente. A entrada é de stdin.

Explicação :

Code                     -                                            - Stack
[~]                      - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
{                        - define a block which...
 \(@                     - brings next number out
 \-                      - swaps and subtracts 2nd down from top
}                                                                     - [] 3 35 {}
*                        - repeat that block 35 times. this ends up
                           pulling the capacities out one by one
                           and decrementing our number-of-days 
                           number by each one                         - [] -84 
\;                       - swap and kill the array to get rid of
                           unused input                               - -84
0>"Sink""Swim"if         - if the num > 0, evaluate to "Sink", 
                           otherwise to "Swim"                        - "Swim"

O programa gera a pilha, que é apenas a resposta.

C: 100 96 95 caracteres

n,m;main(p){scanf("%d%d%d",&n,&m,&p);for(n*=m;n--;scanf("%d",&m))p-=m;puts(p>0?"Sink":"Swim");}

Cinco horas? Levei cinco minutos. :)

Aragaer, obrigado pelas simplificações! No entanto, reorganizei as declarações e argumentos da variável para main, visto que Clang lança um erro se o segundo argumento para main for de outro tipo que não o char **.

Python, 4 linhas, 175 caracteres

import sys 
F=sys.stdin
n,m,p=[int(a) for a in F.readline().split()]
print("sink") if p > sum([sum(int(x) for x in F.readline().split()) for a in range(n)]) else print("swim")

Lol, eu me pergunto se as mais de 40 equipes acabaram encontrando o problema ... depois de trabalhar da maneira mais difícil.

Recurso duplo J (50 caracteres) e K (40)

Acontece que, como sempre, esses dois têm exatamente a mesma estrutura em suas soluções, portanto, ambos estão aqui. K é muito mais curto, porém, o que é uma surpresa agradável.

>Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1

Explicação:

• ".1!:1]1 - Leia na primeira linha e converta para números inteiros.
• (...)/0 2{- Pegue os itens no índice 0 e 2 ( ne prespectivamente) e use-os como argumentos esquerdo e direito para o verbo (...), respectivamente.
• +1!:1@#1:- Leia em n+plinhas.
• [+/@".@$- Pegue ( $) as primeiras nlinhas ( [), descartando o restante, depois converta para números inteiros ( ".) e some em cada linha ( +/).
• ]<[:+/- Adicione as somas da linha e compare esse valor com o argumento correto p. Produzimos true se pfor menor que a soma.
• >Sink`Swim{~- Selecione Swimse a compra acima resultou em verdadeiro ou Sinkfalso.

Uso:

   >Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1
7 5 3
3 2 3 4 5
2 0 3 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
Swim

E agora o K:

`Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`

Explicado:

• . 0:` - Leia uma linha de entrada e converta para uma matriz de números inteiros.
• {...}.- Use esses três números n m pcomo argumentos x y zpara esta função.
• 0::'(x+z)#`- Crie x+zcópias do identificador do arquivo de entrada `e leia em uma linha para cada um deles ( 0::').
• .:'x#- Pegue os primeiros xitens e converta cada um em um vetor de números.
• z<+//- Soma a matriz inteira e teste para ver se é maior que z.
• `Sink`Swim@- Retorne Sinkou de Swimacordo com o retorno do teste verdadeiro.

Uso:

  `Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`
7 5 3
3 2 3 4 5
2 2 0 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
`Swim

APL, 35

4↑'SwimSink'⌽⍨4×x[3]>+/{+/⎕}¨⍳1⌷x←⎕

Não tenho certeza se permitido, mas ele deixa de aceitar entradas após a "cidade"

x←⎕Recebe entrada e armazena-a em variável x(números delimitados por espaço são interpretados como uma matriz numérica)
1⌷Extrair índice 1 (matrizes APL são baseadas em uma)
⍳Gere uma matriz de 1 até o argumento ( 1⌷x←⎕neste caso)
¨operação "Map"
{+/⎕}Retire a matriz de insira e retorne a soma
+/Soma a matriz gerada pela operação do mapa
4×x[3]>Teste se a soma < x[3](retorna 1 ou 0) e multiplique 4
'SwimSink'⌽⍨Gire a string 'SwimSink'por esse valor
4↑Finalmente, extraia os 4 primeiros caracteres da string

AWK, 70

n{for(;NF;NF--)s+=$NF;n--}NR==1{n=$1;p=$3}END{print p<s?"Swim":"Sink"}

Esta é uma violação de laindir na minha submissão (86):

NR==1{h=$1;w=$2;r=$3;next}NR<=h{for(i=1;i<=w;++i)c+=$i}END{print(c>r?"Swim":"Sink")}

CoffeeScript - 128 113

Uma função que aceita a string como o único argumento:

s=(l)->l=l.split /\n/;[n,m,p]=l[x=0].split /\s/;x+=c|0 for c in r.split /\s/ for r in l[1..n];`p>x?"Sink":"Swim"`

SED, 128

Foi divertido escrever uma sedversão disso. Tem as seguintes deficiências:

• Assume que a cidade possui mais de duas colunas, para reconhecer facilmente as linhas de chuva.

• Assume que a capacidade de cada cidade esteja no intervalo de 0 a 9.

Aqui está:

1d
s/^. .$/R/
G
:a
s/[\n 0]//
/[2-9]/{s/^/C/
y/23456789/12345678/}
s/1/C/
s/0//
s/RC//
h
ta
${s/R//g
s/^Sink//
s/.*C$/Swim/
p}

Ligue com a -nbandeira.

SWI-Prolog 79

Se você não se importa com o fato de que esta resposta recebe entrada por consulta, em vez de via stdin:

s(A,L):-append(A,B),sumlist(B,C),length(L,D),(D>C->E='Sink';E='Swim'),print(E).

A resposta não valida o formato de entrada, mas não acho que seja um problema, pois o concurso de programação também não exige que você faça isso.

Consulta de amostra (usando o exemplo na pergunta):

s([[3,2,3,4,5],
   [2,2,0,3,4],
   [1,1,2,3,3],
   [4,1,2,2,2],
   [4,1,1,2,2],
   [4,4,1,2,2],
   [4,4,2,2,2]],
  [(0,0),
   (1,2),
   (4,3)]).

Python - 152

import numpy
n, m, p = map(int,raw_input('').split())
print 'swim' if p<numpy.sum(numpy.matrix(';'.join([raw_input('') for i in range(n)]))) else 'sink'

Scala - 128

val a=readLine.split(' ')map(_.toInt);println(if((1 to a(0)map(x=>readLine.split(' ')map(_.toInt)sum)sum)>a(2))"swim"else"sink")

Pode ser possível omitir alguns parênteses ou algo assim, mas Scala é realmente inconstante sobre pontuação e estilo sem pontos e () vs {} e outros enfeites.

Javascript - 73 caracteres

for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

Assume que a entrada está na variável se gera Swimou Sink.

Exemplo:

Da pergunta original - inserindo isso no console do navegador:

s="7 5 3\n3 2 3 4 5\n2 2 0 3 4\n1 1 2 3 3\n4 1 2 2 2\n4 1 1 2 2\n4 4 1 2 2\n4 4 2 2 2\n0 0\n1 2\n4 3";
for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

Saídas:

Swim