Recent Forum Posts
From categories:
page 1123...next »

eu usei u e v para encontrar a direção do vetor que liga os pontos mais proximos das retas, eu e o cassius bolamos essa solução,
quando você faz a multiplicacão de u e v você tem um vetor perpendicular ao plano que contem esses dois vetores, dando a direção do vetor, para calcular a distancia, eu fiz assim:

criei dois planos paralelos (\lambda u + \sigma v) que passam pelas retas. a distancia entre esses dois planos é o modulo do vetor que eu quero.
deixando os dois planos na forma: ax+by+cz = d, temos d1 e d2, a distancia dos dois planos é: |d1-d2|/(sqrt(a²+b²+c²)) (lembrando que se os planos são paralelos, a1 = a2, b1 = …)

by gustpggustpg, 14 Aug 2009 20:06

Hum, acho que isso tá errado.

As retas P1 e P2 não dependem do módulo de v e u (pode se usar quaisquer vetores paralelos a u e v). E certamente a representação usadas para as retas não pode afetar a distância entre elas, mas do seu jeito isso afeta, subtituiuir u por 2*u e v por 2*v, aumenta a suposta distância.

Re: by sacomotosacomoto, 14 Aug 2009 18:50

Não entendi… esse produto vetorial dá a direção do que?

Re: by gabrielrcpgabrielrcp, 14 Aug 2009 17:53

estava tentando fazer de outra maneira, mas o resultado não dava certo…
eu usei as retas como

(1)
\begin{align} P_{1} = A + \lambda \vec{v} \end{align}
(2)
\begin{align} $P_{2} = B + \sigma \vec{u}$ \end{align}

fiz o produto vetorial de

(3)
\begin{align} \vec{v} x \vec{u} \end{align}

e encontrei a direção, depois era só resolver um sistema e dividir o vetor pela metade. o modulo é algebrera. Alguém conseguiu fazer assim?

by gustpggustpg, 14 Aug 2009 17:45

Depois de responder aí emcima, eu comecei a pensar um pouco na minha solução, e vi que ela está errada!
Pra quem passou, qual a resposta do programa de vocês pra essa entrada?

13 13
*************
*...........*
*.****.****.*
*.*********.*
*.****.****.*
*.*********.*
*.*********.*
*.*********.*
*.*********.*
*.*********.*
*.*********.*
*...........*
*************

As duas peças tem 1 buraco apenas, sendo que a de dentro tem área 79 enquanto que a de fora tem área 48, assim a resposta devia ser 48 (já que há empate, a de menor área ganha).
Mas o meu programa acha que a peça de dentro tem 2 buracos, então responde 79.

Mais um problema com entradas fracas…

Chalenge! by gabrielrcpgabrielrcp, 03 Aug 2009 05:13

É, agora que eu reli, o enunciado dele tá bem confuso mesmo… eu considerei só as verticais/horizontais sempre.

Se mesa for só isso que você colocou, esse 'a' não é um buraco para o meu programa (já que os '*' não são de uma mesma peça). Mas se ele for de um caso desse: (por exemplo)
*****
*..*..*
**a**
*..*..*
*****

Então é um buraco sim, do mesmo jeito que os outros pontos daí também são buracos diferentes (tem 5 buracos nessa peça).

Re: Clarification by gabrielrcpgabrielrcp, 03 Aug 2009 01:26

The hole is a 4-connected area of '.'s completely surrounded with '*'s.

O que ele quer dizer por completamente cercado, tem que estar cercado somente somente nas direcoes verticais e horizontais (caso em que o 'a' não é um buraco) ou tem que estar cercado nas diagonais também?

.*.
*a*
.*.

Clarification by sacomotosacomoto, 02 Aug 2009 19:27

Alguma idéia para resolver esse?
O Joel comentou que a idéia que ele usou era parecida com a do elastico, mas eu também não sei como resolver aquele.

Dicas? by gabrielrcpgabrielrcp, 29 Jul 2009 23:59

Era esse mesmo o problema, mudei pra long long e passou. Nem tinha reparado nisso, valeu!

Re: Formato da Saida by sacomotosacomoto, 27 Jul 2009 07:40

Passei aqui usando o algoritmo mais ingênuo, busca binária com bellman-ford (não a versão FIFO), sem gambiarra nenhuma.

Só alguns detalhes, eu não construi a matriz de adjacências, isso é meio óbvio mas, no bellman-ford uma lista de arestas é o suficiente. E na busca binária comecei com 0 e custo máximo (positivo) das arestas.

