Problemas de Programação

Link to the problem: http://br.spoj.com/problems/PROIBIDO/ The solution below keeps the forbidden numbers in a structure (HashSet). Then, for every query, we only need to check if the structure contains the numbers. As we are using a HashSet, this operation costs only O(1). import java.io.*; import java.util.*; class Main {     public static long reader(BufferedReader br) throws NumberFormatException, IOException {              long n;         long 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;          }         public void process() throws NumberFormatEx

Link to the problem: http://br.spoj.com/problems/OLIMP09/ This is another problem where we only need to sort a structure. import java.io.*; import java.util.*; class Main {     public static int reader(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;          }         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new

Link to the problem: http://br.spoj.com/problems/TIMES1/ We only need to sort the students according to their level of ability in the game. Then, we distribute each student in a team. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         String line = br.readLine();         String[] s = line.split(" ");         int numStudents = Integer.parseInt(s[0]);         int numTeams = Integer.parseInt(s[1]);         Abilitie[] abilities = new Abilitie[numStudents];         for (int i = 0; i < numStudents; i++) {             line = br.readLine();             s = line.split(" ");             abilities[i] = new Abilitie(s[0], Integer.parseInt(s[1]));         }         br.close();         Arrays.sort(abilities);                 ArrayLi

Link to the problem: http://br.spoj.com/problems/SUPERMER/ The solution below uses the concept of median to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int numCase = 0;         String line = br.readLine();         String[] s = line.split(" ");         int numMarkets = Integer.parseInt(s[0]);         while (numMarkets != 0) {             int[] arrayX = new int[numMarkets];             int[] arrayY = new int[numMarkets];             for (int i = 0; i < numMarkets; i++) {                 line = br.readLine();                 s = line.split(" ");                 arrayX[i] = Integer.parseInt(s[0]);                 arrayY[i] = Integer.parseInt(s[1]);             }             Arrays.sort(arrayX);             Arrays.sort(arrayY);                         int x = 0;             int y

