Coding Exercise – Timus Online Judge – 1820. Ural Steaks, C/C++ solution

This problem is from Timus Online Judge. The original problem description can be found here.

There are k   steaks that can be cooked at the same time. So if , it has to take 2 minutes to cook all steaks.

The algorithm should be greedy so that asap one side of steak is cooked.

Recursion Analysis (Decomposition)

We can decompose the problem into smaller ones by using recursive formula. Suppose we use to denote the answer for the time needed to cook n steaks with the fact that at most k steaks can be cooked at the same time. We can come up with the following relations (in C++ solution).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
 
using namespace std;
 
int f(int n, int k) {
    if (n <= k) return 2;     
    // n / k pairs of two mins     
    if (n % k == 0) return n / k * 2;     
    if (n > k && n < 2 * k) {         
        if (n - k > k / 2) {
            return 4;
        }
        return 3;
    }
    // takes 2 mins to cook k steaks
    return f(n - k, k) + 2;
}
 
int main() {
    int n, k;
    cin >> n >> k;
    cout << f(n, k);
    return 0;
}

#include <iostream>

using namespace std;

int f(int n, int k) {
    if (n <= k) return 2;     
    // n / k pairs of two mins     
    if (n % k == 0) return n / k * 2;     
    if (n > k && n < 2 * k) {         
        if (n - k > k / 2) {
            return 4;
        }
        return 3;
    }
    // takes 2 mins to cook k steaks
    return f(n - k, k) + 2;
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << f(n, k);
    return 0;
}

It is easy to understand that the cases of and (n divisible by k).  for n is between   k    and   2 * k  we should consider two situations. If the remainder   n – k    is less than half of k  , in this case, it takes 3 mins to cook all (otherwise 4 mins). For example,

There are three steaks,  a, b and c. a1, b1 and c1 are first side of steaks, a2, b2 and c2 are second side of streaks. The wrong cooking sequence is

• 1s: a1,b1
• 2s:a2,b2
• 3s:c1
• 4s:c2

The correct order should be:

• 1s:a1,b1
• 2s:a2,c1
• 3s:b2,c2

In other cases, the recursive formula is  which reduces the size of problem (k steaks are cooked in two minutes).

The Pure Math Solution.

The above solution shows you how to analyse the problem into a smaller one (decomposition). It is an accepted solution since the problem input size is small (less than 1000).  However, it is not the most efficient solution.

The total sides of steaks are and each time it cooks  k  steaks at most, therefore, the answer is the ceiling function of . Of course, when ,  it still takes 2 minutes to cook (the exception case).

1
2
3
4
5
6
7
8
9
10

#include <iostream>
 
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
    cout << (n<k?2:2*n%k?2*n/k+1:2*n/k);
    return 0;
}

#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    cout << (n<k?2:2*n%k?2*n/k+1:2*n/k);
    return 0;
}

–EOF (The Ultimate Computing & Technology Blog) —