Tostlar#510

Tostlar (Həll təhlili)

Əgər $n = 0$ n = 0 olarsa, cavab $0$ -dır.

Əgər tostların sayı $n$ tavaların tutumundan çox deyilsə $k (n \leq k)$ k~(n \le k), bütün tostları hər iki tərəfdən qızartmaq üçün $4$ dəqiqə tələb olunur.

Hər tost hər iki tərəfdən qızardılmalıdırsa, ümumilikdə $⌈ 2 n / k ⌉$ qızartma lazımdır. Hər qızartma (tavaya eyni anda $k$ tost yerləşdirə bilmək) $2$ dəqiqə davam edir.

Nəticə etibarilə, əgər $n > k$ n > k olarsa, bütün tostları qızartmaq üçün minimal vaxt $2 \cdot ⌈ 2 n / k ⌉$ 2 \cdot \lceil 2n / k \rceil dəqiqəyə bərabərdir.

Nümunə

Tutaq ki, $n = 3$ n = 3 tost var və tava eyni anda $k = 2$ k = 2 tost yerləşdirə bilir. Tostların tərəflərini $1 a, 1 b, 2 a, 2 b, 3 a, 3 b$ 1a, 1b, 2a, 2b, 3a, 3b kimi ifadə edək.

Beləliklə bütün $6$ tərəfi $6$ dəqiqədə qızartmaq mümkündür:

Birinci qızartma: $1 a$ və $2 a - 2$ 2a - 2 dəqiqə;
İkinci qızartma: $1 b$ və $3 a - 2$ 3a - 2 dəqiqə;
Üçüncü qızartma: $2 b$ və $3 b - 2$ 3b - 2 dəqiqə;

Cəmi: $3$ qızartma hər biri $2$ dəqiqədən, yəni $6$ dəqiqə.

Alqoritmin reallaşdırılması

Giriş məlumatlarını oxuyuruq.

scanf("%d %d",&n,&k);

Əgər $n = 0$ n = 0 olarsa, cavab $0$ -dır.

if (!n) res = 0; else

Əgər tostların sayı tavaların tutumundan çox deyilsə, onları qızartmaq üçün $4$ dəqiqə lazımdır.

if (n <= k) res = 4; else
{

Hər tost hər iki tərəfdən qızardılmalıdır, yəni ümumilikdə $⌈ 2 n / k ⌉$ tərəf qızardılmalıdır. Bir qızartma (tavada yerləşdirilə bilən tostların sayından asılı olmayaraq) $2$ dəqiqə davam edir.

  res = 2 * n / k;
  if (2 * n % k) res++;
  res *= 2;
}

Cavabı çap edirik.

printf("%d\n",res);

Java da reallaşdırma

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int k = con.nextInt();
    int res;
  
    if (n == 0) res = 0; else    
    if (n <= k) res = 4; else
    {
      res = 2 * n / k;
      if (2 * n % k > 0) res++;
      res *= 2;
    }        
    System.out.println(res);
    con.close();
  }
}

Java