Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1278 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int distanceToFly;     public int[][] windstrength;     public int[][] state;         public int rec(int currAltitude, int currColumn) {         if (currAltitude >= 10 || currColumn > distanceToFly/100 || currAltitude < 0 || currColumn < 0) {             return Integer.MAX_VALUE/2; // invalid         }                 if (currAltitude == 9 && currColumn == distanceToFly/100) {        ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2415 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int numDrawers;     public int numDrawersToSecure;     public int[] drawers;     public long[][][] state;         public long rec(int currDrawer, int numLocked, int lock) {         if (currDrawer > numDrawers || numLocked > numDrawers) {             return 0;         }                 if (currDrawer == numDrawers) {             if (numLocked == numDrawersToSecure) { ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=1461 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int n;     public int an1;     public long[][] matrix;         public long rec(int i, int j) {         if (i == n && j == 1) {             return an1;         }                 if (matrix[i][j] != -1) {             return matrix[i][j];         }                 if (i < j) { ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1662 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int numUnits;     public int numBars;     public int numMaxSequence; // units wide     public long[][][] matrix;         public long rec(int pos, int totalBars, int sizeSeq) {         if (totalBars > numBars) {             return 0;         }         if (sizeSeq > numMaxSequence) {             return 0;         }           ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=508 The distance between every connected country is equal to 1. Given a starting country and a destination country, this problem wants us to find a path between them that uses the minimum number of countries. Once we will be given a lot of queries, one good solution is to use Floyd-Warshall's algorithm, that will give us all the minimum distance between every two countries. import java.io.*; import java.util.*; class Main {     public int reader(BufferedReader br) throws NumberFormatException, IOException {              int n;         int resp = 0;                     while (true) {           ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1851 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int numSubjects;     public int minMark;     public int[][] matrix;         public int rec(int grade, int subjectID) {         if (grade < minMark) {             return 0; // invalid         }                 if (subjectID == numSubjects) {             return 1; // plus one way         }            ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=682&page=show_problem&problem=3688 The problem asks us to find the sequence of direct transports that has the lowest travelling cost. For this reason, the solution below used Dijkstra. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;         public ArrayList<Integer> dijkstra(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0, new ArrayList<Integer>()));                 HashSet<Integer> visited = new HashSet<>();                 int minCost = Integer.MAX_VALUE; // ke...