TEMA

PROBLEM 1027 - URI Fórum 1.0

URI Online Judge preguntado 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Beto Jamaíca respondido 4 years ago

    Apesar do nível e tema, é possível resolver esse problema de forma gulosa com um algoritmo bem simples. O Thalyson já comentou sobre, apenas reforço que poderia ser adicionado o "guloso" ao spoiller desse problema. :)

  • Unknown respondido 4 years ago

    Eu fiz um criador de testes em java pra esse enunciado e me ajudou bastante a achar o erro de WA 10%. Basta rodar e escrever o N números de pontos e o raio que você de quer que x e y atinjam. O ideal é criar uns 2000 casos testes com raio 10 e usar diff(se jogar no google você acha um site que compara 2 textos) pra ver qual teste está diferente do resultado do toolkit.

    public static void main(String[] args) {
            int range,N;
            Random g = new Random();
            Scanner l = new Scanner(System.in);
            N = l.nextInt();
            range = l.nextInt();
            for(int j = 0;j<N;j++){
                System.out.println("10");
                for(int i =0;i<5;i++){
                    System.out.println(g.nextInt(range) + " " + g.nextInt(range));
                    System.out.println(g.nextInt(range) + " " + -g.nextInt(range));
    
                }
            }
            l.close();
        }
    
    }
  • Vinicius Sanches respondido 5 years ago

    Pessoal, estou tentando vários métodos para avaliar esse problema mas não estou conseguindo. Sempre para no WA 10% segue meu código abaixo. Alguém pode me dar uma luz do que pode estar errado? Todos os testes sugeridos aqui e nos exemplos estão executando corretamente. Esse código está pouco elegante pois já estou apelando pra força bruta. Existe alguma regra que eu não tenha visto?

    include include include include include

    using namespace std;

    void combination(vector vect_geral,set union_dominio_superior , set union_dominio_inferior, bool up, int level, int counter_max,int count_temp ) {

    if (level < vect_geral->size() && count_temp+(vect_geral->size()-level) > *counter_max)
    {
    
        for (int i = level; i < vect_geral->size(); i++)
        {
            if (up == true && union_dominio_superior->count(vect_geral->at(i)))
            {
                combination(vect_geral,union_dominio_superior,union_dominio_inferior,false,i+1,counter_max, count_temp+1);
            }
            else
            {
                if(up == false && union_dominio_inferior->count(vect_geral->at(i)))
                {
                    combination(vect_geral,union_dominio_superior,union_dominio_inferior,true,i+1,counter_max, count_temp+1);
                }
            }
        }
    
    }
    else
    {
        if (count_temp > *counter_max) *counter_max = count_temp;
    }

    }

    int main(int argc, char **argv) { for ( ; ; ) { int points ; int max = 0xEFFFFFFF; int min = 0x7FFFFFFF;

        map< short int,set<short int> >point_map_inv; 
    
        short int X, Y;
        if (cin.eof()) break;
        cin >> points;
        //if ( points > 1000 || points == 0) return 0;
        for (int i = 0 ; i < points; i++)
        { 
    
            set<short int> aux_set_inv;
            cin >> X >> Y;
    
            if (point_map_inv.count(Y))
                aux_set_inv = point_map_inv[Y];
    
            aux_set_inv.insert(X);
    
            point_map_inv[Y] = aux_set_inv;
    
            if (max < Y) max = Y;
            if (min > Y) min = Y;
        }
    
        int count_point_max = 0;
        if (min == max || abs(max - min) == 1 || point_map_inv.size() == 1 || points == 1)
            cout << 1 << endl;
        else
        {
            for (int a = min + 1; a < max ; ++a)
            {
                set<short int> union_dominio_geral;
                set<short int> union_dominio_superior;
                set<short int> union_dominio_inferior;
                // superior
                union_dominio_superior.insert(point_map_inv[a+1].begin(),point_map_inv[a+1].end());
                // inferior
                union_dominio_inferior.insert(point_map_inv[a-1].begin(),point_map_inv[a-1].end());
                // uniao 
                union_dominio_geral.insert(point_map_inv[a+1].begin(),point_map_inv[a+1].end());
                union_dominio_geral.insert(point_map_inv[a-1].begin(),point_map_inv[a-1].end());
                vector<short int> vect_geral(union_dominio_geral.begin(),union_dominio_geral.end());
                if (!union_dominio_superior.empty() && !union_dominio_inferior.empty() && union_dominio_geral.size() > count_point_max) // Optimization
                {
                    combination(&vect_geral,&union_dominio_superior,&union_dominio_inferior,false,0,&count_point_max,0);
                    combination(&vect_geral,&union_dominio_superior,&union_dominio_inferior,true,0,&count_point_max,0);
                }
    
            }
    
            cout << count_point_max << endl;
        }
    }
    return 0;

    }

  • Thalyson Nepomuceno respondido 6 years ago

    poderia alterar o assunto dessa questão. Tem que é programação dinâmica, porém fiz um guloso e passou de boa :D

  • Victor Marcilio Peixoto respondido 6 years ago

    @meitcher: então, eu disse que não via outra resposta que não fosse 3... o problema é que um amigo tinha me mandado o código dele e eu usei esse código como toolkit já que o do site tava off... e o código dele imprimiu 4, por isso que achei que tava errado. Mas... já encontrei um erro, não era no algoritmo, era só um incremento de uma variavel que tava bugado ^.-

  • Marcos Treviso respondido 6 years ago

    @nightshade: Perceba que você deve variar o y apenas entre a-1 e a+1. Ou seja, se o y escolhido tiver o valor 2, a curva deve passar pelos pontos x cujo seu respectivo y é 1 ou 3.

    A saída correta para esse caso de teste seria 3. Faça o gráfico com os pontos, assim ficará mais fácil de entender o problema.

    @Lucas Silva: Sim, você pode considerar que os pontos de x devem estar em ordem crescente.

    Valeu!

  • Victor Marcilio Peixoto respondido 6 years ago

    a resposta disso:

    10 5 -1 5 -3 2 0 2 -4 0 3 2 3 4 1 0 -3 5 -2 2 -1

    é pra ser 4?

    única "possível" solução que encontrei seria com os pontos:

    0 -3 2 -1 4 1 5 -1

    mas então quem seria o valor pra reta A?

    tou tomando 10% WA mas eu fiz supondo que só poderiam existir 2 possiveis pros Y dos pontos selecionados (a + 1 e a - 1) e o único par de valores que se repete é (-1, -3), deixando os pontos:

    0 -3 2 -1 5 -3 5 -1 (não é possivel pegar esse pois a coordenada x é igual ao anterior)

    minha resposta pra esse caso seria 3... alguém sabe me dizer o que interpretei errado? (ou em que aspectos o enunciado foi mal formulado?)

  • Lucas Basquerotto da Silva respondido 6 years ago

    Eu gostaria de esclarecer uma dúvida quanto ao que deve ser feito neste problema.

    O programa que eu criei estava dando 5 para a primeira forma de onda (com a = 0), de forma que os pontos seriam p3 -> p1 -> p6 -> p8 -> p10. Eu fiz o programa seguindo as diretrizes dadas em que se diz 'Todos os pontos na curva deverão ter diferentes coordenadas x', mas não diz que os pontos x devem ser sempre crescentes, a partir do início. Entretanto, o que percebi foi que o resultado (que está mostrado na imagem do problema) foi feito com os x sempre maiores em relação ao do ponto anterior.

    O que deduzi foi que ao dizer que é uma forma de onda estaria implícito que os pontos x deveriam ser sempre crescentes. Seria isto?

  • Marcos Treviso respondido 6 years ago

    Teste com os seguintes casos:

    10
    5 0
    2 1
    2 0
    1 4
    1 2
    1 1
    4 -1
    0 1
    4 0
    1 -2
    10
    5 1
    4 1
    0 0
    2 3
    2 1
    3 0
    5 -5
    5 -2
    1 -4
    4 -2
    10
    0 2
    5 -3
    0 0
    1 -1
    0 3
    3 -2
    2 0
    0 -3
    0 3
    0 1
    10
    5 -1
    5 -3
    2 0
    2 -4
    0 3
    2 3
    4 1
    0 -3
    5 -2
    2 -1
    10
    1 0
    1 3
    4 4
    4 -3
    4 -2
    4 2
    5 -4
    3 -2
    0 0
    0 -1

    Pelo que entendi no seu código, você não está levando em consideração que os pontos da coordenada y: a+1 e a-1 podem estar no mesmo x na primeira iteração, quando isso acontece, você tem de testar os dois casos e considerar o que resulta o maior valor.

  • Omar Esteves Duarte Filho respondido 6 years ago

    Olá! Estou quebrando a cabeça aqui. Já testei com vários test cases e acredito que o meu código esteja correto mas, continuo recebendo WA! Alguém consegue enxergar o erro?

    /*
     ============================================================================
     Name        : URI.c
     Author      : Omar Esteves Duarte Filho
     Version     :
     Copyright   : Your copyright notice
     Description : Hello World in C, Ansi-style
     ============================================================================
     */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    #define FALSE                  0
    #define TRUE    1
    
    #define DEBUG
    #ifdef DEBUG
    #define printd(args...)  printf(args)
    #else
    #define printd(args...)   ;
    #endif
    
    typedef struct
    {
        int x;
        int y;
    } STR_TYPE;
    
    STR_TYPE coords[1000];
    
    ///* qsort struct comparison function (product C-string field) */
    //int struct_cmp_avg(const void *a, const void *b)
    //{
    //            int cmp;
    //            STR_TYPE *ia = (STR_TYPE *) a;
    //            STR_TYPE *ib = (STR_TYPE *) b;
    //            cmp = (int) (ia->avg - ib->avg);
    //            return cmp;
    //}
    //
    ///* Example struct array printing function */
    //void print_struct_array(STR_TYPE *array, size_t len)
    //{
    //            size_t i;
    //
    //            for (i = 0; i < len; i++)
    //            {
    //                           printd("%d-%d", array[i].residents, array[i].avg);
    //                           if (i == len-1) printf("\n");
    //                           else printf(" ");
    //            }
    //
    //}
    
    #define MAX_POINTS                                 1000
    #define UP          1
    #define DOWN        0
    #define UNKNOWN     2
    
    /* qsort struct comparison function (product C-string field) */
    int struct_cmp_coordx(const void *a, const void *b)
    {
        int cmp;
        STR_TYPE *ia = (STR_TYPE *) a;
        STR_TYPE *ib = (STR_TYPE *) b;
        cmp = (int) (ia->x - ib->x);
        return cmp;
    }
    
    int count_critical(STR_TYPE *coords, int initial, int N)
    {
        int ymax, ymin;
        int count;
        int dir;
        int psel;
        int i;
    
        count = 0;
    
        ymin = coords[initial].y;
        ymax = coords[initial].y;
    
        dir = UNKNOWN;
    
        psel = initial;
    
        count++;
        printd("\nP%d - INI(%d,%d)", psel + 1, coords[psel].x, coords[psel].y);
        if (N > 1)
        {
            for (i = initial + 1; i < N; i++)
            {
                /* All the points on the curve should have different x coordinates.  */
                if (coords[i].x == coords[psel].x)
                    continue;
    
                /* Two consecutive points on the curve should have a difference of 2 in their y coordinate. */
                if (abs(coords[psel].y - coords[i].y) != 2)
                    continue;
    
                if (dir == UNKNOWN)
                {
                    if (coords[i].y > coords[psel].y)
                        dir = UP;
                    if (coords[i].y < coords[psel].y)
                        dir = DOWN;
                    psel = i;
                }
                else
                    if (dir == UP)
                    {
                        if ((coords[i].y < coords[psel].y))
                        {
                            printd("\nP%d - MAX(%d,%d)", psel + 1, coords[psel].x,
                                    coords[psel].y);
                            count++;
                            dir = DOWN;
                            psel = i;
                        }
                    }
                    else
                        if (dir == DOWN)
                        {
                            if (coords[i].y > coords[psel].y)
                            {
                                printd("\nP%d - MIN(%d,%d)", psel + 1,
                                        coords[psel].x, coords[psel].y);
                                count++;
                                dir = UP;
                                psel = i;
                            }
                        }
            }
            if (i == N)
            {
                printd("\nP%d - END(%d,%d)", psel + 1, coords[psel].x,
                        coords[psel].y);
                count++;
            }
    
        }
    
        return count;
    }
    
    int main(void)
    {
        int N;
        //while (1)
        {
            int i;
            int max_count = 0;
    
            memset(coords, 0, sizeof(coords));
    
            scanf("%d", &N);
    
            for (i = 0; i < N; i++)
            {
                if (EOF == scanf("%d %d", &coords[i].x, &coords[i].y))
                    break;
            }
    
            /* Sort points */
            /* Sort Original input by group */
            //qsort(coords, N, sizeof(STR_TYPE), struct_cmp_coordx);
    
            /* Process */
            for (i = 0; i < N; i++)
            {
                int count;
                count = count_critical(coords, i, N);
    
                if (count > max_count)
                    max_count = count;
                printd("\n\t%2d)TOTAL = %d\n", i, max_count);
    
                if (N - 1 - i < max_count)
                    break;
            }
            //printf("%d\n", max_count);
        }
    
        return EXIT_SUCCESS;
    }
  • Cristhian Bonilha respondido 6 years ago

    O segundo caso dá 3 pois você deve escolher um valor para a e apenas selecionar pontos que intercalam seu valor y em a-1 e a+1.

    No caso, escolheremos a = 0, e a sequência de pontos vai ser: 1 -1 3 1 4 -1

  • Old man respondido 7 years ago

    Entrada:

    10
    0 1
    1 0
    1 -1
    2 -2
    3 1
    3 -1
    3 -2
    4 1
    4 -1
    5 -1
    10
    0 2
    2 0
    1 -1
    2 -2
    3 1
    3 -1
    3 -2
    4 1
    4 -1
    5 –1

    No primeiro caso dá 4 e no segundo dá 3, porém nos meus cálculos deu 4 o segundo caso. Alguém pode me dizer porque dá 3 e não 4?

    Me ajudem no meu código também por favor.

    #include <stdio.h>
    
    main(){
        int n, x, y, i, pontoY;
    
        while(scanf("%d", &n)){
            int sobe=0, desce=0, cont=-1;
            scanf("%d %d", &x, &y);
            pontoY=y;
    
            i=0; while(i<n-1){
                scanf("%d %d", &x, &y);
    
                if(y<=pontoY){
                    desce++;
                    sobe=0;
                    pontoY=y;
                }else if(y>=pontoY){
                    sobe++;
                    desce=0;
                    pontoY=y;
                }
                if(sobe==1 || desce==1){
                    cont++;
                }
            i++;}
            printf("%d\n", cont);
        }
    }