TOPIC
PROBLEM 1912 - URI Fórum 1.0
This topic was solved and cannot recieve new replies.
-
lkarsburg replied 7 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; } -
danielsaad replied 8 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.
-
DouglasDCarvalho replied 7 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 replied 8 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; } -
gduarte replied 8 years ago
MODEu 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
-
aaabotaleb replied 8 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.
-
tmagalhaes0 replied 8 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); } -
kelvinangelus replied 8 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.
-
DamiHenrique replied 8 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.
-
kelvinangelus replied 8 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); }
