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