11332 - Summing Digits

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

int GetDigit(int number)
{
//System.out.println(number);
int sum=0;
if(number<10)
return number;


while((number/10)>0)
{
sum+=number%10;
number=number/10;
}

sum+=number;
return GetDigit(sum);
}

public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub

String input;
        Main digitCounting=new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        while ((input=br.readLine()) != null)
{
 if(input.compareTo("0")==0)
 break;
 else
System.out.println(digitCounting.GetDigit(Integer.parseInt(input)));

}

}

}

Percolation

Percolation.java
==================
public class Percolation {
 private enum State {
  BLOCKD, OPEN, FULL
 }

 private State[][] site;
 private int N;
 private WeightedQuickUnionUF unionFindHelper;

 public Percolation(int N) // create N-by-N grid, with all sites blocked
 {
  if (N <= 0)
     throw new IllegalArgumentException();
  this.N = N;
  unionFindHelper = new WeightedQuickUnionUF(N * N + 2);
  site = new State[N][N];
  for (int i = 0; i < N; i++) {
   for (int j = 0; j < N; j++) {
    site[i][j] = State.BLOCKD;
   }
  }

 }

 public void open(int i, int j) // open site (row i, column j) if it is not
 // open already
 {
  if ((i < 1) || (i > N))
   throw new IndexOutOfBoundsException("row index i out of bounds");

  if ((j < 1) || (j > N))
   throw new IndexOutOfBoundsException("row index j out of bounds");

  if (isOpen(i, j))
   return;
  else
   site[i - 1][j - 1] = State.OPEN;

  if (i == 1) {
   unionFindHelper.union(0, twoDimensionToOneDimension(i, j));
  }

  if (i == N) {
   unionFindHelper.union(twoDimensionToOneDimension(i, j), N * N + 1);
  }

  if (isValidSite(i - 1, j) && (isOpen(i - 1, j) || isFull(i - 1, j))) {
   unionFindHelper.union(twoDimensionToOneDimension(i, j),
     twoDimensionToOneDimension(i - 1, j));
 
   if(unionFindHelper.connected(0, twoDimensionToOneDimension(i-1, j)))
  site[i-2][j-1] = State.FULL;
  }

  if (isValidSite(i, j - 1) && (isOpen(i, j - 1) || isFull(i, j - 1))) {
   unionFindHelper.union(twoDimensionToOneDimension(i, j),
     twoDimensionToOneDimension(i, j - 1));
 
   if(unionFindHelper.connected(0, twoDimensionToOneDimension(i, j-1)))
  site[i-1][j-2] = State.FULL;
  }

  if (isValidSite(i, j + 1) && (isOpen(i, j + 1) || isFull(i, j + 1))) {
   unionFindHelper.union(twoDimensionToOneDimension(i, j),
     twoDimensionToOneDimension(i, j + 1));

   if(unionFindHelper.connected(0, twoDimensionToOneDimension(i, j + 1)))
  site[i-1][j] = State.FULL;
  }

  if (isValidSite(i + 1, j) && (isOpen(i + 1, j) || isFull(i + 1, j))) {
   unionFindHelper.union(twoDimensionToOneDimension(i, j),
     twoDimensionToOneDimension(i + 1, j));
 
   if(unionFindHelper.connected(0, twoDimensionToOneDimension(i+1, j)))
  site[i][j-1] = State.FULL;
  }

  if (unionFindHelper.connected(0, twoDimensionToOneDimension(i, j))) {
   site[i - 1][j - 1] = State.FULL;
  }

 }

 private int twoDimensionToOneDimension(int i, int j) {
  // TODO Auto-generated method stub
  return (i - 1) * N + j;
 }

 private boolean isValidSite(int i, int j) {
     return !((i < 1) || (i > N) || (j < 1) || (j > N));
 }

 public boolean isOpen(int i, int j) // is site (row i, column j) open?
 {
  if (!isValidSite(i, j))
   throw new IndexOutOfBoundsException();

  return (site[i - 1][j - 1] == State.OPEN) || (site[i - 1][j - 1] == State.FULL);
 }

