Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1008 The problem asks us if it is possible to go from a state to another one without visiting states that are forbidden using the minimum number of operations. For this reason, the solution below used Breadth-First Search (BFS) to solve this problem. import java.io.*; import java.util.*; class Main {     public int[][] forbidden;     public int numForbidden;     public int[] start;     public int[] end;         public int bfs(int s1, int s2, int s3, int s4) {         Queue<State> queue = new ArrayDeque<>();         queue.add(new State(s1, s2, s3, s4, 0));                boolean[][][][] visited = new boolean...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=3743 The solution below used a Greedy approach to solve this problem. We need to create an array with some information about the gas stations. This array is sorted based on the left limit, and we always try to choose the gas station that covers a bigger right area. import java.io.*; import java.util.*; class Main {     public int lengthRoad;     public int numGasStation;     public Gas[] gas;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         lengthRoad = sc.nextInt();      ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=582 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 key = sc.nextInt();         while (key != 0) {             String code = sc.next();             int size = code.length();             String s = "_abcdefghijklmnopqrstuvwxyz.";                ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=745&page=show_problem&problem=2174 import java.io.*; import java.util.*; class Main {     public boolean receiveES(String s) {         if (s.charAt(s.length()-1) == 'o'                 || s.charAt(s.length()-1) == 's'                 || s.charAt(s.length()-1) == 'x'                 || (s.charAt(s.length()-2) == 'c' && s.charAt(s.length()-1) == 'h')                 || (s.charAt(s.length()-2) == 's' && s.charAt(s.length()-1) == 'h')) {             return true...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3183 We start this problem with the information of the maximum value of k. Then, we can use Binary Search to discover the minimum value of k. For every possible value, we need to simulate if the monkey can reach the top rung. import java.io.*; import java.util.*; class Main {     public int best;     public int[] distances;     public int numRungs;         public boolean simulate(int strength) {         int previous = 0;         for (int i = 0; i < numRungs; i++) {             int distance = distances[i]-previous;             if (distance > strength) {      ...

Link to the problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2408 Based on the sum of the content of all vessels, the solution below used Binary Search to find out the minimum possible capacity of the container with maximum capacity. import java.io.*; import java.util.*; class Main {     public int[] vessels;     public int numVessels;     public int numContainers;     public int best;         // try to fill the numContainers with maxContainer (max)     public boolean simulate(int maxContainer) {         int index = 0;         for (int i = 0; i < numContainers; i++) {             int amount = 0;             while (ind...

Link to the solution: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=716 The solution below used Backtracking to try to find a Hamiltonian Cycle. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Integer>> adjList;     public HashSet<Integer> visited;     public ArrayList<Integer> orderVisit;     public ArrayList<Integer> answer;     public int numVertices;     public boolean found;     public int start;         public void rec(int curr) {         if (visited.size() == numVertices && adjList.get(curr).contains(start)) {             answer = (ArrayList<Integer>) orderVisit.clone();      ...