UVA 326

http://uva.onlinejudge.org/external/3/326.html

using namespace std;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<limits>
#include<cmath>
#include<queue>
#include<map>
#define LLU long long unsigned int
#define LLD long long double
#define FOR(i,N) for(int i=0;i<(N);i++)
int main()
{
    int N,t,k;
    while(cin>>N && N)
    {
        vector<int> inp;
        FOR(i,N)
        {
            cin>>t;
            inp.push_back(t);
        }
        cin>>k;
        vector<int> res;
        res.push_back(inp[inp.size()-1]);
        for(int i=0;i<N-1;i++)
        {
            for(int j=N-1;j>i;j–)
            {
                inp[j]=inp[j]-inp[j-1];
            }
            res.push_back(inp[N-1]);
        }
        for(int j=0;j<k;j++)
        {
            for(int i=res.size()-2;i>=0;i–)
            {
                res[i]=res[i]+res[i+1];
            }
        }
        printf(“Term %d of the sequence is %d\n”,N+k,res[0]);
    }
}

UVA 507

http://uva.onlinejudge.org/external/5/507.html

#include<iostream>
using namespace std;

void max(int a[],int n,int j)
{
 int m_s=1,m_e=2,m=a[0],s=a[0],st=0;
 
 for (int i=1;i<n;i++)
 {
  if (s>=0)
   s+=a[i];
  else
  {
   st=i;
   s=a[i];
  }
  
  if (s>m)
  {
   m=s;
   m_s=st+1;
   m_e=i+2;
  }
  else if (s==m)
  {
   if (i-st > m_e-m_s)
   {
    m=s;
    m_s=st+1;
    m_e=i+2;
   }
   else if (i-st == m_e-m_s)
   { 
    if (st < m_s)
    {
     m=s;
     m_s=st+1;
     m_e=i+2;
    }
   }
  }
 }
 
 if (m>=0)
  cout<<"The nicest part of route "<<j<<" is between stops "<<m_s<<" and "<<m_e<<endl;
 else
  cout<<"Route "<<j<<" has no nice parts\n";
}

int main()
{
 int n,s;
 cin>>n;
 for (int i=1;i<=n;i++)
 {
  cin>>s;
  int a[s-1];
  for (int j=0;j<s-1;j++)
   cin>>a[j];
  
  max(a,s-1,i);
 }
}

UVA 481

http://uva.onlinejudge.org/external/4/481.html

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
  if (a[b.back()] < a[i]) 
                {
   p[i] = b.back();
   b.push_back(i);
   continue;
  }
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
                {
   int c = (u + v) / 2;
   if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
                // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
                {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[100000],i=0;
 
 while(scanf("%d",&a[i])!=EOF)
  i++;
 vector<int> seq(a, a+i); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
        printf("%d\n-\n",lis.size());
 for (size_t i = 0; i < lis.size(); i++)
  printf("%d\n", seq[lis[i]]);   
 
 return 0;
}

UVA 616

http://uva.onlinejudge.org/external/6/616.html

#include<iostream>
using namespace std;

int no(int c);
void print(int p,int n);

int main()
{
 int c,p;

 cin>>c;
 while(c>0)
 {
  p=no(c);
  print(p,c);
  cin>>c;
 }
}

void print(int p,int n)
{
 if(p>0)
 {
  cout<<n<<" coconuts, "<<p<<" people and 1 monkey\n";
 }
 else
  cout<<n<<" coconuts, no solution\n";
}


int no(int c)
{
 int j,a,b,d;

 for(int i=10;i>1;i--)
 {
  if(c%i==1)
  {
   b=c;
   a=1;
   for(j=1;j<=i;j++)
   {
    if (b%i==1)
    {
     b=((b-1)/i)*(i-1);
    }
    else
    {
     a=0;
     break;
    }
   }
   if ((a==1)&&(b%i==0))
   {
    return i;
   }
   else if ((a==0)&&(i==2))
    return -1;
  }
 }
 return -1;
}