Tanrım! Məni xilas et#1575

Tanrım! Məni xilas et (Həll təhlili)

Gözlənilan $P$ vaxtını təyin edək, hansı ki təhlukəsiz yerə otağı tərk etmək imkanını verir. Bu vaxt aşağıdakı kimi ifadə edilir:

P = i = 1 \sum n p_{i} \cdot t_{i},

P = \sum_{i=1}^n p_i \cdot t_i,

burada $t_{i}$ t_i — i-ci qapını seçdikdə təhlukəsiz yerə çıxma vaxtıdır. Aydındır ki, $t_{i} = x_{i}$ t_i = x_i əgər $x_{i} > 0$ x_i > 0; əgər $x_{i} < 0$ x_i < 0, tərk etmək üçün əvvəlcə $- x_{i}$ -x_i vaxtını otağa qayıtmağa sərf etməli və sonra çıxışa yenidən cəhd üçün $P$ vaxtını sərf etməli. Amma, bu halda $t_{i} = - x_{i} + P$ t_i = -x_i + P.

Nəticədə isə $P$ üçün xətti tənlik əldə edirik. Bu tənliyi qurmaq və həll etmək $O (n)$ vaxt aparır, burada $n$ — qapıların sayıdır.

Nümunə

Birinci testi nəzərdən keçirək:

P = 0.33 * 2 + 0.33 * (3 + P) + 0.34 * (5 + P),

P = 0.33 * 2 + 0.33 * (3 + P) + 0.34 * (5 + P),

buradan $0.33 \cdot P = 3.35$ 0.33 \cdot P = 3.35 və ya $P = 10.151515$ P = 10.151515.

Alqoritmin realizasiyası

Xətti tənliyin həllini aşağıdakı kimi aparacağıq. $P$ çarpanını ehtiva edən bütün elementləri sol tərəfə keçiririk və onların əmsallarını $l e f t$ dəyişənində saxlayırıq. Bütün sabitlər sağ tərəfdə toplanır və $r i g h t$ dəyişənində saxlanılır. İlkin olaraq $l e f t = 1$ left = 1 və $r i g h t = 0$ right = 0 olaraq təyin edirik.

Oxuyuruq $n$ cüt ədədi $x$ və $p$ .

Əgər $x > 0$ x > 0, sağ tərəfi $x \cdot p$ x \cdot p ilə artırırıq.
Əgər $x < 0$ x < 0, sağ tərəfdə $p \cdot (- x + P)$ p \cdot (-x + P) elementi yaranır. Bu halda, sağ tərəfə $p \cdot (- x)$ p \cdot (-x) artırmalı və sol tərəfdən $p$ çıxmalıyıq.

left = 1.0; right = 0.0;
scanf("%d",&n);
for(j = 0; j < n; j++)
{
  scanf("%lf %lf",&x, &p);
  if (x < 0.0)
  {
    left -= p;
    right += p * (-x);
  } else
      right += x * p;
}

C++

Nəticədə $l e f t \cdot P = r i g h t$ left \cdot P = right tənlik alırıq. Əgər $l e f t = 0$ left = 0, otağı tərk etmək mümkün deyil (təhlukəsiz yerə aparan qapı yoxdur). Əks halda, axtarılan vaxt $P = r i g h t / l e f t$ P = right / left kimi hesablanır.

if (left > 0.0)
{
  res = right / left;

Cavabı təqdim edirik. $i$ dəyişənilə testin nömrəsi uyğun gəlir.

  printf("Case %d: %.2lf\n",i,res);
} else
  printf("Case %d: God! Save me\n",i);