(SPOJ) 11631 - Número de Envelopes - Solução Java

Esta solução não passa no SPOJ devido ao limite de tempo, mas as respostas estão corretas.
Para tentar diminuir o tempo, lê-se a 2ª linha de entrada como se esta fosse uma string e posteriormente cada número é lido a partir da string.

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }
   
    static int leitor(BufferedReader br) throws NumberFormatException, IOException {
        int n;
        int resp = 0;
        
        while (true) {
            n = br.read();
            if (n >= '0' && n <= '9')
                break;
        }
        while (true) {
            resp = resp*10 + n-'0';
            n = br.read();
            if (n < '0' || n > '9')
                break;
        }
        
        return resp;
    }
   
    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int qteRotulos = leitor(br);
        int tiposBalas = leitor(br);

        //char[] ibuf = new char[qteRotulos];
        String ibuf = "";
        ibuf = br.readLine();

        int[] balas = new int[tiposBalas];
       
        int tamBuf = ibuf.length();
        int i = 0;
        int lidos = 0;
        while (lidos < qteRotulos) {
            Integer indice = 0;
            String indiceTmp = "";
            while (i < tamBuf && ibuf.charAt(i)-'0' != -16) {
                //indice = indice*10 + (ibuf.charAt(i)-'0');
                indiceTmp += ibuf.charAt(i);
                i++;
            }
            lidos++; // vai pro proximo numero
            i++; // vai pro seguinte ao espaço
            indice = Integer.parseInt(indiceTmp);
            balas[indice-1] += 1;
        }
       
        int menor = 1000000;
        for (i = 0; i < tiposBalas; i++) {
            if (balas[i] < menor) {
                menor = balas[i];
            }
        }

        bw.write(menor+"\n");   
        bw.flush();
        bw.close();
                               
        return;
    }
}

Comments

  1. Essa aqui passa no SPOJ com o tempo de 1.39

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;

    public class NumeroEnvelopes {

    public static void main(String[] args) {

    try (BufferedReader input = new BufferedReader(new InputStreamReader(System.in))) {

    int firstIteration = 0;

    int numberTypes = 0;

    int[] types = null;

    while (input.ready()) {

    if (firstIteration == 0) {

    StringTokenizer stringReader1 = new StringTokenizer(input.readLine());

    stringReader1.nextToken();// skip not used first information
    numberTypes = Integer.parseInt(stringReader1.nextToken());

    firstIteration = 1;

    } else {
    types = new int[numberTypes];

    StringTokenizer stringReader2 = new StringTokenizer(input.readLine());

    while (stringReader2.hasMoreTokens()) {
    types[(Integer.parseInt(stringReader2.nextToken()) - 1)] += 1;
    }

    }
    }

    int menor = Integer.MAX_VALUE;
    for (int i = 0; i < numberTypes; i++) {
    if (types[i] < menor) {
    menor = types[i];
    }
    }

    System.out.println(menor);

    } catch (Throwable e) {
    e.printStackTrace();
    }
    }

    }

    ReplyDelete
    Replies
    1. Oi, Bruno.

      Legal! Tentei submeter novamente minha solucao para ver se nao tinham mudado o tempo limite desde a ultima vez que tentei, mas realmente ainda da tempo limite excedido. Pelo que vi, apenas sua solucao e a de mais uma pessoa passaram para Java :)

      Delete
    2. Simplifiquei o codigo e agora ele passa:

      import java.io.*;
      import java.util.*;

      class Main {
      public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      int qteRotulos = leitor(br);
      int tiposBalas = leitor(br);

      int[] balas = new int[tiposBalas];

      for (int i = 0; i < qteRotulos; i++) {
      balas[leitor(br)-1]++;
      }

      int menor = 1000000;
      for (int i = 0; i < tiposBalas; i++) {
      if (balas[i] < menor) {
      menor = balas[i];
      }
      }

      System.out.println(menor);

      System.exit(0);
      }

      private static int leitor(BufferedReader br) throws NumberFormatException, IOException {
      int n;
      int resp = 0;

      while (true) {
      n = br.read();
      if (n >= '0' && n <= '9')
      break;
      }
      while (true) {
      resp = resp*10 + n-'0';
      n = br.read();
      if (n < '0' || n > '9')
      break;
      }

      return resp;
      }
      }

      Delete

Post a Comment

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução