Friday, August 30, 2013

COCI 2012/2013 #1 ~ #6

Croatian Open Competition in Informatics Contest #1 ~ #6

#1
1. http://www.acmicpc.net/problem/2789 : Simply delete some letters.
5. http://www.acmicpc.net/problem/2793
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.

#2
1. http://www.acmicpc.net/problem/2783 : Easy
2. http://www.acmicpc.net/problem/2784 : Easy
4. http://www.acmicpc.net/problem/2786
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 .

#3
1. http://www.acmicpc.net/problem/3076 : Easy

#4
1. http://www.acmicpc.net/problem/3985 : Easy
3. http://www.acmicpc.net/problem/3987
BFS. care about changing of direction.
4. http://www.acmicpc.net/problem/3988
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.

#5
4. http://www.acmicpc.net/problem/5214
BFS. The point is that we don't have to visit the hurb which has been visited.

#6
2. http://www.acmicpc.net/problem/5623 : Easy
3. http://www.acmicpc.net/problem/5624 : O(N^2)
5. http://www.acmicpc.net/problem/5626
Dynamic Programming.
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)

No comments:

Post a Comment