Embedded Files
EGG DROPPING PUZZLE (R)
EGG DROPPING PUZZLE (R)
Egg break -> N-1 and X-1 ; Eggs does not break -> N and K-X ; MIN of all Max(B,NB) + 1
import java.util.Scanner;
import java.util.Scanner;
class Main{
class Main{
public static int minattempt(int N,int K) {
public static int minattempt(int N,int K) {
if(K==1 || K==0 || N==1) {
if(K==1 || K==0 || N==1) {
return K;
return K;
}
}
int min=Integer.MAX_VALUE;
int min=Integer.MAX_VALUE;
for(int x=1;x<=K;x++){
for(int x=1;x<=K;x++){
int res=Math.max(minattempt(N-1,x-1),minattempt(N,K-x));
int res=Math.max(minattempt(N-1,x-1),minattempt(N,K-x));
if(res<min){
if(res<min){
min=res;
min=res;
}
}
}
}
return 1+min;
return 1+min;
}
}
public static void main(String [] args){
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
int T=sc.nextInt();
for(int i=0;i<T;i++){
for(int i=0;i<T;i++){
int N=sc.nextInt();
int N=sc.nextInt();
int K=sc.nextInt();
int K=sc.nextInt();
System.out.println(minattempt(N,K));
System.out.println(minattempt(N,K));
}
}
}
}
}
}
EGG DROPPING PUZZLE (DP)
EGG DROPPING PUZZLE (DP)
public static int minattempt(int N,int K){
public static int minattempt(int N,int K){
int mat[][]=new int[N+1][K+1];
int mat[][]=new int[N+1][K+1];
for(int i=1;i<=N;i++){ //1 floor 1 trial
for(int i=1;i<=N;i++){ //1 floor 1 trial
mat[i][1]=1;
mat[i][1]=1;
mat[i][0]=0;
mat[i][0]=0;
}
}
for(int j=1;j<=K;j++){ //1 egg j trials
for(int j=1;j<=K;j++){ //1 egg j trials
mat[1][j]=j;
mat[1][j]=j;
}
}
for(int i=2;i<=N;i++){
for(int i=2;i<=N;i++){
for(int j=2;j<=K;j++){
for(int j=2;j<=K;j++){
mat[i][j]=Integer.MAX_VALUE;
mat[i][j]=Integer.MAX_VALUE;
for(int x=1;x<=j;x++){
for(int x=1;x<=j;x++){
int res=1+Math.max(mat[i-1][x-1],mat[i][j-x]);
int res=1+Math.max(mat[i-1][x-1],mat[i][j-x]);
if(res<mat[i][j]){
if(res<mat[i][j]){
mat[i][j]=res;
mat[i][j]=res;
}
}
}
}
}
}
}
}
return mat[N][K];
return mat[N][K];
}
}
LONGEST COMMON SUBSEQUENCE
LONGEST COMMON SUBSEQUENCE
i==0 && j==0 -> 0 ; same -> diagonal+1 ; diff -> Max(top,left)
public static void LCS(char s1[],char s2[]){
public static void LCS(char s1[],char s2[]){
int l1=s1.length;
int l1=s1.length;
int l2=s2.length;
int l2=s2.length;
int mat[][]=new int[l1+1][l2+1];
int mat[][]=new int[l1+1][l2+1];
for(int i=0;i<=l1;i++){
for(int i=0;i<=l1;i++){
for(int j=0;j<=l2;j++){
for(int j=0;j<=l2;j++){
if(i==0 || j==0){
if(i==0 || j==0){
mat[i][j]=0;
mat[i][j]=0;
}
}
else if(s1[i-1]==s2[j-1]){
else if(s1[i-1]==s2[j-1]){
mat[i][j]=mat[i-1][j-1]+1;
mat[i][j]=mat[i-1][j-1]+1;
}
}
else{
else{
mat[i][j]=Math.max(mat[i][j-1],mat[i-1][j]);
mat[i][j]=Math.max(mat[i][j-1],mat[i-1][j]);
}
}
}
}
}
}
return mat[l1][l2];
return mat[l1][l2];
}
}
LONGEST COMMON SUBSTRING
LONGEST COMMON SUBSTRING
i==0 && j==0 -> 0 ; same -> diagonal+1 - res=MAX(res,diagonal+1) ; diff -> 0
public static void LCS(char s1[],char s2[]){
public static void LCS(char s1[],char s2[]){
int l1=s1.length;
int l1=s1.length;
int l2=s2.length;
int l2=s2.length;
int result=0;
int result=0;
int mat[][]=new int[l1+1][l2+1];
int mat[][]=new int[l1+1][l2+1];
for(int i=0;i<=l1;i++){
for(int i=0;i<=l1;i++){
for(int j=0;j<=l2;j++){
for(int j=0;j<=l2;j++){
if(i==0 || j==0){
if(i==0 || j==0){
mat[i][j]=0;
mat[i][j]=0;
}
}
else if(s1[i-1]==s2[j-1]){
else if(s1[i-1]==s2[j-1]){
mat[i][j]=mat[i-1][j-1]+1;
mat[i][j]=mat[i-1][j-1]+1;
result=Math.max(result,mat[i][j]);
result=Math.max(result,mat[i][j]);
}
}
else{
else{
mat[i][j]=0;
mat[i][j]=0;
}
}
}
}
}
}
return result;
return result;
}
}
0-1 Knapsack problem
0-1 Knapsack problem
import java.util.*;
import java.util.*;
public class Main {
public class Main {
public static void main(String [] args){
public static void main(String [] args){
Scanner sc=new Scanner(System.in);
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int N=sc.nextInt();
int C=sc.nextInt();
int C=sc.nextInt();
int W[]=new int[N];
int W[]=new int[N];
int V[]=new int[N];
int V[]=new int[N];
for(int i=0;i<N;i++){
for(int i=0;i<N;i++){
W[i]=sc.nextInt();
W[i]=sc.nextInt();
}
}
for(int i=0;i<N;i++){
for(int i=0;i<N;i++){
V[i]=sc.nextInt();
V[i]=sc.nextInt();
}
}
int mat[][]=new int[N+1][C+1];
int mat[][]=new int[N+1][C+1];
for(int i=0;i<=N;i++){
for(int i=0;i<=N;i++){
for(int j=0;j<=C;j++){
for(int j=0;j<=C;j++){
if(i==0||j==0){
if(i==0||j==0){
mat[i][j]=0;
mat[i][j]=0;
}
}
else if(W[i-1]<=j){
else if(W[i-1]<=j){
mat[i][j]=Math.max(mat[i-1][j],V[i-1]+mat[i-1][j-W[i-1]]);
mat[i][j]=Math.max(mat[i-1][j],V[i-1]+mat[i-1][j-W[i-1]]);
}
}
else{
else{
mat[i][j]=mat[i-1][j];
mat[i][j]=mat[i-1][j];
}
}
}
}
}
}
System.out.print(mat[N][C]);
System.out.print(mat[N][C]);
}
}
}
}
EDIT THE DISTANCE
EDIT THE DISTANCE
i==0 -> j ; j==0 -> i ; same -> diagonal ; diff -> Max(top,left)+1 (**top-remove,left-insert,diagonal-replace**)
if two operations are allowed insert and delete there are (m-lcs) delete operation and (n-lcs) insert operation
public static void EDIT(char s1[],char s2[]){
public static void EDIT(char s1[],char s2[]){
int l1=s1.length;
int l1=s1.length;
int l2=s2.length;
int l2=s2.length;
int mat[][]=new int[l1+1][l2+1];
int mat[][]=new int[l1+1][l2+1];
for(int i=0;i<=l1;i++){
for(int i=0;i<=l1;i++){
for(int j=0;j<=l2;j++){
for(int j=0;j<=l2;j++){
if(i==0 || j==0){
if(i==0 || j==0){
mat[i][j]=0;
mat[i][j]=0;
}
}
else if(s1[i-1]==s2[j-1]){
else if(s1[i-1]==s2[j-1]){
mat[i][j]=mat[i-1][j-1];
mat[i][j]=mat[i-1][j-1];
}
}
else{
else{
mat[i][j]=1+Math.min(mat[i][j-1],mat[i-1][j],mat[i-1][j-1]);
mat[i][j]=1+Math.min(mat[i][j-1],mat[i-1][j],mat[i-1][j-1]);
}
}
}
}
}
}
return mat[l1][l2];
return mat[l1][l2];
//find lcs print (m-lcs)+(n-lcs);
//find lcs print (m-lcs)+(n-lcs);
MAX VALUE OBTAINED
MAX VALUE OBTAINED
Page updated
Google Sites
Report abuse