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