 public boolean isFull(int i, int j) // is site (row i, column j) full?
 {
  if (!isValidSite(i, j))
   throw new IndexOutOfBoundsException();
  return (site[i - 1][j - 1] == State.FULL);
 }

 public boolean percolates() // does the system percolate?
 {
  return unionFindHelper.connected(0, N * N + 1);

 }

 public static void main(String[] args) // test client (optional)
 {int N=2;
  Percolation p = new Percolation(N);
  p.open(1, 1);
  p.open(2, 2);
  p.open(2, 1);
  System.out.println(p.isFull(1, 1));
 
  for(int i=0;i<N;i++)
  {  for(int j=0;j<N;j++)
  {
 System.out.print(p.site[i][j]+ " ");
  }
  System.out.println();
  }
 }
}

PercolationStats.java

==================

public class PercolationStats {

 private int T;

 private double[] percolationThresholdArray;

 public PercolationStats(int N, int T) // perform T independent experiments

 // on an N-by-N grid

 {

  this.T = T;

  if (N <= 0 || T <= 0) {

   throw new IllegalArgumentException();

  }

  percolationThresholdArray = new double[T];

  for (int t = 0; t < T; t++) {

   Percolation percolation = new Percolation(N);

   int row;

   int col;

   int numberOfSiteOpend = 0;

   while (!percolation.percolates()) {

    row = StdRandom.uniform(N) + 1;

    col = StdRandom.uniform(N) + 1;

    if (!percolation.isOpen(row, col)) {

     percolation.open(row, col);

     numberOfSiteOpend++;

    }

   }

   percolationThresholdArray[t] = (double) numberOfSiteOpend

     / (double) (N * N);

  }

 }

 public double mean() // sample mean of percolation threshold

 {

  double mean = 0;

  for (int t = 0; t < T; t++) {

   mean += percolationThresholdArray[t];

  }

  mean = mean / T;

  return mean;

 }

 public double stddev() // sample standard deviation of percolation threshold

 {

  double stdDev = 0;

  double mean = this.mean();

  for (int t = 0; t < T; t++) {

   stdDev += (percolationThresholdArray[t] - mean)

     * (percolationThresholdArray[t] - mean);

  }

  stdDev = stdDev / (T - 1);

  stdDev = Math.pow(stdDev, 0.5);

  return stdDev;

 }

 public double confidenceLo() // low endpoint of 95% confidence interval

 {

  double mu = mean();

  double sigma = stddev();

  double confidence = mu - (1.96 * sigma / Math.pow(T, 0.5));

  return confidence;

 }

 public double confidenceHi() // high endpoint of 95% confidence interval

 {

  double mu = mean();

  double sigma = stddev();

  double confidence = mu + (1.96 * sigma / Math.pow(T, 0.5));

  return confidence;

 }

 public static void main(String[] args) {

  if (args.length == 2) {

   try {

    int N = Integer.parseInt(args[0]);

    int T = Integer.parseInt(args[1]);

    PercolationStats ps = new PercolationStats(N, T);

    System.out.println("mean                    = " + ps.mean());

    System.out.println("stddev                  = " + ps.stddev());

    System.out.println("95% confidence interval = "

      + ps.confidenceLo() + ", " + ps.confidenceHi());

    System.out.println("\n");

   } catch (NumberFormatException e) {

    System.err.println("Argument" + args[0]

      + " must be an integer.");

   }

  }

 }

}

103 - Stacking Boxes

// StakingBox.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
// StakingBox.cpp : Defines the entry point for the console application.
//



#include<iostream>
#include<vector>
#include<algorithm>
#include <stdio.h>
using namespace std;

struct Box
{
vector<int> dimentions;
int number;
int numberOfBoxesFit;
int child;
};

bool comparer(Box a, Box b)
{
    vector<int>::iterator itB=b.dimentions.begin();
    for(vector<int>::iterator itA=a.dimentions.begin();itA!=a.dimentions.end();++itA,++itB)
    {
        if(*itA>=*itB)
            return false;
    }
    return true;
}


