ONI'2013

[polska]

Esta-me a escapar algo.. Como estou a assumir isso? Por calcular a primeira pedra a partir das 3 posições seguintes e não considerar a própria primeira pedra? Eu já tinha lido o input com índices de 1 a N e depois calculava o próprio i=0 que significa a tal posição 0, que é antes da primeira pedra.. Mas o resultado foi o mesmo..

[mogers]

best = pedras[N-1];

Não podes fazer isto porque N pode ser maior que K. Podes evitar estas inicializações e começar o ciclo em N-1 se admitires que em N o melhor é zero.

if(dir[i] > best) best = dir[i];
if(esq[i] > best) best = esq[i];

Idem, pelo mesmo motivo. Deves ver os dir[] e esq[] de 0..K-1.

Se já tinhas tentado calcular a partir de 0, deves ter feito algum bug noutro sitio como a inicialização do best.

[polska]

best = pedras[N-1];

Não podes fazer isto porque N pode ser maior que K. Podes evitar estas inicializações e começar o ciclo em N-1 se admitires que em N o melhor é zero.

if(dir[i] > best) best = dir[i];
if(esq[i] > best) best = esq[i];

Idem, pelo mesmo motivo. Deves ver os dir[] e esq[] de 0..K-1.

Se já tinhas tentado calcular a partir de 0, deves ter feito algum bug noutro sitio como a inicialização do best.

Eu já tinha alterado essas inicializações todas, já as tinha retirado e feito o ciclo a começar em N-1 . Quando testei a própria posição 0, falta mesmo esse caso de testar o best, faltava mesmo apenas testar de 0 a K-1... Agora já deu os 60 pts, obrigado pela ajuda 😉

[JoaoSantos95]

Estou aqui com um problema no exercício B das ONI de 2012:

Enunciado: http://www.dcc.fc.up.pt/oni/problemas/2012/final/probB.html

Meu Código: http://pastebin.com/ebRzU3DV

Dadas as coordenadas inteiras 2D de uma sequência de arranha-céus retangulares, estando a sequência ordenada pela distância crescente em relação ao ponto de onde tiras a foto, a tua tarefa é calcular duas coisas. Primeiro, o número de arranha-céus que são visíveis, ou seja, que aparecem na foto (ainda que apenas parcialmente). Segundo o máximo número de arranha-céus que estão uns atrás dos outros, ou seja, o maior número de edifícios que estão numa mesma posição do quadriculado.

As coordenadas são dadas na forma: X_inicial, X_final, Altura.

Tive Wrong Answer (19 pontos) no exercício, estou aqui a matutar e não consegui descobrir porquê. No entanto, fiquei na ideia que o erro do problema tinha haver com quando os edifícios tinham x_inicial[ j ] = x_final.

Para ter a certeza quanto a isso, alguém me consegue dizer qual seria a resposta para o input:

5

3 5 6

4 4 20

4 6 7

11 12 8

11 13 9

Edited May 2, 2013 at 06:55 PM by JoaoSantos95

[mogers]

Para ter a certeza quanto a isso, alguém me consegue dizer qual seria a resposta para o input:

5

3 5 6

4 4 20

4 6 7

11 12 8

11 13 9

5 3

[mogers]

3

1 5 4

6 10 5

3 8 3

A resposta é 2 2

[JoaoSantos95]

obrigado pela ajuda. Vou resolver o problema relativo ao último output que puseste ; )

[skiller10]

É já amanhã a final. Descansem bem para amanhã darem o vosso melhor. Boa sorte!

[anolsi]

Bom trabalho para todos os finalistas. Espero que desfrutem da final. 🙂

[Pedro Ribeiro]

A final realizou-se ontem, dia 3 de Maio, no DCC/FCUP:

- Classificação da Final

- Problema A: Alice no País dos Primos

- Problema B: Constelação Retangular

- Problema C: Apagando Letras

- Álbum de Fotos

Parabéns a todos os finalistas por lá terem chegado, mas de um modo especial felicito o Afonso Santos, pelo 1º lugar, e o 4 primeiros (Afonso Santos, Pedro Silva, David Gomes e Victor Meriqui) por se terem apurado para representar Portugal nas IOI'2013, em Brisbane (Austrália).

Edited May 4, 2013 at 10:35 AM by Pedro Ribeiro

[SirDave]

Eu gostava de ver uma solução do B com somas acumuladas visto que eu bem tentei mas não consegui.

Parabéns aos outros finalistas e ao professor pelos problemas!

[mogers]

