UVa 357

#include<bits/stdc++.h>
#define ll long long

using namespace std;


ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;

 ll table[n+1][m];
 
 for (i=0; i<m; i++)
  table[0][i] = 1;

 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
  
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}


int main()
{
 ll a[] = {1,5,10,25,50};
 ll m = 5;
 ll n;
 
 while(cin>>n){
  ll ans;
  
  ans = count(a,m,n);
  
  if(ans>1){
   cout<<"There are "<<ans<<" ways to produce "<<n<<" cents change."<<'\n';
  }
  else cout<<"There is only "<<ans<<" way to produce "<<n<<" cents change."<<'\n';
 }
 return 0;
}

UVa 11137

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll a[21];
void precal(){

    for(int i=0; i< 21 ;i++) a[i]= ( (i+1) * (i+1) * (i+1) );

}

ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;
 ll table[n+1][m];

 for (i=0; i<m; i++)
  table[0][i] = 1;
 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}



int main(){

 precal();

//cout<<a[20];
 ll n,ans;

    while(cin >> n){

        ans = count(a,21,n);
        cout<< ans << '\n';
    }


 return 0;
}

UVa 674

#include<bits/stdc++.h>
#include<iomanip>
#define ll long long

using namespace std;


ll count( ll S[], ll m, ll n )
{
 ll i, j, x, y;

 ll table[n+1][m];
 
 for (i=0; i<m; i++)
  table[0][i] = 1;

 for (i = 1; i < n+1; i++)
 {
  for (j = 0; j < m; j++)
  {
  
   x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
   y = (j >= 1)? table[i][j-1]: 0;
   table[i][j] = x + y;
  }
 }
 return table[n][m-1];
}


int main()
{
 ll a[] = {1,5,10,25,50};
 ll m = 5;
 ll n;
 
 while(cin>>n){
  ll ans;
  
  ans = count(a,m,n);
  
  cout<<ans<<'\n';
 }
 return 0;
}

UVa 10130

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}

int main(){
 
 int t,n,sum;
 int p[1000+1],w[1000+1];
 int gn,g;
 
  cin>>t;
  while(t--){
   
   sum=0;
   cin>>n;
   for(int i=0; i<n; i++){
    
    cin>>p[i];
    cin>>w[i];
   }
   
   cin>>gn;
   for(int j=0; j<gn; j++){
    cin>>g;
    sum+=knap(g,w,p,n);
   }
   
   cout<<sum<<'\n';
  }
 
 
 return 0;
}

UVa 562

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}

int main(){
 
 int t,n,w,d,ans,sum;
 
 while(cin>>t){
  
  while(t--){
   
   sum=0;
   cin>>n;
   int wt[100+1],val[100+1];
   memset(wt,0,101);
   memset(val,0,101);
   
   for(int i=0; i<n; i++){
    cin>>wt[i];
    val[i]=wt[i];
    sum+=wt[i];
   }
  
   w = sum/2;
   d = knap(w,wt,val,n);
   ans=sum - 2*d;
   cout<<ans<<'\n';
   
  }
 }
 
 return 0;
}

UVa 10664

#include<bits/stdc++.h>

using namespace std;

int knap(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}


int main(){

 string n;
 int m,sum,d,w,ans;
 int wt[21],val[21];
 
  cin>>m;
  getchar();
  while(m--){
   
   
   getline(cin,n);
   int num;
   istringstream str(n);
   
   int i=0; sum=0;
   while(str >> num){
    sum+=num;
    wt[i]=val[i]=num;
    i++;
    
   }
   
  
   
   if(sum%2==1){
    cout<<"NO"<<'\n';
   }
   else {
    
    w= sum / 2;
    d= knap(w,wt,val,i);
    
    if(d==w) cout<<"YES"<<'\n';
    else cout<<"NO"<<'\n';

   }
   
   }

 return 0;
}

UVa 12555

#include<bits/stdc++.h>

using namespace std;

int main()
{
 int t,sz,a;
 int kase=1;
 double res;
 string inp;

 cin>>t;

 while(t--){
  
  res=0;
  cin>>a;
  cin>>inp;
  
  sz=inp.size();
  
  if(sz <= 4) res = a * .5;
  else res = (inp[3]-'0') * .05 + a * .5;
  
  cout<<"Case "<<kase<<": ";
  cout<<res<<endl;
  kase++;

 }

 return 0;

}

//translation chinese to english :D
//.5kg =  jin 
//.05 = two
// so "5 jin 2 two" consider it :)

