(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;
}
}
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;
}
}
Essa aqui passa no SPOJ com o tempo de 1.39
ReplyDeleteimport 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();
}
}
}
Oi, Bruno.
DeleteLegal! 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 :)
Simplifiquei o codigo e agora ele passa:
Deleteimport 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;
}
}