Link to the problem: http://br.spoj.com/problems/MITO09/ For this problem, we only need to check if a position in the matrix is mentioned more than one time. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String line = br.readLine();         int numRegisters = Integer.parseInt(line);                 boolean notTrue = false;         int[][] matrix = new int[501][501];         for (int i = 0; i < numRegisters; i++) {             line = br.readLine();             String[] s = line.split(" ");             int row = Integer.parseInt(s[0]);             int col = Integer.parseInt(s[1]);             if (matrix[row][col] == 1) {                 notTrue = true;                 break;             }             matrix[row][col] = 1;         }         br.close();                 if (notTrue) {             System.out.pri

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=422 The solution below uses a modified version of the Longest Increasing Sequence (LIS). import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 ArrayList<Feature> numbers = new ArrayList<>();         String line = br.readLine();         while (line != null) {             numbers.add(new Feature(Integer.parseInt(line), -1));             line = br.readLine();         }         br.close();                 TreeMap<Integer, Integer> map = new TreeMap<>();         for (int i = 0; i < numbers.size(); i++) {             Map.Entry<Integer, Integer> entry = map.ceilingEntr

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1475 The solution below uses a modified version of the Longest Increasing Sequence (LIS). import java.io.*; import java.util.*; class Main {     public static int reader(BufferedReader br) throws NumberFormatException, IOException {              int n;         int resp = 0;                     while (true) {                      n = br.read();             if (n == -1) return -1;                      if (n >= '0' && n <= '9') {                 break;             }         }                     while (true) {                      resp = resp*10 + n-'0';                      n = br.read();             if (n == -1) return -1;             if (n < '0' || n > '9') {                 break;                  }         }                return resp;          }         public void process() t

Link to the problem: http://br.spoj.com/problems/NUMERDOS/ The solution below used Breadth-First Search to identify the number of Erdos. First, for every author, I tried to find its "distance" to P. Erdos. However, this solution got Time Limit Exceeded. Then, I decided to start from P. Erdos and calculate its distance to every other author. import java.io.*; import java.util.*; class Main {     public HashMap<String, ArrayList<String>> adjList;     public List<Info> answer;     public HashSet<String> visited;         public void bfs(String start) {         Queue<Erdos> queue = new ArrayDeque<Erdos>();         queue.add(new Erdos(start, 0));                 while (queue.size() > 0) {             Erdos curr = queue.poll();             String currAuthor = curr.author;             int currNumErdos = curr.numErdos;                         if (visited.contains(currAuthor)) {                 continue;             }             visited.add(

Link to the problem: http://br.spoj.com/problems/FUSOES1/ The solution below used Union-Find to connect two banks. Then, when it was necessary to check if two banks were the same, we only had to check their roots. import java.io.*; import java.util.*; class Main {     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (nodeParent[n] != n) {             n = nodeParent[n];         }                 return n;     }         public void union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] >= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                 if (depth[rootN1] == depth[rootN2]) {                     depth[rootN1] += 1;                 }             }             else {                 nodeParent[rootN1] = nodeParent[rootN2];             }         }     }         public void process() throws NumberFor

Link to the problem: https://www.hackerrank.com/challenges/maxsubarray In order to obtain the maximum possible sum of a non-contiguous sub-array, we only consider the positive elements. If there is not any positive element, we consider the maximum negative element. On the other hand, to obtain the maximum possible sum of a contiguous subarray, we keep an array of sums. In this array, we keep the sum of all the elements until the current position (inclusive). If the sum is negative, we replace it by zero in the array. Then, the answer is the biggest value that we have in this array. PS.: It can also be done without using the array. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             int numElements = sc.nextInt();

Link to the problem: https://www.hackerrank.com/challenges/angry-children The solution below sorts the given array and, for every interval of size K, we check its unfairness. In addition, we keep always the minimum value of unfairness. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Solution {        public static void main(String[] args) throws NumberFormatException, IOException {       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));       int N = Integer.parseInt(br.readLine());       int K = Integer.parseInt(br.readLine());       int[] list = new int[N];       for(int i = 0; i < N; i++) {          list[i] = Integer.parseInt(br.readLine());       }            int unfairness = Integer.MAX_VALUE;       Arrays.sort(list);       for (int i = 0; i <= N-K; i++) {           int min = list[i];           int max = list[i+K-1];           unfairness = Math.min(unfairness, max-

Link to the problem: https://www.hackerrank.com/challenges/floyd-city-of-blinding-lights As the name of the problem indicates, the solution below used Floyd-Warshall. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static int[][] adjMatrix;         public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 int numNodes = sc.nextInt();         int numConnections = sc.nextInt();             adjMatrix = new int[numNodes+1][numNodes+1];         for (int i = 1; i <= numNodes; i++) {             for (int j = 1; j <= numNodes; j++) {                 if (i == j) {                     adjMatrix[i][j] = 0;                     continue;                 }                 adjMatrix[i][j] = 100000;             }         }                 for (int i = 0; i < numConnections; i++) {             int n1 = sc.nextInt();             int n2 = sc.nextInt();      

Link to the problem: https://www.hackerrank.com/challenges/pairs The solution below sorts the given array. Then, for every element in the array, we apply the following steps: Sum the element and the value of K; Call the Binary Search method to find out if the array contains the result of the sum; If the array contains the result of the sum, then we found a pair. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     static int[] elements;         static boolean binSearch(int lo, int hi, int value) {         if (lo > hi) {             return false;         }                    int m = (lo+hi)/2;         if (elements[m] < value) {             return binSearch(m+1, hi, value);         }         if (elements[m] > value) {             return binSearch(lo, m-1, value);         }         else {             return true;         }     }         static int pairs(int k) {         int count = 0;        

Link to the problem: https://www.hackerrank.com/challenges/taum-and-bday If it is cheaper to buy a gift and change its color instead of buying the appropriate color of the gift, we buy the necessary quantity of gifts and change their color. This solution is called Greedy, and it was used by the solution below. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int t = in.nextInt();         for(int a0 = 0; a0 < t; a0++){             long b = in.nextLong();             long w = in.nextLong();             long x = in.nextLong();             long y = in.nextLong();             long z = in.nextLong();                         long costB = 0;             long costW = 0;             if (x+z < y) {                 costW = (x+z)*w;             }             else {                 costW = y*w;             }       

Link to the problem: http://br.spoj.com/problems/MAGICO11/ In order to solve this problem, it is only necessary to check if the numbers are valid, if all the numbers between 1 and size^2 are being used exactly once and if the sums (row, column, diagonal) are equal. import java.io.*; import java.util.*; class Main {     public static int reader(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;          }         public void process() throws NumberFormatException, IOE

Link to the problem: http://br.spoj.com/problems/SELOS11/ The solution below has a special case that checks if the number is less than 4, which indicates that it is not possible to form a rectangle with more than one row and one column. For the other numbers, we find the square root of this number, and we check if the number is divisible for any other number between 2 and the square root. We do not check this condition between 2 and the number because the maximum number can be 10,000,000,000, which would exceed the time limit. Using the square root, we decrease considerably the number of operations. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                String line = br.readLine();         long number = Long.parseLong(line);         if

Link to the problem: http://br.spoj.com/problems/JFILA14/ The solution below keeps the sequence of the queue in an array and the sequence of people who gave up in a hashset. Then, we only need to go through the array checking whether the hashset contains the current value or not. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 String line = br.readLine();         int numPeople = Integer.parseInt(line);                 int[] people = new int[numPeople];         line = br.readLine();         String[] s = line.split(" ");         for (int i = 0; i < numPeople; i++) {             people[i] = Integer.parseInt(s[i]);         }                 HashSet<Integer> gone = new HashSet<>();         line = br.readLine();

Link to the problem: http://br.spoj.com/problems/PONTES09/ We need to find the path from the canyon to the camp which has the smaller number of holes. Then, we can use Dijkstra's algorithm to solve this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Integer, ArrayList<Edge>> adjList;         public int dijkstra(int start, int end) {         Queue<Edge> queue = new PriorityQueue<Edge>();         queue.add(new Edge(start, 0));                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {             Edge curr = queue.poll();             int currPillar = curr.pillar;             int currHoles = curr.hole;                         if (visited.contains(currPillar)) {                 continue;             }             visited.add(currPillar);                         if (currPillar == end) {                 return currHoles;             }                         ArrayList&l