beecrowd perguntou on mai. 1 2013

URI Online Judge Fórum 1.0

MOD

Este tópico foi resolvido e não pode receber novas respostas.

• 

  +5

  mmendes2 respondido 9 years ago

  Esse problema é bem parecido com o "Bubbles and Buckets".

  No Bubbles eu consegui passar na primeira com o Shell Sort, mas no fórum todo mundo dizia q dava pra passar em O(n) sem utilizar nenhum algoritmo de ordenação. Mudei a solução e passei.

  Como a sequencia é uma permutação de números 1..N então cada numero na sequencia ordenada deve ficar na posição correspondente ao seu numero. Ex: Índices: 1 2 3 4 sequencia: 1 2 3 4

  O numero 1 fica na pos 1, o 2 na pos 2 e assim por diante. Na sequencia não haverá nenhum numero além de N. Agora é só contar quantas trocas foram feitas para chegar na sequencia ordenada.

• 

  +3

  jbsilva respondido on mai. 2 2013

  Este problema é bem parecido com o "Bubbles and Buckets", "Train Swapping" e "Start Grid", mas as trocas não precisam ser entre elementos consecutivos.

  Recebi TLE com o selection sort O(n^2).

  Edit: Dica: consegui resolver em O(n) fazendo uma modificação no selection sort, que leva em consideração que eu já conheço a sequência ordenada.

• 

  0

  vvillar respondido 7 years ago

  Por que meu código não funciona? Podem me ajudar?

  #include <cstdlib>
  #include <iostream>
  #include <stdio.h>
  #include <algorithm>
  using namespace std;
  
  int selection_sort(int num[], int tam) 
  { 
    int i, j, min, aux, r = 0;
    for (i = 0; i < (tam-1); i++) 
     {
      min = i;
      for (j = (i+1); j < tam; j++) {
        if(num[j] < num[min]) 
          min = j;
      }
      if (i != min) {
        aux = num[i];
        num[i] = num[min];
        num[min] = aux;
      }
      r++
    }
    return r;
  }
  
  int main(int argc, char** argv) {
  
      int i, j, n, nn;
      int vet[10000];
  
      scanf("%d", &n);
  
      while(n--){
          scanf("%d", &nn);
          for(j = 0; j < nn; j++){
              scanf("%d", &vet[j]);
          }
          i = selection_sort(vet, j);
          printf("%d\n", j);
      }
      return 0;
  }

• 

  0

  rsantana4 respondido 8 years ago

  public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(
                  new InputStreamReader(System.in));
          int testCases = Integer.parseInt(br.readLine());
          for (int i = 0; i < testCases; i++) {
              br.readLine();
              String[] list = br.readLine().split(" ");
              iterations = 0;
              quickSort(list, 0, list.length - 1);
              System.out.println(iterations);
          }
      }
  
      private static void quickSort(String[] list, int low, int high) {
          if (low < high) {
              int mid = partition(list, low, high);
              quickSort(list, low, mid - 1);
              quickSort(list, mid + 1, high);
          }
      }
  
      private static int partition(String[] list, int low, int high) {
          String pivot = list[low];
          int pivotInt = Integer.parseInt(pivot);
          do {
              while (low < high && Integer.parseInt(list[high]) >= pivotInt) {
                  high--;
              }
             if (low < high) {
                  list[low] = list[high];
                  iterations++;
                  while (low < high && Integer.parseInt(list[low]) <= pivotInt) {
                      low++;
                  }
                  if (low < high) {
                      list[high] = list[low];
                      iterations++;
                  }
              }
          } while (low < high);
  
          list[low] = pivot;
          return low;
      }
  }

  Estou recebendo WA 100%.

  Testei alguns casos e notei que meu código falha para a seguinte entrada:

  1
  8
  6 8 7 1 2 3 4 5

  Saída esperada (toolkit):

  6

  Retorno do meu código:

  8

  Porém não sei como solucionar. Alguém tem alguma ideia?

