Problemas de Programação

Link to the problem: http://br.spoj.com/problems/BANCO12/ The solution below keeps a queue with the employees in order to discover who is the next employee that will serve the client.For every attendance, we check if the time that the employee will start to talk to the client minus the time that this client arrived at the bank is bigger than the 20 minutes. 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 numEmployees = Integer.parseInt(s[0]);         int numPeople = Integer.parseInt(s[1]);                 People[] people = new People[numPeople];         for (int i = 0; i < numPeople; i++) {             line = br.readLine();             s =

Link to the problem: http://br.spoj.com/problems/ROBO13/ The solution below used Depth-First Search to find the path from the first to the last '1'. import java.io.*; import java.util.*; class solucao {     public int[][] matrix;     public boolean[][] visited;     public int[] vi = {-1,0,0,1};     public int[] vj = {0,-1,1,0};     public int rowEnd;     public int colEnd;     public int numRows;     public int numCols;         public void dfs(int currI, int currJ) {         rowEnd = currI;         colEnd = currJ;         visited[currI][currJ] = true;         for (int i = 0; i < 4; i++) {             int nextI = currI+vi[i];             int nextJ = currJ+vj[i];             if (nextI > 0 && nextJ > 0 && nextI <= numRows && nextJ <= numCols && matrix[nextI][nextJ] == 1 && !visited[nextI][nextJ]) {                 dfs(nextI, nextJ);                 return;             }         }     }         public void process() throws

Link to the problem: https://www.hackerrank.com/challenges/stockmax The solution below passes through the array checking if there is any element bigger than the current element in its right. If the answer is positive, we buy the current element. Otherwise, if we have any element, we sell it/them. 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 numNumbers = sc.nextInt();             int[] numbers = new int[numNumbers];             for (int j = 0; j < numNumbers; j++) {                 int n = sc.nextInt();                 numbers[j] = n;             }                         long profit = 0;             int biggerOnTheRight = 0;             for (int j = numNumbers-1; j >= 0; j--) {                 if (biggerOn

