Çəkimlər#1993

Çəkimlər (Həll təhlili)

Bütün şarları üç mümkün olduğu qədər bərabər sayda qrupa bölək. Əgər $n$ ədədi $3$ -ə bölünmürsə, o zaman qrupların ölçüləri bir şardan artıq fərqlənməyəcək. Eyni ölçülü iki qrupu tərəzilərin həqiqi yerlərinə qoyacağıq. Bir çəkmə nəticəsində ağır şarın hansı üç qrupda olduğunu müəyyən edirik.

Beləliklə, $n$ şarlarının olduğu problemi bir çəkmə ilə ən pis halda $⌈ n /3 ⌉$ şarları olan problemə endiririk. Demək, ağır şarın tam şəkildə tapılması üçün $⌈ l o g_{3} n ⌉$ ⌈log_3n⌉ çəkmələr yetərlidir.

İkinci həll. $p$ — $3^{p} 0 ˘ 03 c n$ 3^p \u003c n qeyri-bərabərliyini əməl edən ən böyük dərəcə olsun. O zaman ağır şarın tam şəkildə tapılması üçün dəyişən çəkmələrin minimum miqdarı $p + 1$ p + 1-dir.

Nümunə

Üç şar üçün bir çəkmə yetərlidir. Əgər tərəzilər tarazlıqdadırsa, demək, daha ağır şar tərəzilərə qoyulmamışdır.

$9$ şar vəziyyətində onları $3$ girovda $3$ şar ilə böləcəyik. Hər tərəzinin həqiqi yerinə bir qrupu qoyaraq, bir çəkmə ilə hansı qrupda ağır şarın olduğunu müəyyən edirik.

Əgər $8$ şar varsa, onları $3, 3$ və $2$ şar ilə üç qrupa böləcəyik. Burada tərəzinin həqiqi yerlərinə $3$ şarı olan iki qrupu qoyacağıq.

Alqoritmin realizasiyası

Şarların miqdarı $n$ -i oxuyuruq.

scanf("%d",&n);

Cavabı hesablayır və çıxış edirik.

res = ceil(log(n) / log(3));
printf("%.0lf\n",res);

Alqoritmin realizasiyası – dövri

Şarların miqdarı $n$ -i oxuyuruq.

scanf("%d",&n);

Cavabı hesablayır və çıxış edirik.

res = 0; p = 1;
while (p < n)
{
  p = p * 3;
  res++;
}

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

C++

Java realizasiyası

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();   
    double res = Math.ceil(Math.log(n) / Math.log(3));
    System.out.printf("%.0f\n",res);
    con.close();
  }
}

Java

Python realizasiyası

Şarların miqdarı $n$ -i oxuyuruq.

n = int(input())

Cavabı hesablayır və çıxış edirik.

print(int(math.ceil(math.log(n) / math.log(3))))