Acho que eu vou fazer a análise desse problema.

Busca binária sem gambiarra by sacomotosacomoto, 27 Jul 2009 07:07

Eu calculei 2x a área e imprimio a parte inteira desse número sobre 2. Depois imprimo um ".5" se for ímpar.

Você ta usando long long? (os limites podem estourar um int)

Re: Formato da Saida by gabrielrcpgabrielrcp, 26 Jul 2009 22:45

Só tomo WA, mas no TJU eu consegui AC.

Como é que você estão escrevendo a saída? A área é sempre um inteiro ou um inteiro mais 0.5 (pq os vértices são inteiros), no primeiro caso eu imprimo um inteiro e no segundo um float com precisão de uma casa decimal (%0.1f).

Formato da Saida by sacomotosacomoto, 26 Jul 2009 22:03

Perdi um tempo debuggando o meu código, vou colocar o caso de testes que eu usei pra achar o problema aqui, talvez ajude quem for debuggar também.

Entrada
2 3
1 1 1
1 1 2
2 3
1 1 1
1 2 1
3 5
1 1 1
1 2 1
1 2 2
4 6
4 1 6
2 2 5
1 4 4
3 3 3
0 0

Saida
25
25
121
165

Alguns casos de teste by sacomotosacomoto, 26 Jul 2009 21:09
sacomotosacomoto 24 Jul 2009 20:15
in discussion Hidden / Per page discussions » PKU 1633 - Gladiators

Interessante, os números definidos por esta recorrência, são 'quase' os números eulerianos do segundo tipo. A única diferença é a segunda restrição sobre a sequência. E assim como os números eulerianos tenho quase certeza que essa sequência tem uma fórmula fechada.

by sacomotosacomoto, 24 Jul 2009 20:15

Beleza, entendi.
Valeu!

by gabrielrcpgabrielrcp, 19 Jul 2009 21:37

Essa codificação não forma uma árvore de huffman válida. Cada nó de uma arvore de huffman ou é uma folha ou tem 'n' filhos.

Ops… não vi que já tinham respondido.

by sacomotosacomoto, 19 Jul 2009 20:57
AtolAtol 19 Jul 2009 20:54
in discussion Hidden / Per page discussions » PKU 1261 - Huffman Trees

"(i.e., each node is either a leaf or has exactly two sub-nodes)"

Nesse caso, a sua árvore ficaria com um nó interno com um único filho, o que não é permitido. ( O vértice representado pelo caminho "11" ).

by AtolAtol, 19 Jul 2009 20:54

Eu não sei se eu entendi esse prob…
No enunciado ele diz que não haverão casos com duas respostas. Mas o segundo caso do exemplo não pode ter essa resposta?

0->00
1->01
2->110
3->10
Clarification by gabrielrcpgabrielrcp, 19 Jul 2009 20:21

Nâo, é uma programação dinâmica. Suponha que seu grafo seja fortemente conexo, e seja s um vértice qualquer dele.
Vamos denotar por $d^k(j)$ o menor custo de um passeio de comprimento exatamente k de s até j. $d^k(j)$ pode ser calculado pela recorrência ($c_{ij}$ é o custo do arco ij):

(1)
\begin{align} d^k(j) = \begin{cases} 0 & \mbox{se } j = s \mbox{ e } k = 0 \\ + \infty & \mbox{se } j \neq s \mbox{ e } k = 0 \\ \min_{ij \in A} \left\{ d^{k-1}(i) + c_{ij} \right\} & \mbox{c.c.}\\ \end{cases} \end{align}

Daí entra a "mágica", o custo médio mínimo de um ciclo é dado por:

(2)
\begin{align} \min_{i \in V} \max_{1 \leq k \leq n-1} \frac{d^n(i) - d^k(i)}{n - k} \end{align}

Onde n é o número de vértices do grafo (ou da componente fortemente conexa que estamos considerando). Mas eu não sei se eu entendi exatamente porque isso funciona, ainda to pensando a respeiro…

Re: by gabrielrcpgabrielrcp, 16 Jul 2009 06:16
AtolAtol 15 Jul 2009 20:40
in discussion Hidden / Per page discussions » PKU 2949 - Word Rings

Como é esse segundo algoritmo? é baseado em busca binária + bellman-ford tambem?

Eu implementei usando vectors para lista de adjacencia, talvez isso tenha ficado um pouco mais lento, tambem. Mas sei lá. meu código tem muita gambiarra…

Oq quer dizer que ele confirma que é minimo dos máximos?

by AtolAtol, 15 Jul 2009 20:40
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License