TEMA

PROBLEM 1366 - URI Fórum 1.0

URI Online Judge preguntado 7 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Marco Antônio de Almeida Fernandes respondido 5 years ago

    O que há de errado ? wrong answer 60%

    #include<stdio.h>
    #include<stdlib.h>
    
    int main()
    {
        int N, var, i, j;
        int ci[10000], vi[1000];
    
        do
        {
            var = 0;
            scanf("%d", &N);
            if(N == 0)
                break;
            for(i =0;i < N; i++)
            {
                scanf("%d %d", &ci[i], &vi[i]);
                if(vi[i] >= 4)
                {
                    var += vi[i]/4;
                    vi[i] -= ((vi[i]/4)*4);
                }
                else
                {
                    for(j =0; j < i;j++)
                    {
                        if(vi[i] >=2 && vi[j]>=2)
                        {
                            var+=1;
                            vi[i]-=2;
                            vi[j]-=2;
                        }
                        else if((ci[i] == ci[j]))
                        {
                            if((vi[j]==3 && vi[i] == 1) || (vi[j] == 1 && vi[i] == 3))
                            {
                                var++;
                                vi[j] = vi[i] = 0;
                            }
                        }
                    }
                }
            }
            printf("%d\n", var);
    
        }while(N != 0);
        return 0;
    }
  • Jonathan Queiroz respondido 7 years ago

    Estritamente falando, é possível pegar quatro varetas de uma mesma linha também (um quadrado é um retângulo).

    Mas a sua ideia está certa: você precisa separar dois pares de varetas para formar um retângulo, cada par composto por varetas de mesmo comprimento. No entanto, ir formando os retângulos um a um deve dar TLE. Tente otimizar a forma de contar os retângulos. Dica: esqueça os retângulos inicialmente, pense apenas nos pares de varetas.

  • anderson luiz respondido 7 years ago

    Da maneira que estou entendendo,eu teria que pegar 2 sticks de uma linha e 2 de outra para formar o retangulo. Por exemplo,tem um caso de teste dado assim:

    4 50 2 40 2 30 4 60 4

    Então, eu pegaria 2 de 50 e 2 de 40. Aí formaria um retângulo. Como não haveria mais sticks de 40 e 50,então partiria para os próximos e assim por diante,estou certo? Ou estou abordando a questão de uma maneira ineficiente?

  • Jonathan Queiroz respondido 7 years ago

    algobob, tente pensar na condição para que um retângulo seja formado. O que é necessário para que isso aconteça?

  • anderson luiz respondido 7 years ago

    dicas? xD