TÓPICO
PROBLEM 1520 - URI Fórum 1.0
Este tópico foi resolvido e não pode receber novas respostas.
-
crbonilha respondido on mar. 9 2014
Encontrei um erro, quando o número procurado é o último da lista.
1 1 5 5
-
crbonilha respondido on mar. 4 2014
Há várias maneiras de se abordar este exercício. Vou citar uma que imagino ser a mais direta.
Crie um vetor, com zero elementos dentro dele. Para cada uma das N linhas que representam os lotes, adicione a esse vetor os valores que compõem o lote. Por exemplo, sejam os lotes (1, 3) e (2, 5), o seu vetor conterá os seguintes elementos: 1, 2, 3, 2, 3, 4, 5.
vetor[tam++] = aux; // para adicionar o valor aux dentro do vetor // tam aqui detona quantos elementos há dentro do vetor
Após isso, ordene os elementos dentro do vetor.
#include <algorithm> ... std::sort(vetor, vetor+tam);
E por fim encontre onde fica a primeira e última aparição de Num dentro desse vetor, se é que ele se encontra lá.
-
compiledge respondido 9 years ago
Pessoal, obtive um Wrong answer 80%. Já testei com alguns casos e não encontrei o erro:
/*Exercício Resolvido.*/
-
oman10 respondido on mar. 8 2014
Alguém tem algum caso de teste interessante desse exercício, pois estou com Wrong answer (10%) e não consigo finalizar. Help pls.
-
Icaro-Lima respondido 7 years ago
10% W.A Oque poderia ser?
#include <cstdio> #include <set> using namespace std; int main() { int n, a, b, c; multiset<int>::iterator first, last; multiset<int> mult; while (scanf("%d", &n) != EOF) { for (; n > 0; n--) { scanf("%d%d", &a, &b); for (int i = a; i <= b; i++) { mult.emplace(i); } } scanf("%d", &c); first = mult.lower_bound(c); last = mult.upper_bound(c); if (first == mult.end()) { printf("%d not found\n", c); } else { printf("%d found from %d to %d\n", c, distance(mult.begin(), first), distance(mult.begin(), last) - 1); } mult.clear(); } return 0; }
-
pfelipe1 respondido 8 years ago
Talvez nem precise usar busca binária por causa dos limites da entrada, mas vamos supor que os limites da entrada sejam muito altos, você não poderia usar uma busca linear.
Você está usando c++, sugiro pesquisar na biblioteca algorithm as funções lower bound e upper bound.
-
jdamasio0 respondido 8 years ago
Mais um WA 100% com outro código, se qualquer pessoa puder revisar, agradeço.
while True : try : resp = [] n = input() for i in range(n) : ini, fim = map(int, raw_input().split()) for j in range(ini, fim+1) : resp.append(j) resp.sort() num = input() if num in resp : ini = resp.index(num) soma = 1 for j in range(ini+1, len(resp)) : if resp[j] == num : soma += 1 else : break print "%d found from %d to %d" % (num, ini, ini + soma - 1) else : print "%d not found" % num except : break
-
jdamasio0 respondido 9 years ago
Velhos, se alguém puder me achar um caso de erro ficarei tão agradecido que sou capaz até de comprar um ovo de páscoa. Agradeço desde já. =)
while True : try : resp = [0 for i in range(101)] n = input() for i in range(n) : ini, fim = map(int, raw_input().split(' ')) for j in range(ini, fim+1) : resp[j] += 1 num = input() if resp[num] != 0 : soma = 0 for j in range(num) : soma += resp[j] print "%d found from %d to %d" % (num, soma, soma + resp[num] - 1) else : print "%d not found" % num except : break
-
dcpietropaolo respondido 9 years ago
#include <stdio.h> #include <string.h> int main (){ int a, b, mr, c, h, j, som, mir, k, e, d[101]; for (b=0; b<101; b++){ d[b]=0; } while (scanf ("%d", &a)!=EOF){ som=0; mir=0; for (j=0; j<a; j++){ scanf ("%d %d", &c, &b); if (mir<b){ mir=b; } for (e=c; e<=b; e++){ d[e]++; } } scanf ("%d", &h); for (k=0; k<h; k++){ som=d[k]+som; } if (d[h]==0){ printf ("%d not found\n", h); } else{ if (h==mir){ som++; } printf ("%d found from %d to %d\n", h, som++, som+d[h]-1); } for (int oi=0; oi<mir; oi++){ d[oi]=0; } } }
WA 10%
-
phfleite respondido 9 years ago
Alguem teve problemas com o toolkit deste exercicio? Nem o teste do site esta funcionando.
-
phfleite respondido 9 years ago
Alguém pode ajudar, informa que o código está 100% errado, entretanto tentei diversos casos de testes e em todos o algoritmo passou =X
#include <stdio.h> #include <stdlib.h> typedef struct No_{ int dado; struct No_ *prox; }No; typedef struct Lista_{ No *ini; }Lista; void new(Lista *l) { l -> ini = NULL; } void insereOrd(Lista *l, int v) { No *novo, *ant, *p; novo = malloc(sizeof(No)); novo -> dado = v; ant = NULL; p = l -> ini; while (p != NULL && v > p -> dado){ ant = p; p = p -> prox; } if (ant == NULL) { novo -> prox = l -> ini; l -> ini = novo; } else { novo -> prox = p; ant -> prox = novo; } } int removeIni(Lista *l) { No *p; if (l -> ini != NULL) { p = l -> ini; l -> ini = l -> ini -> prox; } return p -> dado; } int vazia(Lista *l) { if(l -> ini == NULL) return 0; else return 1; } int tam(Lista *l) { No *aux; int tam=0; aux = l -> ini; while (aux != NULL) { tam++; aux = aux -> prox; } return tam; } int main() { int n, x, y, num, aux; Lista l; new(&l); while(scanf("%d", &n) != EOF) { if(n>100 || n<1) return -1; while(n>0) { scanf("%d%d", &x, &y); if(x<0 || x >=y || y >100) return -1; for(; x<=y; x++) insereOrd(&l, x); n--; } if(tam(&l) > 10000) return 0; scanf("%d", &num); if(num<0 || num>100) return -1; n=0, y=0, aux=0; while(vazia(&l)!=0) { x = removeIni(&l); if(num == x && y==0) { printf("%d found from %d", num, n); y++; } else if(num == x) aux = n; n++; } if(y==0) printf("%d not found", num); else if(aux>0) printf(" to %d", aux); printf("\n"); } return 0; }
-
Joe101 respondido 9 years ago
usei um vector em c++ e deu certo passou com 2 ... mas é pq não usei busca binária mas td bem já recebi aceito lá tá de boa
-
Joe101 respondido 9 years ago
tem que usar busca binária pra resolve isso ? Pq aloquei em uma lista fiz pesquisa em uma lista .. depois não deu por time limit ... peguei e coloquei em vetor e até usei o quick sort pra ordena e tals timelimit ... nessa minha lógica tem que ser uma busca binária pra passa ?? pq batem TODAS as saidas com as do toolkit ...
#include <iostream> #include <algorithm> #include <stdlib.h> #include <stdio.h> using namespace std; struct lista { int v; struct lista *prox; }; struct lista *insere(struct lista *ini,int v){ struct lista *aux; aux = (struct lista * )malloc(sizeof(struct lista)); aux->v = v; aux->prox = NULL; if(ini==NULL){ ini = aux; }else{ struct lista *ult = ini; while(ult->prox!=NULL){ ult=ult->prox; }ult->prox = aux; aux->prox=NULL; } return ini; } int contaBloc(struct lista *ini){ struct lista *aux = ini; int cont=0; while(aux!=NULL){ //printf("%d -> ",aux->v); cont++; aux = aux->prox; } return cont; } void retornaBlocosEmVetor(struct lista *ini,int valorbuscado){ struct lista *aux = ini; int cont=0,t; int cont2 = contaBloc(ini); int cont3=0; int flag=0; int vet[cont2]; while(aux!=NULL){ //printf("%d -> ",aux->v); vet[cont] = aux->v; cont++; aux = aux->prox; } sort(vet,vet+cont2); for(t=0;t<cont2;t++){ if(vet[t]==valorbuscado){ cont3++; } //printf("%d ",vet[t]); } if(cont3>0){ flag=1; } //printf("\n"); int vetor[cont3],v=0; for(t=0;t<cont2;t++){ if(vet[t]==valorbuscado){ vetor[v] = t; //printf("%d ",vetor[v]); v++; } } if(flag==1) printf("%d found from %d to %d",valorbuscado,vetor[0],vetor[cont3-1]); if(flag==0){ printf("%d not found",valorbuscado); } } /*void mostra(struct lista *ini){ struct lista *aux = ini; while(aux!=NULL){ printf("%d -> ",aux->v); aux = aux->prox; } } */ /*void pesquisa(struct lista *ini,int v){ int flag=0; int cont=0; int cont2=0; int cont3=0; int i; struct lista *aux = ini; struct lista *aux2 = ini; while(aux2!=NULL){ cont3++; aux2 = aux2->prox; } int vet[cont3]; /// array pra guardar as posições necessárias for(i=0;i<cont3;i++){ vet[i] = 0; } while(aux!=NULL){ if(aux->v==v){ vet[cont] = cont; flag=1; } aux = aux->prox; cont++; } int cont5=0; for(i=0;i<cont3;i++){ if(vet[i]!=0){ cont5++; // printf("%d ",vet[i]); } } int vetaux[cont5]; int cont6=0; for(i=0;i<cont3;i++){ if(vet[i]!=0){ vetaux[cont6] = i; cont6++; } } //printf("%d posicoes sao diferentes de zero %d\n",cont5); //printf("\n"); if(flag==1) printf("%d found from %d to %d",v,vetaux[0],vetaux[cont5-1]); if(flag==0){ printf("%d not found",v); } } */ int main() { struct lista *ini = NULL; int testes,j; int valor1 , valor2,i,cont=0,valorBuscado; while(scanf("%d",&testes)!=EOF){ for(j=0;j<testes;j++){ scanf("%d",&valor1); scanf("%d",&valor2); for(i=valor1;i<=valor2;i++) ini = insere(ini,i); } scanf("%d",&valorBuscado); retornaBlocosEmVetor(ini,valorBuscado); //mostra(ini); //pesquisa(ini,valorBuscado); printf("\n"); ini = NULL; } return 0; }
-
aluiz1 respondido 9 years ago
Gostaria de mais casos de teste,pois estou recebendo 10% de erro,mas não sei por onde =/
//============================================================================ // Name : treinocpp.cpp // Author : andinho // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n,num; int x,y; while (cin >> n){ int bla[10000]; int aux=0; for (int i=0;i<n;i++){ cin >> x >> y; for (int i2=x;i2<=y;i2++){ bla[aux++]=i2; } } cin >> num; sort(bla,bla+aux); // int xx = distance(bla, find(bla, bla + aux, 4)); int v=-1; int inicio = -1; int fim = -1; bool isSegundaVez = false; for (int i=0;i<aux;i++){ if (bla[i]==num){ v=i; inicio = i; break; } } for (int i=aux-1;i>0;i--){ if (bla[i]==num){ v=i; fim = v; break; } } if (v != -1) cout << num << " found from " << inicio << " to " << fim << endl; else cout << num << " not found" << endl; } return 0; }
-
oman10 respondido on mar. 8 2014
olha o código ai:
Resolvido depois da dica do Cristhian.
Testes efetuados: Entrada:
3 1 3 2 4 3 5 4 4 1 3 2 4 1 5 3 6 3 2 1 3 3 5 7 4 1 2 1 2 1 2 1 2 1
Saída:
4 found from 6 to 7 3 found from 5 to 8 7 not found 1 found from 0 to 3
Retorna Wrong answer (10%), não consigo achar o erro, alguém pode ajudar?
-
jsdsilveira respondido on mar. 4 2014
1520 por favor, alguém pode me dar uma dica de como começo este exercício?