Link to the problem: http://br.spoj.com/problems/FLOREST2/ This problem has a pattern. We start the grid with height equals to '2'. Then, to complete the "width of a square", we need more 3 trees (our 'seq'). Every time that the height is increased by one, the amount of trees necessary to complete the width of a square is increased by two.  We only count an arrangement if, given the number of available trees, it is possible to complete the width of a square. We stop to consider the arrangements when the height becomes bigger than width because we already counted the next arrangements. import java.io.*; import java.util.*; class solucao {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 int numTrees = Integer.parseInt(br.readLine());                 int

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1888 If you want to see another solution for this problem using Floyd-Warshall, click here . The solution below used Breadth-First Search (BFS) to solve this problem. We first calculate the distance between every pair of island. If the travel between these islands takes less days than it is allowed, we consider this path in our adjacency list. Finally, we call a BFS method to check if it is possible to go from the start island to the desired destination. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Integer>> adjList;         public int bfs(int start, int end) {         Queue<Integer> queue = new ArrayDeque<Integer>();         queue.add(start);                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {             in

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=1888 The solution below used Floyd-Warshall to solve this problem. Through this algorithm, it is possible to know how many days, in the worst case, are spent to travel from one island to another one. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 while (sc.hasNext()) {             int numDays = sc.nextInt(); // max number of days they can stay in the sea             int speed = sc.nextInt(); // miles a day                         ArrayList<Info> coordinates = new ArrayList<>();             coordinates.add(new Info(0, sc.nextInt(), sc.nextInt(), sc.nextInt())); // start             coordinates.add(new Info(1, s

Link to the problem: http://br.spoj.com/problems/TARZAN12/ The solution below used Union-Find to solve this problem. We connect two vertex if their distance is not more than the distance allowed. Then, in the end, we only check if the number of connections is equal to the number of trees minus one. import java.io.*; import java.util.*; class solucao {     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (nodeParent[n] != n) {             n = nodeParent[n];         }                 return n;     }         public boolean 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]++;                 }             }             else {                 nodeParent[rootN1] = nodePar

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=728 The solution below used Dynamic Programming to solve this problem. Moreover, once we would be handling very large numbers, it was necessary to use BigInteger class instead of int/long types. import java.io.*; import java.util.*; import java.math.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 while (sc.hasNext()) {             BigInteger max = new BigInteger("-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");             int numNumbers = 0;             int number = sc.nextInt();             ArrayList<Integer> numbers = new ArrayList<>();             while (number != -999999) {               

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1625 The solution below used Kadane's algorithm, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 int numBets = sc.nextInt();         while (numBets != 0) {             int[] bets = new int[numBets];             for (int i = 0; i < numBets; i++) {                 bets[i] = sc.nextInt();             }                            int[] sumBets = new int[numBets+1];             sumBets[0] = 0;             int max = 0;             int totalMax = 0;             for (int i = 1; i <= numBets; i++) {                 if (sumBets[i-1]+bets[i-1] > 0) {                   

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=83 The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem. Tip: Instead of manipulating float variables, it is better to convert the entry to an integer. import java.io.*; import java.util.*; class Main {     public int[] coins = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};     public long[][] matrix;         public long coinChange(int money, int indexCoins) {         if (money == 0) {             return 1;         }         else if (money < 0 || indexCoins < 0) {             return 0;         }                 if (matrix[money][indexCoins] != -1) {             return matrix[money][indexCoins];         }                 long use = coinChange(money-coins[indexCoins], indexCoins);         long notUse = coinChange(money, indexCoins-1);         matrix[money][indexCoins] =

Link to the problem: http://br.spoj.com/problems/ALVO13/ For every coordinate of a shot, the solution below calculates the distance between the shot and the center of the target. Then, using this information, we can call a Binary Search to find out how many circles cover this shot. import java.io.*; import java.util.*; class Main {     public long[] radius;         public int binSearch(int lo, int hi, long value) {         if (lo > hi) {             return lo;         }                 int m = (lo+hi)/2;         if (radius[m] > value) {             return binSearch(lo, m-1, value);         }         if (radius[m] < value) {             return binSearch(m+1, hi, value);         }         else {             return m;         }     }         public static long reader(BufferedReader br) throws NumberFormatException, IOException {              long n;         long resp = 0;              int sinal = 1;                     while (true) {                      n = br.read();      

Link to the problem: http://br.spoj.com/problems/PAS11/ The solution below checks every element from the left to the right to see if this element belongs to the current arithmetic progression. import java.io.*; import java.util.*; class solucao {     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 numNumbers = Integer.parseInt(line);                 int numParts = 1;         int lastDiff = 0;         int comparison = 0;         line = br.readLine();         String[] s = line.split(" ");         int lastNumber = Integer.parseInt(s[0]);         for (int i = 1; i < numNumbers; i++) {             int diff = Integer.parseInt(s[i])-lastNumber;             if (comparison > 0 && diff != lastDiff) {                 numParts++;   

Link to the problem: http://br.spoj.com/problems/PAO07/ The solution below used Binary Search to find the biggest length of bread that it is enough for everybody. import java.io.*; import java.util.*; class solucao {     public int[] sandwiches;     public int numSandwiches;     public int numPeople;         public int cutBread(int length) {         int numBread = 0;         for (int i = 0; i < numSandwiches; i++) {             int leftover = sandwiches[i];             while (leftover >= length) {                 leftover -= length;                 numBread++;             }         }         if (numBread >= numPeople) {             return 1;         }         else { // if (numBread < numPeople)             return -1;         }     }         // return the biggest length of bread that it is enough for everybody     public int binSearch(int lo, int hi, int best) {         if (lo > hi) {             return best;         }                 int m = (lo+hi)/2;         int r

Link to the problem: http://br.spoj.com/problems/TABULE12/ Given the moves that the horse must take, the solution below tries to reach every new position until there is no more moves available or until it reaches a hole. import java.io.*; import java.util.*; class Main {     public int[][] matrix;     public int[] vi = {0,-2,-1,1,2,2,1,-1,-2};     public int[] vj = {0,1,2,2,1,-1,-2,-2,-1};     public int[] movements;             public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                 matrix = new int[8][8];         matrix[4][1] = -1;         matrix[4][2] = -1;         matrix[2][2] = -1;         matrix[3][5] = -1;                 String line = br.readLine();         int numMovements = Integer.parseInt(line);                 line = br.readLine();         String[] s = line.split(" ");

Link to the problem: http://br.spoj.com/problems/FRETE08/ The solution below used Prim because in this problem we need to find the minimum spanning tree. import java.io.*; import java.util.*; class Main {     public HashMap<Integer, ArrayList<Edge>> adjList;        public int prim(int numPlaces) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(0, 0));                HashSet<Integer> visited = new HashSet<>();                int totalCost = 0;         while (queue.size() > 0) {             Edge curr = queue.poll();             int currPlace = curr.place;             int currCost = curr.cost;                        if (visited.contains(currPlace)) {                 continue;             }             visited.add(currPlace);                        totalCost += currCost;             if (visited.size() == numPlaces) {                 return totalCost;             }                        ArrayList<Edge> reachPl

Link to the problem: http://br.spoj.com/problems/GUERRA12/ 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 numNumbers = Integer.parseInt(line);                 line = br.readLine();         String[] s = line.split(" ");         int[] numbers = new int[numNumbers];         int total = 0;         for (int i = 0; i < numNumbers; i++) {             numbers[i] = Integer.parseInt(s[i]);             total += numbers[i];         }         br.close();                  int half = total/2;         int sum = 0;         for (int i = 0; i < numNumbers; i++) {             sum += numbers[i];             if (sum == half) {                 bw.write((i+1)+"\n");                 break;

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=293 The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public int[] coins = {1,5,10,25,50};     public long[][] matrix;         public long coinChange(int money, int indexCoins) {         if (money == 0) {             return 1;         }         else if (money < 0 || indexCoins < 0) {             return 0;         }                 if (matrix[money][indexCoins] != -1) {             return matrix[money][indexCoins];         }                 long use = coinChange(money-coins[indexCoins], indexCoins);         long notUse = coinChange(money, indexCoins-1);         matrix[money][indexCoins] = use+notUse;         return matrix[money][indexCoins];     }         public void process() throws NumberFormatException, IOException {   

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=653&page=show_problem&problem=2078 The solution below used the concept of Coin Change, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public int[] cubeCoins;     public long[][] matrix;         public long coinChange(int money, int indexCubeCoins) {         if (money == 0) {             return 1;         }         else if (money < 0 || indexCubeCoins < 1) {             return 0;         }                 if (matrix[money][indexCubeCoins] != -1) {             return matrix[money][indexCubeCoins];         }                 long use = coinChange(money-cubeCoins[indexCubeCoins], indexCubeCoins);         long notUse = coinChange(money, indexCubeCoins-1);         matrix[money][indexCubeCoins] = use+notUse;         return matrix[money][indexCubeCoins];     }         public void fillCubeCoins() {         fo