UVa 10105

#include<bits/stdc++.h>

using namespace std;

int main()
{
 int n,k;
 int a[15];
 a[0]=1;

 for(int i=1; i<15; i++)
  a[i]=a[i-1]*i;

 while(cin>>n>>k)
 {
  int result=a[n];

  while(k--)
  {
   int x;
   cin>>x;
   result/=a[x];
  }

  cout<<result<<endl;
 }
 return 0;
}

UVa 494

#include<bits/stdc++.h>

using namespace std;

int main()
{
 string l,ll;

 while(getline(cin,l) && getline(cin,ll))
 {
  
  set<string>s1,s2;
  string num;
  istringstream str1(l.c_str());

  while(str1>>num)
  {
   s1.insert(num);
  }

  istringstream str2(ll.c_str());

  while(str2>>num)
  {
   s2.insert(num);
  }

  set<string>:: iterator it,ix;

  int ab=0;

  for(it=s1.begin(); it !=s1.end(); it++)
  {
   ix=s2.find(*it);
   if(ix!=s2.end()) ab++;
  }

  int ba=0;

  for(it=s2.begin(); it!=s2.end(); it++)
  {
   ix=s1.find(*it);
   if(ix!=s1.end()) ba++;
  }

   if(ab==0 && ba==0)  cout<<"A and B are disjoint"<<endl;
    else if(ab==ba && (ab==s1.size() && ba==s2.size()))  cout << "A equals B" << endl;
     else if(ab==s1.size() && (s1.size()<s2.size()))  cout << "A is a proper subset of B" << endl;
      else if(ba==s2.size() && (s2.size()<s1.size()))  cout << "B is a proper subset of A" << endl;
       else cout << "I'm confused!" << endl; 

 }

 return 0;
}

UVa 694

#include<bits/stdc++.h>
#define ll long long
#define kase(i) printf("Case %d: ",i)

using namespace std;

int main()
{
 ll a,b,c,i;
 int j=1;

 while(cin>>a>>b)
 {
  c=a;
  if(a<0 && b<0) break;

  for(i=1;;i++)
  {
   if(a==1) break;

   if(a%2==0) a=a/2;
   else a=3*a+1;

   if(a>b) break;
  }

  kase(j);
  cout<<"A = "<<c<<", Limit = "<<b<<", number of terms = "<<i<<endl;
  j++;

 }

 return 0;
}

UVa 11715

#include<bits/stdc++.h>

using namespace std;

int main() {
  int T;
  int c = 0;
  double u, v, t, a, s;

  while (cin >> T) {
    if (T == 0)
      break;

    c++;

    cout << "Case " << c << ": ";

    switch (T) {
      case 1:
        cin >> u >> v >> t;
        a = (v - u) / t;
        s = u * t + 0.5 * a * t * t;
        cout << setprecision(3) << fixed << s << " " << a << endl;
        break;
      case 2:
        cin >> u >> v >> a;
        t = (v - u) / a;
        s = u * t + 0.5 * a * t * t;
        cout << setprecision(3) << fixed  << s << " " << t << endl;
        break;
      case 3:
        cin >> u >> a >> s;
        t = (-u + sqrt(u * u + 2 * a * s)) / a;
        v = a * t + u;
        cout << setprecision(3) << fixed  << v << " " << t << endl;
        break;
      case 4:
        cin >> v >> a >> s;
        t = (-v + sqrt(v * v - 2 * a * s)) / -a;
        u = v - a * t;
        cout << setprecision(3) << fixed  << u << " " << t << endl;
        break;
    }
  }

  return 0;
}

UVa 1230

import java.util.Scanner;
import java.math.BigInteger;

class Main { 

  public static void main(String args[])
   {

    Scanner sc = new Scanner(System.in);
    int c = sc.nextInt();

    while (c-- > 0) {

         BigInteger x = BigInteger.valueOf(sc.nextInt()); 
         BigInteger y = BigInteger.valueOf(sc.nextInt()); 
         BigInteger n = BigInteger.valueOf(sc.nextInt()); 
         System.out.println(x.modPow(y, n)); 
   }
  } 
}

UVa 343

import java.io.*;
import java.util.*;
import java.math.*;

class Main{