int main()
{



int k;
int n;

while(scanf("%i%i",&k,&n)!=EOF)
{
vector<Box> boxes;
boxes.clear();
Box box;

for(int i=0;i<k;i++)
{
box.dimentions.clear();
for(int j=0;j<n;j++)
{
int t;
scanf("%d",&t);
box.dimentions.push_back(t);
}
box.number=i+1;
box.numberOfBoxesFit=0;
box.child=-1;
boxes.push_back(box);

}


for (std::vector<Box>::iterator boxIt=boxes.begin(); boxIt!=boxes.end(); ++boxIt)
        std::sort((*boxIt).dimentions.begin(),(*boxIt).dimentions.end());
   
for (int i=0;i<boxes.size();i++)
{
for (int j=0;j<boxes.size();j++)
{
if(i!=j)
{
if(comparer(boxes[i],boxes[j]))
{
Box temp=boxes[i];
boxes[i]=boxes[j];
boxes[j]=temp;
}
}
}
}

int maxVal=0;
int maxBoxIndex=1;
for (int i=0; i<boxes.size(); ++i)
    {      
for (int j=0; j<boxes.size(); ++j)
{
if(i!=j)
{
if(comparer(boxes[j],boxes[i])) //if A is bigger than B
{
if(boxes[i].numberOfBoxesFit<=boxes[j].numberOfBoxesFit)
{
boxes[i].numberOfBoxesFit=boxes[j].numberOfBoxesFit+1;
boxes[i].child=boxes[j].number;
}
if(maxVal<=boxes[i].numberOfBoxesFit)
{
maxVal=boxes[i].numberOfBoxesFit;
maxBoxIndex=boxes[i].number;
}
}
}
}          
    }  

/*for (std::vector<Box>::iterator boxIt=boxes.begin(); boxIt!=boxes.end(); ++boxIt)
    {
        Box b=*boxIt;
cout<<b.number<<". Number of box fits="<<b.numberOfBoxesFit<<" and child "<<b.child<<" :";
        for(vector<int>::iterator it=b.dimentions.begin();it!=b.dimentions.end();++it)
        {
        cout<<*it<<" ";
        }
       
        cout<<endl;
    }*/

   
//cout<<"Max Val:"<<maxVal<<" max box:"<<maxBoxIndex<<endl;
vector<int> result;
int loop=0;
while(1)
{
if(boxes[loop].number==maxBoxIndex)
{
//cout<<boxes[loop].number<<" ";
result.push_back(boxes[loop].number);
if(boxes[loop].child==-1)
break;
maxBoxIndex=boxes[loop].child;
loop=0;

}
else
{
loop=(loop+1)%boxes.size();
}
}

cout<<result.size()<<endl;
for(int i=result.size()-1;i>=0;i--)
{
if(i!=result.size()-1)
cout<<" ";
cout<<result[i];
}

cout<<endl;

}

return 0;
}

10774 - Repeated Josephus

#include <iostream>
//10774 - Repeated Josephus
using namespace std;
int Josephus(int n,int k)
{
    if(n==1)
        return 1;
    else return (Josephus(n - 1, k) + k-1) % n + 1;
}

void RepeatedJosephus(int caseNo,int n)
{

    int counter=0;
    do
    {
        int result=Josephus(n,2);

        //cout<<result<<endl;
        if(result==n)
        {
            break;
        }
        else
        {
            counter++;
            n=result;
        }
    }while(1);

    cout<<"Case "<<caseNo<<": "<<counter<<" "<<n<<endl;
}

int main()
{
    int caseN;
    cin>>caseN;
    for(int i=0;i<caseN;i++)
    {
        int n;
        cin>>n;
        RepeatedJosephus(i+1,n);
    }
return 0;
}

136 - Ugly Numbers

#include <iostream>

