Posts

(UVA) Ant's Shopping Mall - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3942 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 numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numRows = sc.nextInt();             int numCols = sc.nextInt();             int[][] matrix = new int[numRows][numCols];             for (int i = 0; i < numRows; i++) {                 String line = sc.next();                 for (int j = 0; j < numCols; j++) {                     matrix[i][j] = line.charAt(j)-'0';                 }             }             int count = 0;                     int bestCount = Integer.MAX_VALUE;               for (int j = 0; j < numCol

(UVA) Wedding of Sultan - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=666&page=show_problem&problem=4027 import java.io.*; import java.util.*; class Main {     public Deque<Character> trails;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             String seq = sc.next();             char start = seq.charAt(0);                         trails = new ArrayDeque<>();             int[] count = new int[26];             for (int i = 0; i < seq.length(); i++) {                 if (trails.peek() != null && trails.peek() == seq.charAt(i)) {                     count[seq.charAt(i)-'A']++;                     trails.poll();                     if (trails.peek() == null) {

(UVA) The Orc Attack - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1734 The solution below used Floyd-Warshall 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 numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numLocations = sc.nextInt();             int numConnections = sc.nextInt();                         int[][] matrix = new int[numLocations][numLocations];             for (int i = 0; i < numLocations; i++) {                 for (int j = 0; j < numLocations; j++) {                     matrix[i][j] = Integer.MAX_VALUE/2;                 }                 matrix[i][i] = 0;             }                         for (in

(UVA) Galactic Import - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=324 The solution below used Breadth-First Search (BFS) to solve this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Character, ArrayList<Info>> adjList;         public char bfs(char start, int numPlanets) {         Queue<Info> queue = new ArrayDeque<>();         queue.add(new Info(start, 0, 0));                 HashSet<Character> visited = new HashSet<>();                 double bestValue = 0;         char bestPlanet = 'Z';         while (queue.size() > 0) {             Info curr = queue.poll();             char currPlanet = curr.planet;             double currValue = curr.value;             int currDist = curr.distance;                         if (visited.contains(currPlanet) || currValue < 0) {                 continue;             }             visited.a

(UVA) Word Transformation - Solution 2

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Floyd-Warshall to solve this problem. If you want to see another solution using Breadth-First Search, click here . import java.io.*; import java.util.*; class Main {     public ArrayList<String> mapIntToString;     public Map<String, Integer> mapStringToInt;         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = Integer.parseInt(br.readLine());         br.readLine();         for (int test = 0; test < numTests; test++) {             if (test > 0) {                 bw.write("\n"); // blank line between outputs             }                         int index = 0;             mapInt

(UVA) Word Transformation - Solution 1

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Breadth-First Search (BFS) to solve this problem. For every word that we visit in the BFS method, we check all the other words. If the other word differs only in one character of the current word, we add it in our queue. import java.io.*; import java.util.*; class Main {     public ArrayList<String> words;         public int bfs(String start, String end) {         Queue<Counter> queue = new ArrayDeque<>();         queue.add(new Counter(start, 0));                 HashSet<String> visited = new HashSet<>();                 while (queue.size() > 0) {             Counter curr = queue.poll();             String currS = curr.s;             int currCount = curr.count;                         if (visited.contains(currS)) {                 continue;             }             visited.a

(UVA) Y2K Accounting Bug - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1517 The solution below used Backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public int s;     public int d;     public int maxSurplus;     public int[] register;         public void rec(int month, int surplus, int lastFive) {         if (month >= 5) {             if (lastFive >= 0) {                 return;             }         }         if (month == 12) {             maxSurplus = Math.max(maxSurplus, surplus);             return;         }                         register[month] = s;         rec(month+1, surplus+s, lastFive + s - (month >= 5 ? register[month-5] : 0));         register[month] = d;         rec(month+1, surplus+d, lastFive + d - (month >= 5 ? register[month-5] : 0));     }         public void process() throws NumberFormatException, IOException {         Scanner sc = n