Tutorial•2 gün öncə

Tədris Raundu 2

“Məktəb Şagirdinin Orta Çəkisi” layihəsini Məmməd və Səməd həyata keçiriblər.

Onlara bu ədədin niyə lazım olduğu hələ də müəmmadır. Onlar məktəbdəki bütün şagirdlərdən çəkiyə çıxmalarını xahiş etdilər və nəticələri cədvələ yazdılar. Sənin vəzifən onlara şagirdlərin orta çəkisini hesablamaqda kömək etməkdir. Lakin bir şərt var: orta hesablanarkən ən yüksək və ən aşağı çəkiyə malik şagirdlər nəzərə alınmamalıdır.

Qeyd edək ki, Məmməd və Səməd ümumi şagird sayını saymağı unudublar, lakin bu, tapşırığı yerinə yetirməyə mane olmayacaq.

Giriş. Şagirdlərin çəkiləri bir neçə sətir üzrə verilir və boşluqlarla (bir və daha çox) və ya sətirsonu simvolu ilə ayrılır. Giriş faylın sonuna qədər davam edir.

Çıxış. Ən yüksək və ən aşağı çəkiyə malik şagirdləri istisna etməklə, şagirdlərin orta çəkisini çap edin. Nəticə ən yaxın tam ədədə yuvarlaqlaşdırılmalıdır.

beginrow

Məsələyə keçid

Massivi elan edin.

int w[1000];

Giriş məlumatlarını oxuyun. Daxil edilən ədədlərin sayı $n$ dəyişənində saxlanılır.

n = 0;
while (scanf("%d", &w[n]) == 1) n++;

Massivdə ən kiçik element $min$ və ən böyük element $ma x$ tapın.

min = max = w[0];
for (i = 0; i < n; i++)
{
  if (w[i] > max) max = w[i];
  if (w[i] < min) min = w[i];
}

Ən yüksək və ən aşağı çəkilər istisna olunmaqla, cəmi $s$ və şagirdlərin sayını $c n t$ hesablayın.

s = cnt = 0;
for (i = 0; i < n; i++)
  if (w[i] != min && w[i] != max)
  {
    s = s + w[i];
    cnt++;
 }

Nəticəni ən yaxın bütöv kiloqrama yuvarlaqlaşdıraraq çap edin.

printf("%.0lf\n", 1.0 * s / cnt);

Alqoritmin reallaşdırılması — min_element, max_element

Massivi elan edin.

vector<int> w;

Giriş məlumatlarını oxuyun.

while (scanf("%d", &x) == 1)
  w.push_back(x);

Massivdə ən kiçik element $min_e l$ və ən böyük element $ma x_e l$ tapın.

min_el = *min_element(w.begin(), w.end());
max_el = *max_element(w.begin(), w.end());

Ən yüksək və ən aşağı çəkilər istisna olunmaqla çəki cəmini $s$ və şagirdlərin sayını $c n t$ hesablayın.

s = cnt = 0;
for (int x : w)
  if (x != min_el && x != max_el) 
  {
    s += x;
    cnt++;
  }

Nəticəni ən yaxın bütöv kiloqrama yuvarlaqlaşdıraraq çap edin.

printf("%.0lf\n", 1.0 * s / cnt);

Fermer Conun ən az xoşladığı təsərrüfat işlərindən biri çoxlu inək peyinini daşımaqdır. Bu prosesi sadələşdirmək üçün o, möhtəşəm bir ixtira fikirləşir: peyin teleportatı! Traktorunun arxasında qoşqu ilə iki nöqtə arasında peyin daşımaq əvəzinə, peyin teleportunu istifadə edib onu bir yerdən başqa yerə anında köçürə bilər.

Fermer Conun təsərrüfatı tək, uzun, düz bir yol boyunca salınıb; buna görə təsərrüfatdakı istənilən yer sadəcə bu yol üzərindəki mövqeyi ilə təsvir oluna bilər (əslində ədədlər oxunda bir nöqtə kimi). Teleport iki ədədlə — $x$ və $y$ ilə — təsvir olunur; $x$ mövqeyinə gətirilən peyin ani olaraq $y$ mövqeyinə, yaxud əksinə, daşına bilər.