using namespace std;
int GetFactor(int n)
{
    if(n==2 || n==3||n==5)
        return 1;

int modTwo=n%2;
int modThree=n%3;
int modFive=n%5;

if(modTwo==0)
       return  GetFactor(n/2);
    else if(modThree==0)
        return GetFactor(n/3);
    else if(modFive==0)
        return GetFactor(n/5);
    else
        return 0;
}

int main()
{
cout<<"The 1500'th ugly number is 859963392."<<endl;

//int count=1;
//for(int i=2;count<=1502;i++)
 //   {
 //       if(i%2==0 || i%3==0 || i%5==0)
 //       {
 //           if(GetFactor(i))
// {
// count++;
// cout<<count<<" "<<i<<endl;
// }
 //       }

 //   }

//cin.get();
return 0;
}

113 - Power of Cryptography

#include <math.h>
#include <stdio.h>
#include <iostream>

using namespace std;
int main()
{
double n,p;
while(scanf("%lf%lf",&n,&p) == 2)
{
printf("%.0lf\n",pow(p,1/n));
}

return 0;
}

130 - Roman Roulette

// romanR.cpp : Defines the entry point for the console application.
//

#include <iostream>
using namespace std;

struct node
{
int data;
struct node * next;
};

typedef struct node point;

point * startPoint=NULL;

void createCircularList(int N)
{
point * nextPoint;
for(int i=1;i<=N;i++)
{
  if(startPoint==NULL)
{
startPoint=new node();
startPoint->data=1;
startPoint->next=NULL;
nextPoint=startPoint;
}
else
{
point * newPoint=new point();
newPoint->data=i;

nextPoint->next=newPoint;
newPoint->next=startPoint;
nextPoint=newPoint;
}
}
}

void showAllNode()
{
point * temp=startPoint;

while(temp!=NULL)
{
cout<<temp->data<<" ";
if(temp->next==startPoint)
{
break;

}
else
{
temp=temp->next;
}
}
cout<<endl;
}
void destroyCircle(int n)
{
point * last=startPoint;


point * toDelete=startPoint;
for(int i=0;i<n;i++)
{
if(toDelete!=NULL)
{
point *temp=toDelete->next;
delete toDelete;
toDelete=temp;
}
}
startPoint=NULL;
}
int GetSafePosition(int n,int k)
{
point * temp=startPoint;
int total=n;
//int returnVal=startPoint->data;
point * toBeKilled=temp;
point * toBeReplaced;

while(total>1)
{
int needToSkipped=0;

do
{
if(needToSkipped>=k)
{
break;
}
else
{
if(toBeKilled->data>0)
{
needToSkipped++;
if(needToSkipped>=k)
break;
}
toBeKilled=toBeKilled->next;
}

}while(1);

needToSkipped=0;
toBeReplaced=toBeKilled->next;

do
{
if(needToSkipped>=k)
{
break;
}
else
{
if(toBeReplaced->data>0 && toBeReplaced!=toBeKilled)
{
//cout<<toBeReplaced->data<<endl;
needToSkipped++;
if(needToSkipped>=k)
break;
}
toBeReplaced=toBeReplaced->next;
}

}while(1);
//cout<<"To be killed "<<toBeKilled->data<<" to be replaced "<<toBeReplaced->data<<endl;
toBeKilled->data=toBeReplaced->data;
//returnVal=toBeKilled->data;
toBeReplaced->data=0;
total--;
//showAllNode();
toBeKilled=toBeKilled->next;
}

while(temp->data==0)
{
temp=temp->next;
}

//cout<<"show all the nodes"<<endl;
//showAllNode();


return (n-temp->data+1)%n+1;

}
void RomanRoulette(int n,int k)
{
if(n==1)
{cout<<1<<endl; return;}
if(k==0)
{cout<<1<<endl; return;}

createCircularList(n);
//showAllNode();
cout<<GetSafePosition(n,k)<<endl;
//showAllNode();
destroyCircle(n);
}

int main()
{
int n=0,k=0;
while(1)
{
cin>>n>>k;
if(n==0 && k==0)
{
break;
}
RomanRoulette(n,k);
}


return 0;
}