• 

  0

  rsantos5 respondido 8 years ago

  Caso de Teste:

  1 10 2 3 4 9 8 7 1 6 5 10

  saída: 8

  Se a saída for igual, possívelmente estará tudo bem com sua solução.

• 

  0

  dcpietropaolo respondido 9 years ago

  #include <stdio.h>
  
  int main (){
      int a, b, c[100000], f, e;
  
          scanf ("%d", &a);
          for (int g=0; g<a; g++){
              scanf ("%d", &f) ;
              e=0;
              for (b=0; b<f; b++){
                  scanf ("%d", &c[b]);
  
                  if (c[b]-b-1>0)
                      e=c[b]-b-1+e;
                  else
                          e=(-1)*(c[b]-b-1)+e;
              }
  
          printf ("%d\n", e/2);
      }
  }

  WA 100% Disponibilizem + casos de teste!!!!

• 

  0

  dcpietropaolo respondido 9 years ago

  Casos de teste?

  #include <stdio.h>
  
  int shellSort(int *vet, int size) {
      int i , j , value, u=0;
      int gap = 1;
      while(gap < size) {
          gap = 3*gap+1;
      }
      while ( gap > 1) {
          gap /= 3;
          for(i = gap; i < size; i++) {
              value = vet[i];
              j = i - gap;
              while (j >= 0 && value < vet[j]) {
                  vet [j + gap] = vet[j];
                  j -= gap;
                  u++;
              }
              vet [j + gap] = value;
  
          }
      }
      return u;
  }
  int main (){
      int a, b, c[100000], f, e;
  
          scanf ("%d", &a);
          for (int g=0; g<a; g++){
              scanf ("%d", &f) ;
              for (b=0; b<f; b++){
                  scanf ("%d", &c[b]);
              }
          e=shellSort (c, f);
          printf ("%d\n", e);
      }
  }

  Meu codigo ta 100% WA

• 

  0

  cvinicius1 respondido 9 years ago

  Meu código foi o seguinte:

  #include <iostream>
  #include <stdio.h>
  
  #define MAXN 10005
  
  using namespace std;
  
  long long int merge_count(int A[], int esq, int meio, int dir){
      int B[MAXN];
  
      for(int i = esq; i <= meio; i++) B[i] = A[i];
      for(int j = meio+1; j <= dir; j++) B[dir+meio+1-j] = A[j];
  
      int i = esq, j = dir;
      long long int qtde = 0;
      for(int k = esq; k <= dir; k++){
          if(B[i] <= B[j])
              A[k] = B[i++];
          else{
              A[k] = B[j--];
              qtde += (meio-i+1);
          }
      }
      return qtde;
  }
  
  long long int sort_count(int A[], int esq, int dir){
      if(esq >= dir) return 0;
      int meio = (esq+dir)/2;
      return sort_count(A,esq,meio) + sort_count(A,meio+1,dir) + merge_count(A,esq,meio,dir);
  }
  
  int main(){
      int t, n, v[MAXN];
  
      scanf("%d", &t);
      while(t--){
          scanf("%d", &n);
          for(int i = 0; i < n; i++)
              scanf("%d", &v[i]);
          printf("%lld\n", sort_count(v,0,n-1));
      }
  
      return 0;
  }

  Não sei porque, mas apesar de funcionar em todos os meus testes, estou recebendo Wrong Answer 100% com esse código.

  Detalhe: utilizei o mesmo algoritmo em outros problemas semelhantes e funcionou perfeitamente.

• 

  0

  jbsilva respondido 9 years ago

  Eu acredito que deveria funcionar sim. Talvez na sua implementação alguma conta a mais é feita.

• 

  0

  cvinicius1 respondido 9 years ago

  Por que contar as inversões através do merge sort não funciona nesse problema?

  Eu utilizei um código semelhante ao disponível no seguinte site -> http://marathoncode.blogspot.com.br/201 ... rsoes.html