uva 247 - Calling Circles

/*

Problem link
Type: Graph, DFS, Strongly connected components
Algorithm: Tarjan
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 50;

uva 11799 - Horror Dash

/*

Problem link

*/

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
 int ntest, n;
 cin >> ntest;
 for (int test=1; test<=ntest; test++)
 {
  cin >> n;
  int max = 0, value;
  for (int i=1; i<=n; i++) 
  {
   cin >> value;
   if (value>max) max = value;
  }
  printf("Case %d: %d\n",test, max);
 }
}

uva 1213 - Sum of Different Primes

/*

Problem link
Type: DP, Prime
Algorithm:
 Let f(i,j,k) is the number of way to split number i into j prime numbers 
 using the first k prime numbers
 
 If we decide to choose the kth prime in the sum, then the number of ways
 is f(i-Prime[k],j-1,k-1), that is, the number of way to split number
 i-Prime[k] into j-1 prime numbers (and the kth prime number) using 
 the first k-1 prime numbers (cannot choose Prime[k] again)

uva 10664 - Luggage

/*

Problem link

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
//-----------------------------
void readfile();
bool solve();

uva 11727 - Cost Cutting

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

int main() {
 int a,b,c,t;
 cin >> t;
 for (int test = 1; test<=t; test++)
 {
  cin >> a >> b >> c;
  printf("Case %d: %d\n",test,a+b+c-max(c,max(a,b))-min(c,min(a,b)));
 }
 return 0;
}

uva 315 - Network

/*

Problem link
Type: Graph, DFS Variant
Algorithm:
 Use the DFS to search for articulation points
 low[u]: the lowest num[v] that u can reach
 num[u]: the order in the DFS when u is visit for the first time
 if low[v]>=num[u], v is a child of u, if v cannot reach any vertex lower than u without
 going through u, this mean when u is remove, v cannot reach any vertex lower than u
 hence u is the articulation point.
*/

uva 10667 - Largest Block

/*
Problem link
Type: DP, data structure
Algorithm: I use the stack in the problem, with this I can solve it in O(n^2)
 Let h[i][j] be the height of the consecutive comlumn of 0 at (i,j)
 Let l[i][j] is the index left most element of (i,j) that from h[i][l[i][j]] to h[i][j]
  is all >= h[i][j]
 Let r[i][j] is the index right most element of (i,j) that from h[i][j] to h[i][r[i][j]]
  is all >= h[i][j]
 Find max of (j-l[i][j]+r[i][j]-j+1)*h[i][j] for all i,j
 l and r are calculated in O(n^2) by using the stack
*/

uva 787 - Maximum Sub-sequence Product

/*

Problem link
Type: DP, BigNum
Algorithm:
 Just go for an O(n^2) to calculate each product from i to j.
 The bignum is a bit tricky, I build a class for BigNum here so it can be processed easily.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;

uva 168 - Theseus and the Minotaur

/*

Problem link
Type: Graph, graph traversal
Algorithm: 
 Just go but aware of the order of the vertex before reaching it.
 Never go back to the previous edge because that's where Thesus stand
 Every k vertex, lit it up
*/

uva 11559 - Event Planning

/*

Problem link
Easy Adhoc
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;

int n,b,h,w;

int main() {
 while (!cin.eof())
 {
  int m = 2000000000;
  cin >> n >> b >> h >> w;
  if (cin.eof()) break;
  for (int i=1; i<=h; i++)
  {
   int p,k;
   cin >> p;
   for (int j=1; j<=w; j++)
   {
    cin >> k;
    if (k>=n && n*p<m) m = n*p;
   }
   
  }
  if (m<=b) cout << m << endl;
  else cout << "stay home" << endl;
 }
 return 0;
}

uva 118 - Mutant Flatworld Explorers

/*

Problem link
Algorithm:
 - Just go and take note of the grid where the robots fall.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 5000;

uva 10534 - Wavio Sequence

/*

Problem link
Type: DP, LIS, LDS
Algorithm: 
 - Find the LIS and save the LIS til index i in array d1.
 - Find the LDS by do the LIS backward and save the LDS till index i in array d2.
 - For each element, consider it as the top element of the waivo.
*/

uva 10131 - Is Bigger Smarter?

