Ex A - ONI 2010

[polska]

Boas pessoal, estive a resolver este exercício das ONI de 2010 e gostava que me ajudassem a melhora-lo:

http://www.dcc.fc.up.pt/oni/problemas/2010/final/probA.html

Eu conssegui 40pts nesse exercício, a minha solução era guardar os Q numeros num array e depois de usar um for de 1 até 1 000 000 que me verificasse se o i era um numero possivel, se fosse contava até chegar ao numero guardado no array ..

Por exemplo, o primeiro num do aray é 4, logo quando o for chegasse ao 4 numero possivel, fazia printf e saía do for...

Que solução devo explorar para consseguir 100pts?

[skiller10]

Vê se isto te ajuda 🙂

http://www.dcc.fc.up.pt/oni/problemas/2010/final/discussao/solA.html

[polska]

Vê se isto te ajuda 🙂

http://www.dcc.fc.up...ussao/solA.html

Estava mesmo a ver isso agora, lembrei-me de ver se havia discussão para as edições anteriores xD ..

Ajudar ajuda, daí a fazer 😄 ... Eu por acaso pensei que consseguiria melhorar o problema fazendo uma ordenação dos Q valores, depois confirmar que é verdade já me deixou feliz ahahahah, vamos lá ver se faço o resto ..

Uma pergunta, quando requer uma ordenação, se eu usar 2 for para ordenar o vector em vez de um algoritmo tipo quick sort, vou perder eficiencia no programa?

[skiller10]

muita mesmo.

Os 2 for (buble sort) tem uma complexidade de O(N^2) em que N é o número de elementos enquanto que o sort da STL, o Merge Sort e o Heap Sorte tem uma complexidade de O(N x log(N)) inclusivé no pior caso. O Quick Sort tem um caso médio de O(N x log(N)) mas o pior caso é O(N^2).

Acho que devias estudar pelo menos o Quick Sort e o Merge Sort e aprender a usar o sort da STL 🙂

[polska]

muita mesmo.

Os 2 for (buble sort) tem uma complexidade de O(N^2) em que N é o número de elementos enquanto que o sort da STL, o Merge Sort e o Heap Sorte tem uma complexidade de O(N x log(N)) inclusivé no pior caso. O Quick Sort tem um caso médio de O(N x log(N)) mas o pior caso é O(N^2).

Acho que devias estudar pelo menos o Quick Sort e o Merge Sort e aprender a usar o sort da STL 🙂

Vamos a isso ;D

Thanks 👍

[mogers]

Acho que devias estudar pelo menos o Quick Sort e o Merge Sort e aprender a usar o sort da STL 🙂

Subscrevo!

O Quick Sort tem um caso médio de O(N x log(N)) mas o pior caso é O(N^2).

A título de curiosidade, na minha primeira entrevista na Google tive de explicar porque é que o pior caso é O(N^2), descrever métodos que são usados para tentar reduzir a probabilidade do worst case acontecer e comparar esses métodos.

Consegues responder a isso? 🙂 Penso que é interessante, não só pelo quick sort mas também por outras situações em que podem ser úteis

[polska]

O meu primeiro programa passava por verificar qual é o numero a cada pedido, ou seja, o pedido é 7, vou percorrer o for de 1 ate 100000 até encontrar o 7 numero com x vezes o A ... de seguida é 4, vou voltar ao for até ser o 4 numero com x vezes o A... Esta solução deu-me 40 pontos.. Vou postar o código:

#include <stdio.h>
int main(){
int nums[1000],A,C,Q,conta,contax,num;
scanf("%d %d",&A,&C);
scanf("%d",&Q);
for(int i=0;i<Q;i++){
 scanf("%d",&nums[i]);
}
for(int i=0;i<Q;i++){
 conta=0;contax=0;
 for(int j=1;j<1000000;j++){
  num=j;
  if(j<10){
do{
 if(num%10==A)
  contax++;
 num=num/10;
}while(num/10!=0);
  }else{
do{
 if(num%10==A)
  contax++;
 num=num/10;
}while(num/10!=0);
if(num%10==A)
 contax++;
  }
  if(contax==C)
conta++;
  if(conta==nums[i]){
printf("%d: %d\n",nums[i],j);
break;
  }
 }
}
return 0;
}

Depois tentei os 60 pontos, assim também vejo as várias técnicas que se pode usar, e então lá dizia que o for so precisa de ser percorrido uma vez, isto se os pedidos estiverem ordenados. Então usei o merge sort para ordenar os pedidos, mas deixei outro vector com os pedidos pela ordem original também.. Depois verifiquei qual o maior pedido que existe, para isso bastou ir buscar o Q-1 ao vector ordenado, e fiz um for de 1 ate 1000000 que guardava todos os numeros com x vezes o A até este ser o pedido maior necessário, ou seja, o maior pedido é 7, então ia guardando os numeros até ser o 7º numero que obdece á condição..

Depois bastou fazer um for que mostrasse o vector dos numeros guardados...

Achei estranho pois ao enviar a solução, baixou de 40 para 36 e mostrou RunTime error .. 😕

Código:

#include <stdio.h>
#define MAX 1000
unsigned long int v[MAX],v1[MAX],ordem[MAX],nums[MAX];
void mergesort(int begin, int end){
int left = 0, right = 0, middle = 0;
int i = 0;
if(begin == end)
 return;
middle = (begin + end)/2;
mergesort(begin,middle);
mergesort(middle + 1,end);
left = begin;
right = middle + 1;
for(i = begin;i <= end;i++)
{
 if(right > end || (left <= middle && v[left] <= v[right]))
 {
  v1[i] = v[left];
  left++;
 }
 else
 {
  v1[i] = v[right];
  right++;
 }
}
for(i = begin;i <= end;i++)
 v[i] = v1[i];
}
int main(){
unsigned long int A,C,Q,contax,num;
bool sair=false;
scanf("%d %d",&A,&C);
scanf("%d",&Q);
for(int i=0;i<Q;i++){
  scanf("%d",&v[i]);
  ordem[i]=v[i];
}
mergesort(0,Q-1);
int j=0;
for(int i=1;i<1000000;i++){
 //renicia variaveis necessarias
 contax=0;sair=false;
 num=i;
 //divide o i e conta quantos A existem
 do{
  if(num%10==A)
contax++;
  num=num/10;
  if(num==0)
sair=true;
 }while(!sair);

 //se houver C A's , guarda o i
 if(contax==C){
  nums[j]=i;
  j++;
 }
 //se tiver chegado ao ultimo pedido necessario (maior pedido), sai do for
 if(j==v1[Q-1]){
  break;
 }
}
for(int i=0;i<Q;i++){
 printf("%d: %d\n",ordem[i],nums[ordem[i]-1]);
}
return 0;
}

Edited May 23, 2012 at 01:53 PM by polska