Fermer Con peyini $a$ nöqtəsindən $b$ nöqtəsinə daşımaq istəyir və bu prosesdə kömək edə biləcək bir teleport quraşdırıb (əlbəttə, kömək etməsə ondan istifadə etməyə bilər). Xahiş edirik, traktorla daşımalı olduğu minimal ümumi məsafəni müəyyənləşdirməyə kömək edin.

Giriş. Bir sətirdə dörd tam ədəd verilir: başlanğıc və son mövqeləri təsvir edən $a$ və $b$ , sonra isə teleportu təsvir edən $x$ və $y$ . Bütün mövqelər $0 \dots 100$ aralığında tam ədədlərdir və bir-birindən mütləq fərqli olmaya bilər.

Çıxış. Traktorla daşımalı olduğu minimal məsafəni göstərən tək tam ədəd çap edin.

Misal. Bu nümunədə ən yaxşı strategiya peyini əvvəlcə $3$ mövqeyindən $2$ mövqeyinə daşımaq, sonra $2$ -dən $8$ -ə teleport etmək, sonda isə $8$ -dən $10$ -a daşımaqdır. Beləliklə, traktor tələb edən ümumi məsafə $1 + 2 = 3$ olur.

beginrow

Məsələyə keçid

$n$ -i aşmayan ədədin mümkün qədər çox böləni olması üçün o, ən kiçik sadə ədədlərin hasil kimi təqdim olunmalıdır.

Məsələn, $2^{k}$ şəklində ədədlərə baxaq. $2^{k} \leq n$ şərtini ödəyən ən böyük $k$ -nı tapın. $2^{k}$ -ın bölənlərinin sayı $d (2^{k}) = k + 1$ -dir.

Daha sonra $2^{k - 1} \cdot 3$ ədədini nəzərdən keçirək. Onun bölənlərinin sayı $d (2^{k - 1} \cdot 3) = k \cdot 2$ -dir ki, bu da $k + 1$ -dən böyükdür.

Deməli:

Əgər $2^{k - 1} \cdot 3 \leq n$ -dirsə, axtarılan ədəd $2^{k - 1} \cdot 3$ -dür;
Əks halda cavab $2^{k}$ -dır.

Sonda xüsusi halı nəzərə alın: $n = 1$ olduqda cavab $1$ -dir.

Nümunə

Qoy $n = 100$ . $100$ -ü aşmayan $2$ -nin ən böyük qüvvəti $2^{6} = 64$ -dür. $64$ ədədinin bölənlərinin sayı $d (64) = 6 + 1 = 7$ -dir.

İndi $2^{5} \cdot 3 = 96$ ədədinə baxaq. Onun bölənlərinin sayı:

d (96) = (5 + 1) * (1 + 1) = 6 * 2 = 12

$96$ $100$ -ü aşmadığı üçün, $n = 100$ üçün axtarılan ədəd bu olacaq.

Bir gün $n$ nəfər ( $n$ cütdür) meydanda görüşdü və iki yallı qurdu. Elə üsulların sayını tapın ki, hər yallı dəqiq $n /2$ nəfərdən ibarət olsun. Hər bir şəxs bu iki yallıdan yalnız birinə aid olmalıdır.

Yallı — $1$ və ya daha çox nəfərdən ibarət dairəvi rəqsdir. İki yallı ayırtedilməz (eyni) sayılır, əgər birincinin başlanğıc iştirakçısını seçməklə o birinə çevrilmək mümkündür. Məsələn, $[1, 3, 4, 2], [4, 2, 1, 3]$ və $[2, 1, 3, 4]$ yallıları ayırtedilməzdir.

Giriş. Tək sətirdə bir cüt tam ədəd $n (2 \leq n \leq 20)$ .

Çıxış. İki yallı qurmağın üsullarının sayını çap edin. Cavabın $64$ -bit tam ədəd tipinə sığacağına zəmanət verilir.

Nümunələr. Məsələn, $n = 4$ üçün üsulların sayı $3$ -dür:

bir yallı — $[1, 2]$ , digəri — $[3, 4]$ ;
bir yallı — $[2, 4]$ , digəri — $[3, 1]$ ;
bir yallı — $[4, 1]$ , digəri — $[3, 2]$ .

hrefhttps://basecamp.eolymp.com/problems/11602Məsələyə keçid

