Sunday, 21 December 2014

LightOJ [1212]

Problem
1212 - Double Ended Queue

Idea Flow
Input_Constraint ~ All operation must be done in O(1)
Question Hints ~ Cake Walk
Conclusion ~ Just follow what problem statement tells.
Learnt lesson ~ Can try different DS other than deque. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package net.egork;

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class L1212 {
    private static final String CASE = "Case";
    private static final String SPACE = " ";
    private static final String COLON = ":";
    private static final String PUSHLEFT = "pushLeft";
    private static final String PUSHRIGHT = "pushRight";
    private static final String POPLEFT = "popLeft";
    private static final String POPRIGHT = "popRight";
    private static final String QUEUEFULL = "The queue is full";
    private static final String PSLEFT = "Pushed in left: ";
    private static final String PSRIGHT = "Pushed in right: ";
    private static final String QUEUEEMPTY = "The queue is empty";
    private static final String POSLEFT = "Popped from left: ";
    private static final String POSRIGHT = "Popped from right: ";

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        int testCase;
        testCase = in.nextInt();
        for (int i = 1; i <= testCase; i++) {
            Deque<Integer> deque = new ArrayDeque<Integer>();
            int sizeDeque, n;
            sizeDeque = in.nextInt();
            n = in.nextInt();
            String getLine;
            String command[];
            System.out.println(CASE + SPACE + i + COLON);
            in.nextLine();
            while (n > 0) {
                getLine = in.nextLine();
                command = getLine.split(" ");
                if (command[0].equals(PUSHLEFT)) {
                    if (checkFull(deque.size(), sizeDeque)) {
                        System.out.println(QUEUEFULL);

                    } else {
                        deque.addFirst(Integer.parseInt(command[1]));
                        System.out.println(PSLEFT + command[1]);
                    }

                } else if (command[0].equals(PUSHRIGHT)) {
                    if (checkFull(deque.size(), sizeDeque)) {
                        System.out.println(QUEUEFULL);

                    } else {
                        deque.addLast(Integer.parseInt(command[1]));
                        System.out.println(PSRIGHT + command[1]);
                    }

                } else if (command[0].equals(POPLEFT)) {
                    if (deque.isEmpty()) {
                        System.out.println(QUEUEEMPTY);
                    } else {
                        System.out.println(POSLEFT + deque.getFirst());
                        deque.removeFirst();
                    }

                } else if (command[0].equals(POPRIGHT)) {
                    if (deque.isEmpty()) {
                        System.out.println(QUEUEEMPTY);
                    } else {
                        System.out.println(POSRIGHT + deque.getLast());
                        deque.removeLast();
                    }

                }
                n--;
            }

        }

    }

    private boolean checkFull(int size, int sizeDeque) {
        return size == sizeDeque;

    }
}
Posted by at No comments:
Labels: ,

LightOJ[1303]

Problem 
1303 - Ferris Wheel

Idea Flow
Input_Constraint ~ Total number of passengers and total number of seats are 20, 20 respectively.
Question Hints ~ Cake Walk
Conclusion ~ proper use of indexing and arrayList can solve the problem.
Learnt lesson ~ Solver need to analyze the time complexity.

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package net.egork;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.io.PrintWriter;

public class L1303 {
    private static final String CASE = "Case";
    private static final String SPACE = " ";
    private static final String COLON = ":";


    int n, m, cursor;
    private int totalTime;

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        int testCase;
        testCase = in.nextInt();
        for (int i = 1; i <= testCase; i++) {
            cursor = 0;
            totalTime = 0;
            n = in.nextInt();
            m = in.nextInt();
            int dp[][] = new int[n + 2][m + 2];
            int circularArray[] = new int[m + 2];
            List<Integer> integerList = new ArrayList<Integer>();
            for (int j = 1; j <= n; j++)
                integerList.add(j);

            do {
                    cursor = (cursor + 1) % m;
                    int outPerson = circularArray[cursor];
                    circularArray[cursor] = 0;
                    if (isNeeded(dp, outPerson)) {
                        integerList.add(outPerson);
                    }
                    int findPerson = getPerson(integerList, dp);
                    if (findPerson >= 0) {
                        int personNumber = integerList.get(findPerson);
                        dp[personNumber][cursor] = 1;
                        integerList.remove(findPerson);
                        circularArray[cursor] = personNumber;
                    }
                    totalTime += 5;

            } while (!isFWEMPTY(circularArray));
            System.out.println(CASE + SPACE +i + COLON + SPACE + totalTime);
        }

    }

    private boolean isFWEMPTY(int[] circularArray) {
        for (int i = 0; i < m; i++) {
            if (circularArray[i] > 0)
                return false;
        }
        return true;
    }

    private boolean isNeeded(int[][] dp, int person) {
        if (person == 0)
            return false;
        for (int i = 0; i < m; i++) {
            if (dp[person][i] == 0)
                return true;
        }
        return false;
    }

    private int getPerson(List<Integer> integerList, int[][] dp) {
        int sz = integerList.size();
        for (int i = 0; i < sz; i++) {
            if (dp[integerList.get(i)][cursor] == 0) {
                return i;
            }
        }
        return -1;

    }

}
Posted by at No comments:
Labels: , ,

LightOJ [1113]

Problem 
1113 - Discover the Web

Idea Flow
Input_Constraint ~ All operation must be done in O(1)
Question Hints ~ Cake Walk
Conclusion ~ Just follow what problem statement tells.
Learnt lesson ~ Solver need to analyze the time complexity.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package net.egork;

import java.util.ArrayList;
import java.util.Scanner;
import java.io.PrintWriter;
import java.util.Stack;

public class L1113 {

    private static final String FORWARD = "FORWARD";
    private static final String VISIT = "VISIT";
    private static final String BACK = "BACK";
    private static final String QUIT = "QUIT";
    private static final String IGNORED = "Ignored";
    private static final String URL = "http://www.lightoj.com/";

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        int testCase;
        testCase = in.nextInt();
        String query[];
        String current;
        for (int i = 1; i <= testCase; i++) {
            System.out.println("Case " + i + ":");
            Stack<String> forwardStack = new Stack<String>();
            Stack<String> backwardStack = new Stack<String>();
            current = URL;
            while (true) {
                query = in.nextLine().split(" ");
                if (query[0].equals(FORWARD)) {
                    if (forwardStack.isEmpty()) {
                        System.out.println(IGNORED);
                    } else {
                        backwardStack.add(current);
                        current = forwardStack.peek();
                        forwardStack.pop();
                        System.out.println(current);

                    }
                } else if (query[0].equals(VISIT)) {
                    backwardStack.push(current);
                    forwardStack.clear();
                    current = query[1];
                    System.out.println(current);
                } else if (query[0].equals(BACK)) {
                    if (backwardStack.isEmpty()) {
                        System.out.println(IGNORED);
                    } else {
                        forwardStack.add(current);
                        current = backwardStack.peek();
                        backwardStack.pop();
                        System.out.println(current);
                    }

                } else if (query[0].equals(QUIT)) {
                    break;
                }

            }
        }

    }
}
Posted by at No comments:
Labels: ,
Subscribe to: Comments (Atom)