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...

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];   ...

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 (i...

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));    ...

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);    ...

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           ...

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);      ...

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")...

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++) {     ...

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;   ...

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);         }     ...

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; ...

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++;    ...

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];       ...

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 currP...

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 (i...

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][i...

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][index...