Əvvəlcə birinci dairəvi rəqs üçün $n /2$ nəfəri seçməliyik. Bunu $C_{n}^{n /2}$ üsulla etmək olar. Bir dairədə insanların necə düzüləcəyinin sayını hesablayaq: birinci olacaq şəxsi fiksasiya edirik, bundan sonra qalan $n /2 - 1$ nəfər istənilən qaydada düzülə bilər, yəni $(n /2 - 1)!$ üsulla. İki dairəvi rəqsin formalaşdırılma üsullarının sayı:

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

Buradakı $2$ -yə bölmə $(x, y)$ və $(y, x)$ cütlərini ayırd etməmək üçün lazımdır. Məsələn, $n = 4$ üçün bölünmələr $([1, 2], [3, 4])$ və $([3, 4], [1, 2])$ eyni sayılır.

Verilən formulu sadələşdirsək, cavabı alarıq:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

Nümunə

Məsələn, $n = 4$ üçün üsulların sayı $3$ -dür:

Bir yallı — $[1, 2]$ , digəri — $[3, 4]$ ;
Bir yallı — $[2, 4]$ , digəri — $[3, 1]$ ;
Bir yallı — $[4, 1]$ , digəri — $[3, 2]$ .

Formul üzrə $n = 4$ üçün cavab

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

Gəlin, $n = 4$ üçün bütün ayırdedilən dairəvi rəqsləri quraq. İştirakçı $1$ -i birinci mövqedə yerləşdirək. Qalan üç mövqeyə digər üç iştirakçının istənilən yerləşməsini qoya bilərik.

Bu düzülüşlərin hər hansı birini çevirməklə eyni (ayırtedilməz) dairəvi rəqslər alınır. Məsələn, aşağıdakı düzülüşlər ayırtedilməzdir (son permutasiyanın siklik sürüşmələrini nəzərdən keçirin):

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

$4$ iştirakçı ilə $4! = 24$ dairəvi rəqs var. Lakin $n = 4$ üçün ayırdedilən dairəvi rəqslərin sayı $3! = 6$ -dır.

Sizə ölçüsü $n \times m$ olan və $k$ xüsusi xanaya malik bir matrisa verilir. $(1, 1)$ mövqeyindən başlayıb $(n, m)$ xanaya çatmalısınız. Hər hansı xananın içindən yalnız sağa və ya aşağı hərəkətə icazə verilir.

Bu $k$ xüsusi xananın hər birinin müəyyən gücü var. $i$ -ci xüsusi xananın gücü $p_{i}$ -dir və əgər bu xananın üzərindən keçsəniz, həmin gücü qazanırsınız.

Tapşırığınız $(1, 1)$ -dən $(n, m)$ -ə olan bütün mümkün yollar üzrə toplanacaq ümumi gücü tapmaqdır.

Qeyd:

Yolun gücü həmin yol boyunca ziyarət edilən bütün xüsusi xanaların $p_{i}$ dəyərlərinin cəmidir.
Xüsusi olmayan adi xanaların gücü sıfıra bərabərdir.

Giriş. Birinci sətirdə testlərin sayı olan $t$ verilir.

Hər testin birinci sətirində üç tam ədəd $n, m (1 \leq n, m \leq 1 0^{5})$ və $k (1 \leq k \leq 1 0^{6})$ verilir; burada $n \times m$ şəbəkənin ölçüsü, $k$ isə xüsusi xanaların sayıdır.

Sonrakı $k$ sətirdə hər birində üç tam ədəd $x_{i}, y_{i} (1 \leq x_{i} \leq n, 1 \leq y_{i} \leq m)$ və $p_{i} (1 \leq p_{i} \leq 1 0^{5})$ verilir; burada $(x_{i}, y_{i})$ xüsusi xananın mövqeyi, $p_{i}$ isə onun gücüdür.

Çıxış. Hər test üçün ayrıca sətirdə toplanacaq ümumi gücü çap edin. Nəticə çox böyük ola biləcəyindən, onu $1 0^{9} + 7$ modulu üzrə verin.

beginrow

Məsələyə keçid

$w a ys (x, y)$ — $(1, 1)$ hüceyrəsindən $(1 + x, 1 + y)$ hüceyrəsinə qədər şəbəkə üzərində yolların sayını ifadə etsin. O zaman

w a ys (x, y) = C_{x + y}^{x} = C_{x + y}^{y}

