TEMA

PROBLEM 1912 - URI Fórum 1.0

URI Online Judge preguntado 5 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • mpineda respondido 4 years ago

    Hello, try this case: input: 2 3 4 4 0 0

    output:

    2.5000

  • Lais Karsburg respondido 4 years ago

    Está dando 10% de erro. Alguém sabe em que caso pode ser?

    #include <stdio.h>
    #include <stdlib.h>
    #define ERRO 0.00001
    
    float buscaBinaria(int area, int tira[], int n, float inicio, float fim) {
        int i;
        float corte = (fim + inicio) / 2.0, areaCorte = 0;
        for(i = 0; i < n; i++) {
            if((float)tira[i] > corte) {
                areaCorte += ((float)tira[i] - corte);
            }
        }
        if(fim - inicio < ERRO) {
            return corte;
        } else if(areaCorte > (float)area) {
            return buscaBinaria(area, tira, n, corte, fim);
        } else {
            return buscaBinaria(area, tira, n, inicio, corte);
        }
    }
    
    int main(void) {
        int a, n, i, areaTira;
        int tira[100000];
        float h, maior = 0;
        scanf("%d %d", &n, &a);
        while(n != 0 && a != 0) {
            areaTira = 0;
            for(i = 0; i < n; i++) {
                scanf("%d", &tira[i]);
                areaTira += tira[i];
                if((float)tira[i] > maior) {
                    maior = (float)tira[i];
                }
            }
    
            if(areaTira == a) {
                printf(":D\n");
            } else if(areaTira < a) {
                printf("-.-\n");
            } else {
                h = buscaBinaria(a, tira, n, 0.0, maior);
                printf("%.4f\n", h);
            }
            scanf("%d %d", &n, &a);
        }
        return 0;
    }
  • Daniel Saad respondido 5 years ago

    Pra passar este problema precisei fazer um ajuste fino nos valores do EPS e da quantidade de iterações máximas da busca binária.

    Dependendo do valor de EPS que você escolher ele dará wrong answer. Um bom valor é 0.0001.

  • Douglas Diniz Carvalho respondido 4 years ago

    Estou tomando um TLE de 4 segundos! Nunca tomei um TLE tão grande numa busca binária, desconfio que seja a forma de ordenação feita (não conheço muito o c++). Alguém sabe qual seria a melhor forma de otimizar essa ordenação decrescente dos valores?

    #include <bits/stdc++.h>
    
    using namespace std;
    
    float busca_binaria(float tiras[], int tamanho, float valor_busca){
        float minimo = 0;
        float maximo = tiras[0];
        float meio, tiras_cortadas;
    
        do{
            meio = (minimo+maximo)/2;
            tiras_cortadas = 0;
    
            for(int i=0; (i < tamanho) && (tiras[i] > meio) && (tiras_cortadas <= valor_busca); i++){
                tiras_cortadas += tiras[i]-meio;
            }
    
            if(tiras_cortadas < valor_busca){
                maximo = meio;
            }else if(tiras_cortadas > valor_busca){
                minimo = meio;  
            }   
        }while(tiras_cortadas != valor_busca);
    
        return meio;
    }
    
    int main(){
        #ifndef ONLINE_JUDGE
            freopen("input.txt", "r", stdin);
        #endif
    
        int N, A, soma;
    
        while((cin >> N >> A) && ((N != 0) && (A != 0))){
            float tiras[N];
            soma = 0;
    
            for(int i=0; i < N; i++){
                cin >> tiras[i];
                soma += tiras[i];
            }
    
            if(soma < A){
                printf("-.-\n");
            }else if(soma == A){
                printf(":D\n"); 
            }else{
                sort(tiras, tiras + N, greater<float>()); // Ordem decrescente
                printf("%.4f\n", busca_binaria(tiras, N, A));
            }
        }
    
        return 0;
    }
  • teste876 respondido 5 years ago

    Estou recebendo 10% WA. Alguém sabe me dizer algum caso de teste onde este código não passa??

    #include <bits/stdc++.h>
    using namespace std;
    double soma_area(double h, vector<double> &vet){
        double soma= 0.0;
        for(int i=0;i<(int)vet.size();i++){
            if(vet[i]>h){
                soma += vet[i]-h;
            }   
        }
        return soma;
    }
    
    int main() {
        int n,a;
        while(scanf("%d %d",&n,&a) && n && a){
            vector<double> vet(n);
            double soma = 0,hmax = 0;
            for(int i=0;i<n;i++){
                scanf("%lf",&vet[i]);
                soma += vet[i];
                hmax = max(hmax,vet[i]);
            }
    
            double area_total = soma_area(0,vet);
            if(area_total == a) {
                printf(":D\n");
                continue;   
            }else if(area_total < a){
                printf("-.-\n");
                continue;
            }else{
                double a1 = 0;
                double b1 = hmax;
                double meio = 0;
                while( b1 - a1 >= 0.00001){
                    meio = (b1+a1)/2.;
                    double res = soma_area(meio,vet); 
                    if(res > a) {
                        a1 = meio;
                    } else if(res < a){
                        b1 = meio;
                    } else break;
                }
                printf("%.4lf\n",b1);       
            }
    
        }
        return 0;
    }
  • Gabriel Duarte respondido 5 years ago

    Eu tinha pensado nisso, mas não dá muito certo, não consigo encontrar nenhum exemplo onde não há resposta e caia em um loop infinito. Todas os exemplos que eu penso onde não há resposta caem na condição que coloquei.

    if(soma < a)
    {
          printf("-.-\n");
         continue;
    }

    Existe algum caso que quebre esse if ?

    EDIT: Não existe, na verdade eu estava usando o valor para o EPS muito pequeno e com isso dava TLE, nem tinha me ligado nisso, o valor foi 1e-4

    MOD
  • Ahmed ali Abotaleb respondido 5 years ago

    Cuidado com a condição de parada, pode acontecer dela nunca ser aceita e seu programa ficar em loop infinito. O que tu pode fazer é determinar um número máximo de iterações para a busca binária.

  • Gabriel Duarte respondido 5 years ago

    Existe alguma sacada nesse problema ? Implementei uma Busca binária e fica dando TLE Alguem pode dar uma dica ?

    ACC
    MOD
  • Thiago Magalhaes respondido 5 years ago

    Mesmo usando Busca Binaria está dando TLE :/

    #include <stdio.h>
    #include <stdlib.h>
    
    double tiras (int *t, double p, double r, double a, double n);
    
    int main(){
    
      int i, t[100000], nn;
      double n, a, soma = 0, maior = 0;
    
      while(scanf("%lf %lf", &n, &a) && n != 0) {
        soma = maior = 0;
        nn = (int) n;
    
        for (i = 0; i < nn; i++) {
          scanf("%d", &t[i]);
          if (i == 0 || maior < t[i])
            maior = t[i];
          soma += t[i];
        }
    
        if (soma == a)
          printf(":D\n");
        else
        if (soma < a)
          printf("-.-\n");
        else
          printf("%.4lf\n", tiras(t, 0, maior, a, n));
    
      }
    
    }
    
    double tiras (int *t, double p, double r, double a, double n) {
      int i;
      double corte, soma = 0;
    
      corte = (r + p) / 2.0;
      for (i = 0; i < n; i++)
        if (corte < t[i])
          soma += t[i] - corte;
    
      if (soma == a)
        return corte;
    
      if (soma > a)
        return tiras(t, corte, r, a, n);
      else
        return tiras(t, p, corte, a, n);
    
    }
  • Kelvin Angelus respondido 5 years ago

    Hum. Ok, Dâmi Henrique. Obrigado pela ajuda. Não conheço busca binária nem estrutura de dados. Tenho que dar um estudada antes rsrs e depois tentarei novamente. Obrigado mesmo já deu o caminho das pedras.

  • Dâmi Henrique respondido 5 years ago

    Opa..

    Você está codando uma solução O(N^2), e como N máximo é 10^5, sua solução se torna lenta demais...

    É possível resolver com uma complexidade bem melhor utilizando uma busca binária... Você basicamente chuta o valor do corte, e dependendo da soma das áreas, decide se seu chute foi alto ou baixo demais.. Repetindo o processo até que a área resultante seja igual o bastante.

  • Kelvin Angelus respondido 5 years ago

    Boa noite, pessoal. Alguém pode dar uma força neste problema? recebo TLE.

    #include<iostream>
    using namespace std;
    
    void quicksort(int *items, int len);
    void qs (int *items, int left,int right);
    
    int main(){
    
        int A, N, k, n, a, i, j = 0,soma = 0, somai, vet[100000],vet2[100000];
        float H = 0.0000,t = 0.0000;
        cin>>N>>A;
    
        do{
    
        somai = 0;  
        for (a = 0;a < N ;a++){
            cin>>vet[a]; somai = somai + vet[a];
        }
        if (somai == A)
            cout<<":D"<<'\n';
        else if(somai < A)
            cout<<"-.-"<<'\n';
        else{
            quicksort(vet,a);
            i = 0; j = 0; n = 0;
            while(i < N){
                while (j < N){
                    soma = soma + vet[j] - n;
                    j++;
                }
            n = vet[i];
            vet2[i] = soma;
            i++; j = i; soma = 0;
            }
            i = N - 1; soma = 0;
            t = 1;
            while (vet2[i] <= A){
                soma = soma + vet[i];
                i--; t++;
            }
            soma = soma + vet[i];
            H = (soma - A)/t;
            std::cout.precision(4);
            std::cout.setf( std::ios::fixed, std:: ios::floatfield );
            std::cout<<H<<'\n';
            }
        cin>>N>>A;
        } while (N || A);
    
    return 0;
    }
    
    void quicksort(int *items, int len){
    
        qs(items, 0, len - 1);
    }
    
    void qs(int *items, int left, int right){
    
        int i, j, x, y;
    
        i = left; j = right; x = items[(left + right)/2];
    
        do{
            while ((items[i] < x) && (i < right)) i++;
            while ((x < items[j]) && (j > left)) j--;
    
            if(i <= j){
                y = items[i];
                items[i] = items[j];
                items[j] = y;
                i++; j--;
            }
        }while (i <= j);
    
        if (left < j) qs (items, left, j);
        if (i < right) qs (items,i,right);
    }