UVa

UVa 686 Goldbach’s Conjecture II Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by dhruv.pancholi on 20/11/16.
 */
public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(System.in);

        int limit = 2 << 14;
        SieveOfEratosthenes soe = new SieveOfEratosthenes(limit);
        List<Integer> primes = soe.getPrimes();
        int[] arr = new int[limit + 1];

        int p1, p2;
        for (int i = 0; i < primes.size(); i++) {
            p1 = primes.get(i);
            for (int j = i; j < primes.size(); j++) {
                p2 = primes.get(j);
                if (p1 + p2 > limit) break;
                arr[p1 + p2]++;
            }
        }

        int n = 0;
        while (true) {
            n = in.nextInt();
            if (n == 0) break;
            System.out.println(arr[n]);
        }
    }

    private static class SieveOfEratosthenes {
        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean[] getArray() {
            return a;
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

6
10
12
0

Sample Output:

1
2
1

UVa 583 Prime Factors Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by dhruv.pancholi on 05/11/16.
 */
public class Main {

    public static List<Integer> getPrimeFactors(int N, List<Integer> primes) {
        List<Integer> factors = new ArrayList<Integer>();
        int index = 0;
        int factor = primes.get(index);
        int limit = (int) Math.sqrt(N) + 1;
        while (N != 1 && factor < limit) {
            while (N % factor == 0) {
                N /= factor;
                factors.add(factor);
            }
            factor = primes.get(++index);
        }
        if (N != 1) factors.add(N);
        return factors;
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(System.in);

        SieveOfEratosthenes soe = new SieveOfEratosthenes((int) Math.sqrt(Integer.MAX_VALUE) * 10);
        List<Integer> primes = soe.getPrimes();


        int n;
        while (true) {
            n = in.nextInt();
            if (n == 0) break;
            List<Integer> factors = getPrimeFactors(Math.abs(n), primes);
            System.out.print(n + " = ");
            if (n < 0) System.out.print("-1 x ");
            for (int i = 0; i < factors.size() - 1; i++) {
                System.out.print(factors.get(i) + " x ");
            }
            System.out.println(factors.get(factors.size() - 1));
        }
    }

    private static class SieveOfEratosthenes {
        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean[] getArray() {
            return a;
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

-190
-191
-192
-193
-194
195
196
197
198
199
200
0

Sample Output:

-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5

UVa 543 Goldbach’s Conjecture Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by dhruv.pancholi on 20/11/16.
 */
public class Main {

    public static void main(String[] args) {

        InputReader in = new InputReader(System.in);

        SieveOfEratosthenes soe = new SieveOfEratosthenes(1000000);
        List<Integer> primes = soe.getPrimes();

        while (true) {
            int n = in.nextInt();
            if (n == 0) break;
            for (int i = 0; i < primes.size(); i++) {
                if (soe.isPrime(n - primes.get(i))) {
                    System.out.println(n + " = " + primes.get(i) + " + " + (n - primes.get(i)));
                    break;
                }
            }
        }
    }

    private static class SieveOfEratosthenes {
        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean[] getArray() {
            return a;
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    System.exit(0);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

8
20
42
0

Sample Output:

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

UVa 524 Prime Ring Problem Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by dhruv.pancholi on 20/11/16.
 */
public class Main {

    private static boolean[] onStack = new boolean[16];

    private static void dfs(List<Integer>[] adjacency, String out, int node, int n, int N) {
        if (n == 1) {
            if (adjacency[node - 1].get(0) == 1) System.out.println(out);
            return;
        }
        for (Integer i : adjacency[node - 1]) {
            if (onStack[i - 1] || i > N) {
                continue;
            } else {
                out += " " + i;
                onStack[i - 1] = true;
                dfs(adjacency, out, i, n - 1, N);
                out = out.substring(0, out.lastIndexOf(" "));
                onStack[i - 1] = false;
            }
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(System.in);
        SieveOfEratosthenes soe = new SieveOfEratosthenes(50);
        List<Integer>[] adjacency;
        adjacency = new List[16];
        for (int i = 0; i < 16; i++) {
            adjacency[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < 16; i++) {
            for (int j = i + 1; j < 16; j++) {
                if (soe.isPrime(i + j + 2)) {
                    adjacency[i].add(j + 1);
                    adjacency[j].add(i + 1);
                }
            }
        }

        int c = 0;
        while (true) {
            LinkedList<Integer> stack = new LinkedList<Integer>();
            stack.add(1);
            onStack[0] = true;
            int n = in.nextInt();
            if (c != 0) System.out.println();
            System.out.println("Case " + (++c) + ":");
            if (n == 1) {
                System.out.println(1);
            } else {
                dfs(adjacency, "1", 1, n, n);
            }
        }
    }

    private static class SieveOfEratosthenes {
        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean[] getArray() {
            return a;
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    private static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    System.exit(0);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

6
8

Sample Output:

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

UVa 406 Prime Cuts Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class PrimeCuts {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        SieveOfEratosthenes soe = new SieveOfEratosthenes(1000);
        boolean[] arr = soe.getArray();
        arr[1] = true;
        int[] agg = new int[1001];
        for (int i = 1; i < agg.length; i++) {
            agg[i] += agg[i - 1];
            if (arr[i]) agg[i]++;
        }

        while (true) {
            int n = in.nextInt();
            int c = in.nextInt();
            int startIndex = (agg[n] % 2 == 0) ? (agg[n] / 2) : (agg[n] / 2 + 1);
            startIndex -= (c - 1);
            startIndex = startIndex > 0 ? startIndex : 1;
            int endIndex = startIndex + ((agg[n] % 2 == 0) ? (2 * c - 1) : (2 * c - 2));
            endIndex = endIndex > n ? n : endIndex;

            System.out.print(n + " " + c + ":");
            int index = 0;
            for (int i = 1; i <= n; i++) {

                if (arr[i]) {
                    index++;
                    if (index >= startIndex && index <= endIndex) {
                        System.out.print(" " + i);
                    }
                }
            }
            System.out.println();
            System.out.println();
        }
    }

    public static class SieveOfEratosthenes {
        private boolean[] a;

        public SieveOfEratosthenes(int N) {
            a = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                a[i] = true;
            }
            a[0] = false;
            a[1] = false;

            int root = (int) Math.sqrt(N);
            for (int i = 2; i <= root; i++) {
                for (int j = 2 * i; j <= N; j += i) {
                    a[j] = false;
                }
            }
        }

        public boolean[] getArray() {
            return a;
        }

        public boolean isPrime(int n) {
            return a[n];
        }

        public List<Integer> getPrimes() {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 1; i < a.length; i++) {
                if (a[i]) {
                    list.add(i);
                }
            }
            return list;
        }
    }

    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    System.exit(0);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Sample Input:

21 2
18 2
18 18
100 7

Sample Output:

21 2: 5 7 11

18 2: 3 5 7 11

18 18: 1 2 3 5 7 11 13 17

100 7: 13 17 19 23 29 31 37 41 43 47 53 59 61 67

UVa 10130 SuperSale solution in Java

Dhruv Pancholi Leave a comment 
import java.io.*;
import java.util.StringTokenizer;

public class SuperSale {

    public static void main(String[] args) throws FileNotFoundException {
        InputReader in = new InputReader(System.in);

        int T = in.nextInt();
        while (T-- != 0) {
            int N = in.nextInt();
            Object[] A = new Object[N];
            int sum = 0;
            for (int n = 0; n < N; n++) {
                A[n] = new Object(in.nextInt(), in.nextInt());
            }

            int G = in.nextInt();
            int MW;
            int max = 0;
            for (int g = 0; g < G; g++) {
                MW = in.nextInt();
                int[][] memo = new int[A.length + 1][31];

                for (int i = 1; i <= A.length; i++) {
                    for (int j = 0; j <= MW; j++) {
                        if (j + A[i - 1].weight <= MW) {
                            memo[i][j + A[i - 1].weight] = Math.max(memo[i - 1][j] + A[i - 1].price, memo[i][j]);
                        }
                        memo[i][j] = Math.max(memo[i][j], memo[i - 1][j]);
                    }
                }

                int localMax = 0;
                for (int j = 0; j <= MW; j++) {
                    localMax = Math.max(localMax, memo[A.length][j]);
                }
                max += localMax;
            }

            System.out.println(max);
        }
    }

    public static class Object {
        public int price;
        public int weight;

        public Object(int price, int weight) {
            this.price = price;
            this.weight = weight;
        }
    }
    
    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

}

Sample Input:

2
3
72 17
44 23
31 24
1
26
6
64 26
85 22
52 4
99 18
39 13
54 9
4
23
20
20
26

Sample Output:

72
514

UVa 562 Dividing Coins Solution in Java

Dhruv Pancholi Leave a comment 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class DividingCoins {
    public static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);

        int T = in.nextInt();
        while (T-- != 0) {
            int N = in.nextInt();
            int[] A = new int[N];
            int sum = 0;
            for (int n = 0; n < N; n++) {
                A[n] = in.nextInt();
                sum += A[n];
            }

            int column = 0;
            boolean[][] B = new boolean[sum / 2 + 1][N + 1];
            for (int i = 0; i < N + 1; i++) {
                B[0][i] = true;
            }


            for (int i = 0; i < A.length; i++) {
                for (int j = 0; j <= sum / 2; j++) {
                    if (B[j][i]) {
                        B[j][i + 1] = true;
                        if ((j + A[i]) <= sum / 2) {
                            B[j + A[i]][i + 1] = true;
                        }
                    }
                }
            }

            int count = 0;
            for (int i = sum / 2; i >= 0; i--) {
                if (B[i][A.length]) break;
                count++;
            }

            System.out.println((sum % 2 == 0) ? 2 * count : 2 * count + 1);
        }
    }
}

Sample Input:

11
3 2 2 1
4 5 5 2 2
3 6 7 8
4 2 3 4 5
2 24 12
2 1 1
12 1 2 3 4 5 6 7 8 9 10 11 12
4 2 3 4 19
5 3 4 2 1 11
3 10 20 30
4 5 6 3 12

Sample Output:

1
0
5
0
12
0
0
10
1
0
2

UVa 299 Train Swapping Solution in C++ (Counting Inversions)

Dhruv Pancholi Leave a comment

This problem is about counting the number of inversions in the given array. This problem can be solved with the help of insertion sort, but will be a naive method as it takes O(N2), so we are solving it with the help of merge sort in O(NlogN).
Things to learn:

  • Divide and Conquer Paradigm to solve a given problem
#include<cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

long long merge(int* arr, int* temp, int left, int mid, int right){
	
	int i, j, k;
	long long inv_count = 0;

	i = left; j = mid; k = left;
	while ((i <= mid - 1) && (j <= right)) {
		if (arr[i] <= arr[j]) temp[k++] = arr[i++];
		else{
			temp[k++] = arr[j++];
			inv_count = inv_count + (mid - i);
		}
	}

	while (i <= mid - 1) temp[k++] = arr[i++];
	while (j <= right) temp[k++] = arr[j++];
	for (i=left; i <= right; i++) arr[i] = temp[i];
	
	return inv_count;
}

long long merge_sort(int* arr, int* temp, int left, int right)
{
	int mid;
	long long inv_count = 0;
	if (right > left){
		mid = (right + left)/2;
		inv_count  = merge_sort(arr, temp, left, mid);
		inv_count += merge_sort(arr, temp, mid+1, right);
		inv_count += merge(arr, temp, left, mid+1, right);
	}
	return inv_count;
}

  
int main(){
	int T; scanf("%d", &T);
	for(int t = 0; t<T; t++){
		int N; scanf("%d", &N);
		int A[N];
		for(int i = 0; i<N; i++){
			scanf("%d", &A[i]);
		}
		int* B = (int *)malloc(N*sizeof(int));
		printf("Optimal train swapping takes %lld swaps.\n", merge_sort(A, B, 0, N-1));
	}
	return 0;
}

Sample Input:

3
3
1 3 2
4
4 3 2 1
2
2 1

Sample Output:

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Runtime: 0.002s

UVa 10194 Football (aka Soccer) Solution in C++

Dhruv Pancholi Leave a comment

A fairly straight forward problem, just one time sorting is required. There are many things to learn from this problem, which are:

  • Using constructor in struct
  • Creating comparator function for two struct
  • Interchangably using C++ and C string
  • Map also accepts C string data format
  • A pair can directly be inserted in map
  • Copying a map to vector
#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>

using namespace std;

struct Team{
	int n_games, n_wins, n_ties, n_loss,
		n_goals, n_goals_against, n_points;
	char* name;
	Team(char* TN) {
		name = TN;
		n_games = 0, n_wins = 0, n_ties = 0, n_loss = 0,
			n_goals = 0, n_goals_against = 0, n_points = 0;
	}
	Team(){
		n_games = 0, n_wins = 0, n_ties = 0, n_loss = 0,
			n_goals = 0, n_goals_against = 0, n_points = 0;
	}
};

bool teams_comparator(pair<string,Team> e1, pair<string,Team> e2){
	Team t1 = e1.second, t2 = e2.second;
    int p_a = t1.n_wins*3 + t1.n_ties, p_b = t2.n_wins*3 + t2.n_ties;
    int gd_a = t1.n_goals - t1.n_goals_against;
	int gd_b = t2.n_goals - t2.n_goals_against;
 
    if (p_a != p_b) return p_a > p_b;
    if (t1.n_wins != t2.n_wins) return t1.n_wins > t2.n_wins;
    if (gd_a != gd_b) return gd_a > gd_b;
    if (t1.n_goals != t2.n_goals) return t1.n_goals > t2.n_goals;
    if (t1.n_games != t2.n_games) return t1.n_games < t2.n_games;

    for(int i=0; i < strlen(t1.name); i++)
		t1.name[i] = tolower(t1.name[i]);
    for(int i=0; i < strlen(t2.name); i++)
		t2.name[i] = tolower(t2.name[i]);
 
    return strcmp( t1.name, t2.name) < 0;
 
}

int main(){
	int N; scanf("%d\n", &N);
	for(int n = 0; n<N; n++){
		char t_name[101]; gets(t_name);
		int n_teams; scanf("%d\n", &n_teams);
		map<string, Team> teams;
		for(int nt = 0; nt<n_teams; nt++){
			char team_name[31];
			gets(team_name);
			Team t = Team(team_name);
			teams.insert(make_pair(team_name, t));
		}

		int n_games; scanf("%d\n", &n_games);
		char game[1001];

		for(int ng = 0; ng<n_games; ng++){
			gets(game);
			int len = strlen(game);
			int i = 0, j = 0;

			// Teamname A and B
			char tn_a[31], tn_b[31];
			
			while(game[i]!='#'){tn_a[j++] = game[i++];}
			tn_a[j] = '\0'; j = 0; i++;

			// Number of goals characters
			char ngc_a[16], ngc_b[16];
			// Number of goals
			int ng_a, ng_b;

			while(game[i]!='@'){ngc_a[j++] = game[i++];}
			ngc_a[j] = '\0'; ng_a = atoi(ngc_a); j = 0; i++;
			while(game[i]!='#'){ngc_b[j++] = game[i++];}
			ngc_b[j] = '\0'; ng_b = atoi(ngc_b); j = 0; i++;

			while(game[i]!='\0'){tn_b[j++] = game[i++];}
			tn_b[j] = '\0'; j = 0; i++;

			// Getting the reference of the team A and B objects
			Team *ta = & teams[tn_a]; Team *tb = & teams[tn_b];

			(ta->n_games)++; (tb->n_games)++;
			ta->n_goals += ng_a; tb->n_goals += ng_b;
			ta->n_goals_against += ng_b; tb->n_goals_against += ng_a;

			if(ng_a == ng_b) (ta->n_ties)++, (tb->n_ties)++;
			else if(ng_a > ng_b) (ta->n_wins)++, (tb->n_loss)++;
			else (ta->n_loss)++, (tb->n_wins)++;
		}
		// Creating new vector for sorted teams
		vector< pair<string, Team> > s_teams;
		// Copying all the elements from map to a vector
		copy(teams.begin(), teams.end(), back_inserter(s_teams));
		// Sorting the teams according to the required parameters
		sort(s_teams.begin(), s_teams.end(), teams_comparator);

		puts(t_name);
		for (int j = 0; j<s_teams.size(); j++){
			printf("%d) %s %dp, %dg (%d-%d-%d), %dgd (%d-%d)\n",
				j+1, s_teams[j].first.c_str(),
				s_teams[j].second.n_wins*3 + s_teams[j].second.n_ties,
				s_teams[j].second.n_games, s_teams[j].second.n_wins,
				s_teams[j].second.n_ties, s_teams[j].second.n_loss,
				s_teams[j].second.n_goals - s_teams[j].second.n_goals_against,
				s_teams[j].second.n_goals, s_teams[j].second.n_goals_against);
		}
        if (n != N-1) printf("\n");
	}
	return 0;
}

Sample Input:

2
World Cup 1998 - Group A
4
Brazil
Norway
Morocco
Scotland
6
Brazil#2@1#Scotland
Norway#2@2#Morocco
Scotland#1@1#Norway
Brazil#3@0#Morocco
Morocco#3@0#Scotland
Brazil#1@2#Norway
Some strange tournament
5
Team A
Team B
Team C
Team D
Team E
5
Team A#1@1#Team B
Team A#2@2#Team C
Team A#0@0#Team D
Team E#2@1#Team C
Team E#1@2#Team D

Sample Output:

World Cup 1998 - Group A
1) Brazil 6p, 3g (2-0-1), 3gd (6-3)
2) Norway 5p, 3g (1-2-0), 1gd (5-4)
3) Morocco 4p, 3g (1-1-1), 0gd (5-5)
4) Scotland 1p, 3g (0-1-2), -4gd (2-6)

Some strange tournament
1) Team D 4p, 2g (1-1-0), 1gd (2-1)
2) Team E 3p, 2g (1-0-1), 0gd (3-3)
3) Team A 3p, 3g (0-3-0), 0gd (3-3)
4) Team B 1p, 1g (0-1-0), 0gd (1-1)
5) Team C 1p, 2g (0-1-1), -1gd (3-4)

Runtime: Giving incorrect answer when submitted on judge, but running correctly on sample test!

UVa 146 ID Codes Solution in C++

Dhruv Pancholi Leave a comment

Use of next_permutation, which gives the lexicographical next permutation of the given array.

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int main(){
	char a[51];
	while(gets(a)){
		if(a[0]=='#') break;
		else{
			if(next_permutation(a, a+strlen(a))) puts(a);
			else puts("No Successor");
		}
	}
	return 0;
}

Sample Input:

abaacb
cbbaa
#

Sample Output:

ababac
No Successor

Runtime: 0.009s