1 il öncə

Tədris Raundu 2

Eolymp #8358. Orta dəyər - 1

“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++;
 }

C++

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++;
  }

C++

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

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

Eolymp #10405. Teleportasiya

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$ 1 + 2 = 3 olur.

beginrow

Məsələyə keçid

Giriş məlumatlarını oxuyun.

scanf("%d %d %d %d", &a, &b, &x, &y);

Cavabı tapın — üç dəyərin minimumunu hesablayın.

res = abs(a - b);
res = min(res, abs(a - x) + abs(b - y));
res = min(res, abs(a - y) + abs(b - x));

Cavabı çap edin.

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

Eolymp #8362. Multiples

$1$ ilə $n$ (daxil olmaqla) arasında elə bir ədəd tapın ki, onun sadə vuruqlara görə parçalanmasında (faktorizasiyasında) sadə vuruqların sayı maksimum olsun. Əgər belə ədədlər bir neçədirsə, ən böyüyünü çap edin.

Məsələn, $n = 7$ n = 7 üçün cavab $6$ -dır, çünki o, sadə vuruqlara parçalananda iki vuruqdan ibarətdir: $2$ və $3$ .

Giriş. Bir tam ədəd $n (1 \leq n \leq 2^{31} - 1)$ n~(1 \le n \le 2^{31} - 1).

Çıxış. Tələb olunan ədədi çap edin.

beginrow

Məsələyə keçid

Girişdən $n$ dəyərini oxuyun.

scanf("%d",&n);

Elə ən böyük $p = 2^{k}$ p = 2^k tapın ki, $p \leq n$ p \le n olsun.

p = 1;
while (p * 2 <= n)
  p = p * 2;

Daha sonra $p 1 = 2^{k - 1} \cdot 3 = p /2 \cdot 3$ p1 = 2^{k - 1} \cdot 3 = p / 2 \cdot 3 hesablayın.

p1 = p / 2 * 3;

Nəticə $r es$ -i müəyyənləşdirin. Əgər $n = 1$ n = 1-dirsə, nəticə $1$ olacaq.

if (p1 <= n) res = p1; else res = p;
if (n == 1) res = 1;

Cavabı çap edin.

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

Eolymp #8304. Fun funksiyası

Funksiyanın dəyərini tapın

f (x, y) = ⎩ ⎨ ⎧ 0, f (x - 1, y - 2) + f (x - 2, y - 1) + 2, f (x - 2, y - 2) + 1, x \leq 0 və ya y \leq 0 x \leq y x > y

f(x, y) = \begin{cases} 0, & x \le 0~\text{və ya}~y \le 0 \\ f(x - 1, y - 2) + f(x - 2, y - 1) + 2, & x \le y \\ f(x - 2, y - 2) + 1, & x > y \end{cases}

Giriş. İki tam ədəd $x, y (0 \leq x, y \leq 50)$ x, y~(0 \le x, y \le 50).

Çıxış. $f (x, y)$ f(x, y) funksiyasının dəyərini çap edin.

Məsələyə keçid

Funksiya dəyərlərini saxlamaq üçün ikiölçülü massiv təyin edin: $d p [x] [y] = f (x, y)$ dp[x][y] = f(x, y).

long long dp[51][51];

Memoizasiya ilə f rekursiv funksiyasını reallaşdırın.

long long f(int x, int y)
{
  if (x <= 0 || y <= 0) return 0;
  if (dp[x][y] != -1) return dp[x][y];
  if (x <= y) return dp[x][y] = f(x - 1, y - 2) + f(x - 2, y - 1) + 2;
  return dp[x][y] = f(x - 2, y - 2) + 1;
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun.

scanf("%d %d",&x,&y);

$d p$ massivinin hüceyrələrini $- 1$ dəyəri ilə ilkinləşdirin.

memset(dp,-1,sizeof(dp));

$f (x, y)$ f(x, y) funksiyasını çağırın və onun dəyərini çap edin.

printf("%lld\n",f(x,y));

Eolymp #11602. İki Yallı (Round Dance)

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]$ [1, 3, 4, 2], [4, 2, 1, 3] və $[2, 1, 3, 4]$ [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)$ n~(2 \le n \le 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 = 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}$ C^{n/2}_n ü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 / 2 - 1 nəfər istənilən qaydada düzülə bilər, yəni $(n /2 - 1)!$ (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

C^{n/2}_n \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 = 4 üçün bölünmələr $([1, 2], [3, 4])$ ([1, 2], [3, 4]) və $([3, 4], [1, 2])$ ([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}

\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 = 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 = 4 üçün cavab

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

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

Gəlin, $n = 4$ 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]

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

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

fact funksiyası $n$ ədədinin faktorialını hesablayır.

long long fact(int n)
{
  long long res = 1;
  for (int i = 2; i <= n; i++)
    res *= i;
  return res;
}

C++

Proqramın əsas hissəsi. $n$ dəyərini oxuyun.

scanf("%d", &n);

Nəticəni hesablayın və çap edin.

res = 2 * fact(n - 1) / n;
printf("%lld\n", res);

Eolymp #11455. K xüsusi xanalar

Sizə ölçüsü $n \times m$ 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}$ 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}$ 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})$ n, m~(1 \le n, m \le 10^5) və $k (1 \leq k \leq 1 0^{6})$ k~(1 \le k \le 10^6) verilir; burada $n \times m$ 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)$ x_i, y_i~(1 \le x_i \le n, 1 \le y_i \le m) və $p_{i} (1 \leq p_{i} \leq 1 0^{5})$ p_i~(1 \le p_i \le 10^5) verilir; burada $(x_{i}, y_{i})$ (x_i, y_i) xüsusi xananın mövqeyi, $p_{i}$ 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$ 10^9 + 7 modulu üzrə verin.

beginrow

Məsələyə keçid

Massivləri təyin edin:

$f a c t$ — ədədlərin faktoriallarının $M O D$ üzrə qalıqları,
$f a c t in v$ factinv — bu faktorialların $M O 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

fact[n] = n! \bmod 1000000007 \\ factinv[n] = (n!)^{-1} \bmod 1000000007

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

pow funksiyası $p$ modulu üzrə qüvvəti hesablayır: $x^{n} mod p$ x^n \bmod 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 u ¨ c ¸ u ¨ n

x^{p-1} \bmod p = 1 \quad \text{istənilən } 1 \le x < p \text{ üçün}

Bunu $(x \cdot x^{p - 2}) mod p = 1$ (x \cdot x^{p-2}) \bmod p = 1 kimi yazmaq olar, buradan $x$ -in modul üzrə tərsinin $x^{p - 2} mod p$ x^{p-2} \bmod 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 )!}

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$ 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$ n + m-dir və dəqiq olaraq $m$ üfüqi addım ehtiva etdiyindən, yolların sayı $C_{n + m}^{m}$ 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$ factinv 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);

C++

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ü $r es$ 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);
}

Tədris Raundu 2

Şərhlər