$(1, 1)$ hüceyrəsindən $(n, m)$ hüceyrəsinə gedən və xüsusi $(x, y)$ hüceyrəsindən keçən yolların sayı $w a ys (x - 1, y - 1) \cdot w a ys (n - x, m - y)$ -ə bərabərdir. Bu ədədi $p$ ilə vurmaq $(x, y)$ hüceyrəsindən keçən bütün yolların ümumi gücünü verir.

Qalır, xüsusi hüceyrələrdən keçən bütün yolların güclərini toplamaq. Cavab aşağıdakı cəmlə veriləcək:

i = 1 \sum k w a ys (x_{i} - 1, y_{i} - 1) \cdot w a ys (n - x_{i}, m - y_{i}) \cdot p_{i}

Nümunə

Verilən nümunədə $k = 2$ xüsusi xana göstərilib.

Gücü $4$ olan xananın üzərindən dəqiq bir yol keçir.
Gücü $7$ olan xananın üzərindən dəqiq bir yol keçir.

Beləliklə, ümumi güc $4 + 7 = 11$ -dir.

Massivləri təyin edin:

$f a c t$ — ədədlərin faktoriallarının $MO D$ üzrə qalıqları,
$f a c t in v$ — bu faktorialların $MO D$ üzrə tərs elementləri:

f a c t [n] = n! mod 1000000007 f a c t in v [n] = (n!)^{- 1} mod 1000000007

#define MAX 800001
ll fact[MAX], factinv[MAX];

pow funksiyası $p$ modulu üzrə qüvvəti hesablayır: $x^{n} mod p$ .

ll pow(ll x, ll n, ll p)
{
    if (n == 0) return 1;
    if (n % 2 == 0) return pow((x * x) % p, n / 2, p);
    return (x * pow(x, n - 1, p)) % p;
}

inverse funksiyası $p$ sadə moduluna görə $x$ ədədinin modul üzrə tərsini tapır. $p$ sadə olduğundan, Fermatın kiçik teoreminə görə:

x^{p - 1} mod p = 1 istənilən 1 \leq x < p \overset{u}{¨} \overset{c}{¸} \overset{u}{¨} n

Bunu $(x \cdot x^{p - 2}) mod p = 1$ kimi yazmaq olar, buradan $x$ -in modul üzrə tərsinin $x^{p - 2} mod p$ olduğu nəticəsi çıxır.

ll inverse(ll x, ll p)
{
  return pow(x, p - 2, p);
}

Cnk funksiyası binom əmsalını aşağıdakı düsturla hesablayır:

C_{n}^{k} = \frac{n !}{k ! ( n - k )!}

ll Cnk(int n, int k)
{
  return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD;
}

ways funksiyası $(0, 0)$ hüceyrəsindən $(n, m)$ hüceyrəsinə qədər $n \times m$ şəbəkəsində yolların sayını hesablayır. Bu nöqtələr arasındakı istənilən yolun uzunluğu $n + m$ -dir və dəqiq olaraq $m$ üfüqi addım ehtiva etdiyindən, yolların sayı $C_{n + m}^{m}$ -ə bərabərdir.

ll ways(int n, int m)
{
  return Cnk(n + m, m);
}

Proqramın əsas hissəsi. Faktoriallar $f a c t$ və tərs faktoriallar $f a c t in v$ massivlərini doldurun.

fact[0] = 1;
for (i = 1; i < MAX; i++)
  fact[i] = (fact[i - 1] * i) % MOD;

factinv[0] = 1;
for (i = 1; i < MAX; i++)
  factinv[i] = inverse(fact[i], MOD);

Testləri ardıcıl emal edin.

scanf("%d", &tests);
while (tests--)
{

Cari test üçün məlumatları oxuyun.

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

Alınan ümumi gücü $res$ dəyişənində saxlayın.

  res = 0;

$k$ xüsusi xananı emal edin.

  for (i = 0; i < k; i++)
  {
    scanf("%d %d %d", &x, &y, &p);
    res = (res + (ways(x - 1, y - 1) * 
                  ways(n - x, m - y)) % MOD * p) % MOD;
  }

Cari test üçün cavabı çap edin.

  printf("%lld\n", res);
}

Şərhlər

Hələ də heç nə

Söhbəti başladan ilk siz olun!

Daxil ol

Yüklənir

Bir an, serverdən məlumat alınır