Croatian Open Competition in Informatics Contest #1 ~ #6
1. http://www.acmicpc.net/problem/2789 : Simply delete some letters.
strength(A) + strength(A+1) + ... + strength(B) = strength(B)-strength(A-1)
According to the description, N is divisible A-1, A-2, ... , 1
Lcm( x1, x2, x3, x4, ... ) = Lcm( ... Lcm ( Lcm ( Lcm( x1, x2 ) , x3), x4 ), ...)
A<B<10^17. So we can guess xn would be small.
1. http://www.acmicpc.net/problem/2783 : Easy
2. http://www.acmicpc.net/problem/2784 : Easy
Sort the prices by B(i)
As we calculate ith minimum cost, we consider two cases.
1) k which is min(A(k)) is in [1, i]
2) k is not in [1, i]
We can get the minimum cost by accumulating smaller A(i) from the back.
ith minimum cost = min( Sum of B(1 ~ i-1) + min(A(j)) , Sum of B(1 ~ i) + min(A(k)-B(k)) )
for j >= i, 1 <= k <= i .
1. http://www.acmicpc.net/problem/3076 : Easy
1. http://www.acmicpc.net/problem/3985 : Easy
BFS. care about changing of direction.
Minimum distance can be exist on the adjacent numbers.
Maximum distance is the difference betweein the smallest and the largest.
So 1) sort the numbers 2) choose N-K numbers from the beginning. 3) Add and delete one by one with heap or priority queue.
BFS. The point is that we don't have to visit the hurb which has been visited.
2. http://www.acmicpc.net/problem/5623 : Easy
3. http://www.acmicpc.net/problem/5624 : O(N^2)
From left to right, calculate the ways like pascal triangle.
d(i, j) = d(i-1, j-1) + d(i-1, j) + d(i-1, j+1)