  void sol()
  {
   Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

    while(in.hasNext())
    {
      String a=in.next();
      String b=in.next();
      BigInteger b1,b2;
      boolean f=false;

       for(int i=2; i<=36; i++)
       {
        try{
         b1=new BigInteger(a,i);
         }

         catch(Exception e)
         {
          continue;
          }

          for(int j=2; j<=36; j++)
          {
           try{
            b2= new BigInteger(b,j);
           }
           catch(Exception e)
           {
            continue;
           }

           if(b1.compareTo(b2)==0){
            f=true;
            System.out.println(a + " (base " + i + ") = " + b + " (base " + j + ")");
            break;

           }

          }

          if(f) break;
        }
         if(!f) System.out.println(a + " is not equal to " + b + " in any base 2..36");


     }


   }


   public static void main(String args[])
   {
    Main uva343 = new Main();
    uva343.sol();
   }


 }

UVa 10302

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{ ll a[50005];
 a[1]=1;
 for(ll i=2; i<=50005; i++)
 {
  a[i]=a[i-1]+(i*i*i);
 }

 ll n;
 while(cin>>n)
 {
  cout<<a[n]<<endl;
 }
 return 0;
}

UVa 392

#include<bits/stdc++.h>
#define M 9

using namespace std;

int main()
{
 int a[M],fr,i;

    while(cin>>a[0])
    {
        for(i=1;i<M;i++)
            cin>>a[i];

        fr=8;
        for(i=0;i<M;i++)
            if(a[i]!=0)
                {
                    fr=i;
                    break;
                }

        if(fr==8)
            cout<<a[fr];
        else
        {
            if(a[fr]==-1)
                cout<<"-";
            else if(a[fr]==1)
                cout<<"";
            else
                cout<<a[fr];
            cout<<"x";

            if(fr!=7)
                cout<<"^"<<8-fr;

            for(i=fr+1;i<M;i++)
                if(a[i]!=0)
                    {
                        if(a[i]<0)
                            cout<<" - ";
                        else
                            cout<<" + ";

                        if((a[i]!=-1 && a[i]!=1) || i==8)
                            {

                                if(a[i]<0)
                                    cout<<a[i]*(-1);
                                else
                                    cout<<a[i];
                            }

                        if(i!=8)
                            cout<<"x";
                        if(i!=7 && i!=8)
                            cout<<"^"<<8-i;
                    }
        }
        cout<<endl;

}
 return 0;
}

UVa 913

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{

 long long N,x;

 while(cin>>N)
 {
  x = 2*(((N/2)+1)*((N/2)+1)) -3;
  cout<<3*x<<endl;
 }

 return 0;
}

UVa 10499

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{

 ll n,p;

 while(cin>>n)
 {
  if(n<0) break;
  p=(n*100)/4;
  if(n==1) cout<<0<<"%"<<endl;
  else cout<<p<<"%"<<endl;
 }

 return 0;
}

UVa 10170

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
 ll s,d,n,i;

 while(cin>>s>>d)
 {
  n=0;
  for(i=s;;i++){

   n+=i;
   if(n>d || n==d) {
    cout<<i<<endl;
    break;
   }
  }
 }
 return 0;
}

UVa 12027

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
 
 string a;
 while(cin>>a)
 {
  if(a=="0") break;
  int l,num;

  l=a.length();
  num=a[0]-'0';
  if(l>1 && l%2==0) num = num*10 + a[1]-'0';

  l = (l-1)/2;
  cout<<int(sqrt(num));

  for(int i=0; i<l; i++){
   cout<<0;
  }
  cout<<endl;
  
 }

 return 0;

}

UVa 371 - Ackermann Functions

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
 ll x, y;
 
 int j,k;
 
 while(cin>>x>>y)
 {
   if(x==0 || y==0) break;
   
   vector<ll>a;
   vector<ll>b;
   vector<ll>c;
   
  j=k=0;
  if(x>y) swap(x,y);
  
  for(ll i=x; i<=y; i++ )
  {
   
   ll ti=0;
   ll tn=i;
   
   if(i==1)
   {
    ti=3;
   }
   
   else {
    while(tn!=1)
   {
    if(tn%2==0){
      tn= tn/2;
      ti++;
    }
    else {
     tn=3*tn+1;
     ti++;
    }
   }
   }
   
   a.push_back(i);
   b.push_back(ti);
   c.push_back(ti);
   
  }
   sort(b.begin(),b.end());
  
   for(ll l=0; l<c.size(); l++)
   {
    if(b[b.size()-1]==c[l]) {
     
     cout<<"Between "<<x<<" and "<<y<<", "<<a[l];
     cout<<" generates the longest sequence of "<<b[b.size()-1]<<" values."<<endl;
     break;
    }
   }
 
 }
 return 0;
}