/*

Problem link
- This problem is a good example of both LIS and LCS. I solved this problem
using the LCS DP (Longest Common sub-Sequence).
** Algorithm:
- The algorithm for the LCS is simple. 
- First we sort the list of the cows in increasing 
order of weight, save their corresponding ID in array l1.
- Second, sort the list of the cows in decreasing 
order of smart, save their corresponding ID in array l2.
- Find the LCS of l1 and l2.

uva 437 - The Tower of Babylon

/*

Problem link

This problem can be attacked in many solution. I choose the DP solution.

It is a bit similar to the LIS.

uva 481 - What Goes Up

/*

Problem link

This is a must-use O(n.log(k)) LIS. It is the same as the uva 231 problem, a little bit troublesome when trace back for the result.

Go to this link to see more detail on O(n.log(k)) algorithm

for LIS at uva 231: http://nminhtu94.blogspot.com/2012/11/uva-231-testing-catcher-version-2.html

*/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 100000;
//----------------------------
class element { public: int value; int index;};

uva 231 - Testing the CATCHER (version 2)

Problem link

/*

This is a more effective algorithm, its complexity is O(n.log(k)) where k is the length of the LIS

- The lis array contains the sequence.

- For each element of the array A, use binary search for the suitable position for that element in the lis array so that this array still a non-Decreasing array, call that position pos.

- Replace lis[pos] with A[i] for a better LDS later (if it has). This greedy step is important!

- If there is no suitable position for A[i], then A[i] must be the next smallest value in lis, hence add A[i] to lis.

- The largest number of elements of lis during this procedure is the result.

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 100000;
//-----------------------------
int a[maxn],lis[maxn];
int n,k;

uva 231 - Testing the CATCHER

Problem link

/*

This is the lazy DP version, the complexity of this approach is O(n^2). But it still got AC for this problem.

l[i] is the length of the LDS(LIS) ends at i. Therefor:

l[i] = 1 as initial.

l[i] = max(l[i], l[j] + 1 for j from 1 to i-1 and a[j]>=a[i])

Note: This problem is non-Decreasing Subsequence.

*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 10000;
//-----------------------------
int a[maxn],l[maxn];
int n,k;

uva 11450 - Wedding shopping

Problem link

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxm = 210;
const int maxc = 25;
//-----------------------------------
int price[maxc][maxc];
bool reachable[maxc][maxm];
int m,c;

uva 406 - Prime Cuts

Types: Number theory, primes number, sieve...

Problem link

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 1010;
//------------------------------------
int a[maxn];
bool isPrime[maxn];
int n,c;

uva 11547 - Automatic Answer

Problem link

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

int main() {
 int ntest,n;
 cin >> ntest;
 for (int test=1; test<=ntest; test++)
 {
  cin >> n;
  int result = (n*63 + 7492)*5 - 498;
  result /= 10;
  cout << abs(result%10) << endl;
 }
 return 0;
}

uva 471 - Magic Numbers

I still dont know why this approach got AC. Try N = 5 and it's 

definitely got TLE. I tried to approach this problem by recursive backtracking but it got TLE, although it is faster for some single test cases.

Problem link

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const long long maxn = 9876543210;

uva 386 - Perfect Cubes

Problem link

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const double eps = 1E-9;
//-----------------------------
class ans { public: int a; int b; int c; int d;};
//-----------------------------
ans kq[225];

uva 260 - Il Gioco dell'X

Problem link

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 210;
const int dx[6] = {0,-1,-1,0,1,1};
const int dy[6] = {-1,-1,0,1,1,0};
//---------------------------------
char a[maxn][maxn];
bool fre[maxn][maxn];
int qx[maxn*maxn*maxn];
int qy[maxn*maxn*maxn];
int n;

uva 11498 - Division of Nlogonia

Problem link

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;

int main() {
 int k;
 cin >> k;
 while (k!=0) 
 {
  int n,m,x,y;
  cin >> n >> m;
  for (int i=1; i<=k; i++)
  {
   cin >> x >> y;
   int xI,yI;
   xI = x-n;
   yI = y-m;
   if (xI>0 && yI>0) cout << "NE" << endl;
   else if (xI>0 && yI<0) cout << "SE" << endl;
   else if (xI<0 && yI<0) cout << "SO" << endl;
   else if (xI<0 && yI>0) cout << "NO" << endl;
   else cout << "divisa" << endl;
  }
  cin >> k;
 }
 return 0;
}