LightOj

Problem No: lightoj1107
Category: Easy

import java.util.*;
public class lightoj1107 {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int test=in.nextInt();
int c=0;
while(test-->0){
int x1=in.nextInt(),y1=in.nextInt(),x2=in.nextInt(),y2=in.nextInt();
int num=in.nextInt();
System.out.println("Case "+(++c)+":");
for(int i=0;i<num;i++){
int x=in.nextInt(),y=in.nextInt();
if(x>=x1 && x<=x2 && y>=y1 && y<=y2){
System.out.println("Yes");
}else{
System.out.println("No");
}
}
}
}
}

Bellman Ford-Shortest Path

Author: Jisan
Help Hints: https://www.youtube.com/watch?v=hq3TZInZ5J4

BellmanFordShortestPath:

package algorithmRevise;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.*;
public class BellmanFord {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in=new Scanner(new FileReader("ShortestPaths.txt"));
        int n=in.nextInt();
        for(int c=1;c<=n;c++){
            int N=in.nextInt();
            int M=in.nextInt();
            int[] dist=new int[N];
            Edge[] ar=new Edge[M];
            System.out.printf("Case #%d:\n", c);
            for(int i=1;i<N;i++){
                dist[i]=Integer.MAX_VALUE;
            }
            for(int i=0;i<M;i++){
                ar[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt());
            }
            for(int i=0;i<N-1;i++){
                for(int j=0;j<M;j++){
                    Edge e=ar[j];
                    if(dist[e.d]>dist[e.s]+e.w){
                        dist[e.d]=dist[e.s]+e.w;
                    }
                }
            }
            boolean flag=false;
            for(int j=0;j<M;j++){
                Edge e=ar[j];
                if(dist[e.d]>dist[e.s]+e.w){
                    System.out.println("  No solution -- graph has a negative cycle.");
                    flag=true;
                }
            }
             for(int i = 0; !flag && i < N; i++)
                    System.out.printf("  %d --> %d : %d\n", 0, i, dist[i]);
   
                System.out.println();
        }
        in.close();
    }
}
class Edge{
    int s,d,w;
    public Edge(int s,int d,int w){
        this.s=s;
        this.d=d;
        this.w=w;
    }
}

495 - Fibonacci Freeze (Dynamic approach)

Author : Jisan
Programming language : Java 
Difficulty : Easy
Status : Accepted
Problem number : UVA-495
 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=436

Code:

import java.math.BigInteger;
import java.util.Scanner;
public class Uva_495 {
    public static void main(String[] args) {
        BigInteger[] fib = fib(5001);
        Scanner in= new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            System.out.printf("The Fibonacci number for %d is %d\n", n, fib[n] );
        }
    }

    public static BigInteger[] fib(int n) {
        BigInteger[] fib = new BigInteger[n + 1];
        fib[0] = BigInteger.ZERO;
        fib[1] = BigInteger.ONE;
        for (int i = 2; i <= n; i++)
            fib[i]= fib[i-1].add(fib[i-2]);
        return fib;
    }
}

674 - Coin Change (Knapsack algorithm)

Author : Jisan
Programming language : Java 
Difficulty : Medium
Status : Accepted
Problem number : UVA-674 (Dynamic Algorithm)
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=615

Code:

import java.util.*;
public class CoinChange{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        long[] ways=new long[40000];
        int[] coin={50,25,10,5,1};
       
        int types=5;
        int i,j,change,taken;
       
        ways[0]=1;
        for(i=0;i<types;i++){
            taken=coin[i];
            for(j=taken;j<=30000;j++){
                ways[j]+=ways[j-taken];
            }
        }
       
       
        while(in.hasNextInt()){
             change=in.nextInt();       
                System.out.println(ways[change]);
            
        }

    }

}

10959 - The Party, Part I (BFS)

Author : Jisan
Programming language : Java 
Difficulty : Medium
Status : Accepted
Problem number : UVA-10959
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1900

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class TheParty1 {

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);
        int tc = in.nextInt();
        while (tc-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            boolean[][] g = new boolean[n][m];
            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                g[a][b] = g[b][a] = true;
            }

            int[] dist = new int[n];
            Arrays.fill(dist, -1);
            dist[0] = 0;
            Queue<Integer> Q = new ArrayDeque<Integer>();
            Q.add(0);
            while (!Q.isEmpty()) {
                int i = Q.remove();
                for (int j = 0; j < n; j++)
                    if (g[i][j] && dist[j] == -1) {
                        dist[j] = dist[i] + 1;
                        Q.add(j);
                    }
            }
            for (int i = 1; i < n; i++)
                System.out.println(dist[i]);
            if (tc != 0)
                System.out.println();
        }
    }

    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 int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

357 - Let Me Count The Ways(Knapsack Algorithm)

Author : Jisan
Programming language : Java 
Difficulty : Easy
Status : Accepted
Problem number : UVA-357
 http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=293&mosmsg=Submission+received+with+ID+14243094

Code:

import java.util.*;
public class LetMeCountTheWays {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in=new Scanner(System.in);
        long[] ways=new long[40000];
        int[] coin={50,25,10,5,1};
       
        int types=5;
        int i,j,change,taken;
       
        ways[0]=1;
        for(i=0;i<types;i++){
            taken=coin[i];
            for(j=taken;j<=30000;j++){
                ways[j]+=ways[j-taken];
            }
        }
       
       
        while(in.hasNextInt()){
             change=in.nextInt();           
              if(ways[change] == 1){
                System.out.println("There is only "+ways[change]+" way to produce "+change+" cents change.");
              }else{
                System.out.println("There are "+ways[change]+" ways to produce "+change+" cents change.");
              }
        }

    }

}

An Interesting Game.

Author : Jisan
Programming language : Java 
Difficulty : Easy
Status : Accepted
Problem number : UVA-12751
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4604

Code:

import java.util.*;
public class Uva_12751 {

public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int a=in.nextInt();
int s=0;

for(int cases=1;cases<=a;cases++){
int b=in.nextInt();
int k=in.nextInt();
int x=in.nextInt();

int rem=0;
for(int c=0;c<k;c++){
rem=rem+x;
x++;
}
s=(b*(b+1))/2;
System.out.println("Case "+cases+": "+(s-rem));
}

}

}