TEMA

PROBLEM 1590 - 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.

  • Cristhian Bonilha respondido 6 years ago

    Dica: Tentem construir a resposta a partir do zero. Comecem pelos bits importantes (de maior valor, mais à esquerda). É possível que tal bit esteja presente na resposta final?

  • Beto Jamaíca respondido 5 years ago

    10%WA, alguém consegue identificar um caso de teste que falha ou algo o pq do wa? :\

    #include <bits/stdc++.h>
    using namespace std;
    
    int main (void){
        long long count, ans, e, i, j, k, t, n, v[40];
    
        scanf ("%lld", &t);
        while (t--){
            scanf ("%lld%lld", &n, &k);
            for (i = 0; i < n; i++){
                scanf ("%lld", &v[i]);
            }
            sort(v,v+n,greater<int>());
            ans = 0;
            for (i = 31; i >= 0; i--){
                e = -1;
                for (j = count = 0; j < n; j++)
                {
                    if ((v[j]>>i)&1 == 1) 
                    {
                        e == -1 ? e = v[j] : e &= v[j];
                        count ++;
                        //printf("e=%d count=%d\n",e,count);
                        if (count >= k)
                            ans = max(e,ans);
                    }               
                }
            }
            printf ("%lld\n", ans);
        }
        return 0;
    }
  • Unknown respondido 6 years ago

    Alguém saberia me apontar o erro no código. Estou recebendo Wrong Answer 100%.

    #include <stdio.h>
    
    int main(){
        int k,t, n,size,i,j,s,maxlength,length,inuse[1000],p;
        char aux[1000],nums[100][100];
        int u,ans;
        scanf("%d",&t);
        for (; t > 0; t--){
            scanf("%d%d",&n,&k);
            j = maxlength = 0;
    
    /*Leitura dos dados. O vetor nums[i] contém o i-ésimo número escrito da direita para esquerda
    na representação binária. A variável maxlength é igual ao número de dígitos do maior dos n números.*/
    
            for (i = 0; i < n; i++){
                scanf("%d", &u);
                length = 0;
                s = 0;
                if (u == 0){
                    nums[j][0] = '0';
                    length = 1;
                }
                while (u > 0){
                    aux[s++] = u%2+'0';
                    u/=2;
                    length++;
                }if (length > maxlength)maxlength = length-1;
                for (p=s; p <30; p++)
                    nums[j][p] = '0';
                s--;
                while (s >= 0) nums[j][s] = aux[s--];
                j++;
            }
            for (i = 0; i < n;i++)inuse[i] = i;
            p = n;
            ans = 0;
            int cont;
    
    /*Algoritmo para resolver o problema. O array inuse contém a posição de todos os números que
    poderão levar a resposta final (ans)*/
    
            for (i = maxlength; i >= 0; i--){
                cont = 0;
                for (j = 0; j < p; j++){
                    if (nums[inuse[j]][i] == '1')aux[cont++] = inuse[j];
                }
                if (cont >= k){
                    p = 0;
                    ans = ans * 2 + 1;
                    while (cont > 0){
                        inuse[p] = aux[p++];
                        cont--;
                    }
                }
                else ans*=2;
            }printf("%d\n",ans);
        }
    }
  • teste876 respondido 6 years ago

    Alguém pode liberar mais casos de teste? O toolkit não está funcionando...

  • Carlos Vinícius respondido 6 years ago

    Obrigado pela dica Cristhian. Accepted :)

  • Carlos Vinícius respondido 6 years ago

    Alguém poderia me passar alguns casos de teste? Estou recebendo WA.

  • Gabriel Duarte respondido 6 years ago

    Alguma dica ? Tentei permutar os números e a cada permutação pego os k's primeiros números e vejo se o AND deles é maior do que eu já tinha, mas TLE.

    MOD