uva 10819 - Trouble of 13-Dots

 1 /*
 2  Problem link
 3  Type: DP, knapsack(0/1)
 4  */

uva 166 - Making Change

  1 /*
  2  Problem link
  3  Type: DP
  4  Algorithm:

uva 147 - Dollars

 1 /*
 2  Problem link
 3  Type: DP
 4  Algorithm:

uva 352 - The Seasonal War

/*

Problem link

Type: Graph, flood fill

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <cstdlib>
 6  using namespace std;

uva 11995 - I Can Guess the Data Structure!

/*

Problem link

Type: Data structure

*/  

  1  #include <iostream>
  2  #include <cstdio>
  3  #include <cstring>
  4  #include <cmath>
  5  #include <cstdlib>
  6  #include <vector>
  7  #include <queue>
  8  #include <stack>

uva 10954 - Add All

/*

Problem link

Type: Adhoc - greedy, Data structure - priority queue

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <vector>
 6  #include <queue>

uva 11926 - Multitasking

/*

Problem link

Type: Adhoc, brute-force

*/

 1  #include <iostream>

 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <cstdlib>
 6  #include <vector>
 7  using namespace std;
 8  const int maxn = 1000010;

uva 11402 - Ahoy, Pirates!

  1 /*
  2  Problem link
  3  Type: Data structure - segment tree
  4  Algorithm:

uva 11235 - Frequent values

//============================================================================
// Name        : 11235.cpp
// Author      : Mr Tu
// Version     :
// Copyright   : Your copyright notice
// Description : Uva 11235 - Frequent values in C++, Ansi-style
// Problem link
// Algorithm: Data structure - Segment tree
//============================================================================

uva 11631 - Dark roads

/*
Problem link
Type: Graph
Algorithm: Kruskal, minimum spanning tree, using priority queue
*/
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;
const int maxn = 200010;

uva 10616 - Divisible Group Sums

/*
Problem link
Type: DP, Mathematics
Algorithm:
 Let f(i,j,k) is the number of ways to choose i elements from a[1..j] so that
 their sum divides d gives the remainder of k. 

uva 473 - Raucous Rockers

/*
Problem link
Type: DP
Algorithm:
 Let f(i,j,k) be the largest amount of songs from 1 to k can be written into 
 the disks from 1 to i with disk i having space j

The Fibonacci Numbers

• The rabbits growth problem:

Fibonacci's book Liber Abaci written in 1202 concerned about the growth of the number of rabbits in a certain area. The problem is: A young pair of rabbits, one of each sex, is placed on an island. Assuming that rabbits do not breed until they are two months old and after they are two months old, each pair of rabbits produces another pair each month, how many pairs are there after n months?

Let f(n) be the number of rabbits after n months. We have f(1) = 1 because only the original pair is on the island after one month. As this pair does not breed during the second month, f(2) = 1. To find the number of pairs after n months, add the number on the island the previous month, f(n-1), to the number of newborn pairs, which equals to f(n-2), because each newborn pair comes from a pair at least two months old. This leads to the following definition.

• Definition: 

The Fibonacci sequence is defined recursively by f(1) = 1, f(2) = 1, and f(n) = f(n-1) + f(n-2) for n>=3. The terms of this sequence are called the Fibonacci Numbers

uva 12015 - Google is Feeling Lucky

/*

Problem link

*/

#include <iostream>
#include <cstdio>
using namespace std;
const int n = 20;

class url {
public:
 string link;
 int value;
};

url a[n];

int main() {
 int ntest;
 string line;
 cin >> ntest;
 for (int test=1; test<=ntest; test++)
 {
  printf("Case #%d:\n",test);
  for (int i=1; i<=10; i++) 
  {
   cin >> a[i].link;
   cin >> a[i].value;
  }
  int themax = 0;
  for (int i=1; i<=n; i++) themax = a[i].value>themax ? a[i].value : themax;
  for (int i =1; i<=n; i++)
   if (a[i].value==themax) cout << a[i].link << endl;
 } 
 return 0;
}




uva 11942 - Lumberjack Sequencing

/*

Problem link

*/

#include <iostream>
#include <cstdio>
using namespace std;
const int n = 10;

int a[n];

int main() {
 int ntest;
 cin >> ntest;
 cout << "Lumberjacks:" << endl;
 for (int test=1; test<=ntest; test++)
 {
  for (int i=1; i<=n; i++) cin >> a[i];
  int tmp = a[2]-a[1];
  int i;
  for (i=3; i<=n; i++)
   if ((a[i]-a[i-1])*tmp<=0)
   {
    cout << "Unordered" << endl;
    break;
   }
  if (i==n+1) cout << "Ordered" << endl;
 }
 return 0;
}




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;