É mais produtivo se explicares o que fizeste exactamente e a parte que não conseguiste fazer.

[polska]

Parabéns a todos, em especial aos 4 primeiros 😉 .

E parabéns também a todos que tornaram possível mais uma realização das ONI 👍 .

[SirDave]

Tens razão, aqui vai:

Eu tinha uma array horizontal[N_LINHAS][N_COLUNAS].

Se a linha 4 fosse do tipo:

. . . . E . E . . E

A array horizontal[4][] ficava assim:

{0, 0, 0, 0, 1, 1, 2, 2, 2, 3}.

Ou seja, somas acumuladas.

Depois, para um certo retângulo a fórmula do impacto seria:

for (i = 0; i < h; i++) // h = altura do quadrado
{
 hor[y + i][x] - hor[y][x - 1] + hor[y][x + largura] - hor[y][x + largura - 1];
}

Depois fazia todos os Xs, todos os Ys, todas as larguras e todas as alturas. Há, ainda, o problema de haver uma estrela no canto do retangulo, que teria de corrigir "à mão". Posso ter tido algum erro lá no DCC mas isso não me estava a dar valores certos, vou tentar resolver outra vez mais tarde, só queria era um mooshaq.

[polska]

Eu pensei em muitas coisas diferentes para resolver o problema, inclusive as somas acomuladas, mas acabei por não conseguir implementar uma solução que respondesse certo.

Depois fazia todos os Xs, todos os Ys, todas as larguras e todas as alturas. Há, ainda, o problema de haver uma estrela no canto do retangulo, que teria de corrigir "à mão". Posso ter tido algum erro lá no DCC mas isso não me estava a dar valores certos, vou tentar resolver outra vez mais tarde, só queria era um mooshaq.

O ano passado os servidores não abriram para a final 2012, não sei se este ano será diferente, mas também gostava que sim.

[mogers]

Tens razão, aqui vai:

Eu tinha uma array horizontal[N_LINHAS][N_COLUNAS].

Se a linha 4 fosse do tipo:

. . . . E . E . . E

A array horizontal[4][] ficava assim:

{0, 0, 0, 0, 1, 1, 2, 2, 2, 3}.

Ou seja, somas acumuladas.

Depois, para um certo retângulo a fórmula do impacto seria:

for (i = 0; i < h; i++) // h = altura do quadrado
{
hor[y + i][x] - hor[y][x - 1] + hor[y][x + largura] - hor[y][x + largura - 1];
}

Depois fazia todos os Xs, todos os Ys, todas as larguras e todas as alturas. Há, ainda, o problema de haver uma estrela no canto do retangulo, que teria de corrigir "à mão". Posso ter tido algum erro lá no DCC mas isso não me estava a dar valores certos, vou tentar resolver outra vez mais tarde, só queria era um mooshaq.

Na formula tens 3 valores em y, deviam ser 2 em y e 2 em y+i

Usa variaveis temporarias para os cantos - o código fica mais facil de ler. Assumindo que o canto inferior é (x,y) e o superior (x+largura-1, y+i-1), devia ser

hor[y+i][x + largura - 1] - hor[y+i][x-1] + hor[y][x + largura - 1] - hor[y][x-1];

Muito mais legivel se escreveres

x2 = x + largura - 1

y2 = y + i

impacto = hor[y2][x2] - hor[y2][x-1] + hor[y][x2] - hor[y][x-1];

Faltam é os valores da vertical

Edit: Eu usei as somas acumuladas dessa forma. No entanto, também poderias usar da forma comum. o valor do perimetro é o valor das estrelas nesse quadrado menos o valor da soma do quadrado interior

Edited May 5, 2013 at 01:13 PM by mogers

[SirDave]

Mas a minha ideia é só guardar horizontais e fazer um loop por todas as "linhas" horizontais do retângulo e assim não precisava de guardar valores verticais.

No entanto, também poderias usar da forma comum. o valor do perimetro é o valor das estrelas nesse quadrado menos o valor da soma do quadrado interior

Esse era o meu objetivo, era um somas acumuladas "geral" como no Max Sum (que é com a área em vez do perímetro), mas não me lembrei dessa ideia, é fixe.

Edited May 5, 2013 at 02:59 PM by thoga31
Adição das tags QUOTE com a referência apropriada

[mogers]

Mesmo assim continuam a faltar os +i da linha actual que estás a processar. No entanto, acaba por ser desnecessario dentro do ciclo porque só estás a adicionar 2 pontos (mat[y+i][x] e mat[y+i][x+largura-1]).