Mmedv2 il öncə

İki göstərici texnikası

İki göstərici texnikası, kompüter elmləri və proqramlaşdırmada, massivlər və ya ardıcıllıqlar ilə bağlı problemlərin həlli üçün geniş istifadə olunan bir strategiyadır. Bu, massiv və ya ardıcıllığı müxtəlif mövqelərdən keçən iki göstəricinin istifadəsini əhatə edir, tez-tez əks istiqamətlərdə və ya fərqli sürətlə hərəkət edirlər. Bu texnika, axtarış, optimallaşdırma və ya massivlərin səmərəli şəkildə manipulyasiyası ilə bağlı problemlərin həllində xüsusilə faydalıdır.

İki göstərici texnikasının necə işlədiyinə dair bir qısa izah:

Başlanğıc: İlk olaraq, iki göstərici, adətən, massiv və ya ardıcıllığın müxtəlif mövqelərində yerləşdirirsiniz.
Hərəkət: Göstəriciləri müəyyən şərtlərə əsasən iterativ olaraq hərəkət etdirirsiniz, ta ki, onlar görüşənə qədər və ya müəyyən bir şərtə çatana qədər. Göstəricilərin hərəkəti problem tələblərinə əsasən idarə oluna bilər. Məsələn, bir göstərici digərlərinə nisbətən daha sürətlə hərəkət edə bilər, ya da onlar əks istiqamətlərdə hərəkət edə bilərlər.
Şərtin yoxlanması: Hər iterasiya addımında, problem tələblərinə əsaslanan müəyyən şərtləri yoxlayırsınız. Bu şərtlər tez-tez göstəriciləri hərəkət etdirmək, bəzi dəyişənləri yeniləmək və ya digər əməliyyatları həyata keçirmək üçün qərar verir.
Tamamlanma: Bu proses, bir və ya iki göstərici massiv və ya ardıcıllığın sonuna çatana qədər davam edir, ya da başqa bir tamamlanma şərti yerinə yetirilənə qədər davam edir.

İki göstərici texnikası, xüsusi meyarlara uyğun olan cütləri və ya alt massivləri axtarma, optimal həll yollarını tapma və ya ardıcıllıqları səmərəli şəkildə manipulyasiya etməklə bağlı problemlərdə xüsusilə faydalıdır, iç içə döngələrdən istifadə etmədən. Bu, xeyli vaxt sərf etmədən, düz xətti və ya logaritmik zaman mürəkkəblik tələbləri olan problemlər üçün genellikle daha səmərəli bir həll təqdim edir.

Eolymp #2098. İnvertor

$n$ tam ədəd verilib. Onları tərs qaydada çap edin.

Giriş. Əvvəlcə $n (0 < n < 100)$ n~(0 < n < 100) verilmişdir, sonra $n$ tam ədəd verilir.

Çıxış. Verilmiş $n$ tam ədədi tərs qaydada çap edin.

Problemi açıq

Bir massiv elan edin.

#define MAX 110
int m[MAX];

Giriş məlumatlarını oxuyun.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%d",&m[i]);

İki göstərici ilə massivini tərs çevirin.

i = 1; j = n;
while(i < j)
{
  temp = m[i]; m[i] = m[j]; m[j] = temp;
  i++; j--;
}

Rəqəmləri çap edin.

for(i = 1; i <= n; i++)
  printf("%d ",m[i]);
printf("\n");

Eolymp #11387. Kart oyunları

Hüseyn və Yaroslav bir kart oyunu oynayır. Masanın üstündə ardıcıl düzülmüş $n$ kart var, hər birinin üzərində fərqli bir rəqəm yazılıb. Oyunçular növbə ilə oynayırlar. Hüseyn oyuna başlayır. Hər dövrdə oyunçu ya sol kənar, ya da sağ kənar kartı ala bilər. Oyunçu həmişə ən yüksək rəqəmi olan kartı seçəcək. Oyun, masada kart qalmadıqda sona çatır. Oyun sonunda Hüseyn və Yaroslavın topladığı kartların rəqəmlərinin cəmini tapın.

Giriş. İlk sətirdə masada $n (1 \leq n \leq 10000)$ n~(1 \le n \le 10000) kartın sayı var. İkinci sətirdə $n$ müsbət tam ədəd var, hər biri kartın üzərindəki rəqəmi göstərir. Bütün ədədlər $1 0^{9}$ 10^9-dan böyük deyil.

Çıxış. Oyun sonunda Hüseyn və Yaroslavın topladığı kartların rəqəmlərinin cəmini çap edin.

Problemi açıq

Massivləri elan edin. Hüseyn və Yaroslavın topladığı kartların sayı $r es [0]$ və $r es [1]$ -də saxlanılacaq.

int m[10001], res[2];

Giriş məlumatlarını oxuyun.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &m[i]);

Göstəriciləri $i = 0$ i = 0 və $j = n - 1$ j = n - 1 təyin edin.

i = 0; j = n - 1;

Oyunçular növbə ilə, toplam $n$ addım atırlar. Hüseyn cüt $k$ üçün növbəyə girir, Yaroslav isə tək $k$ üçün. Buna görə, Hüseynin cəmi $r es [0]$ -da, Yaroslavın cəmi isə $r es [1]$ -də toplanacaq.

for (k = 0; k < n; k++)
{

Hər dövrdə, oyunçu maksimum dəyəri $ma x (m [i], m [j])$ max(m[i], m[j]) olan kartı seçir.

  if (m[i] > m[j])
    res[k % 2] += m[i++];
  else
    res[k % 2] += m[j--]; ;
}

Cavabı çap edin.

printf("%d %d\n", res[0], res[1]);

Eolymp #11388. Kart oyunları 2

Hüseyn $n$ kartı bir sıra düzülərək $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n ilə düzür. Sonra onları toplayır və başqa bir ardıcıllıqla düzür: $a_{1}, a_{3}, a_{5}, ..., a_{6}, a_{4}, a_{2}$ a_1, a_3, a_5, ..., a_6, a_4, a_2. Bu, Yaroslava verdiyi ardıcıllıqdır. Sizin işiniz, Yaroslavanın Hüseynin orijinal ardıcıllığını bərpa etməsinə kömək etməkdir.

Məsələn, əgər Yaroslava ardıcıllığı $(2, 4, 9, 4, 7, 6)$ (2, 4, 9, 4, 7, 6) verilibsə, o zaman o, Hüseyinə $(2, 6, 4, 7, 9, 4)$ (2, 6, 4, 7, 9, 4) ardıcıllığını qaytarmalıdır.

Giriş. İlk sətirdə bir tam ədəd $n (1 \leq n \leq 10000)$ n~(1 \le n \le 10000) var, kartların sayı. İkinci sətirdə $n$ müsbət tam ədəd var, kartların üzərindəki ədədlər. Bütün ədədlər $1 0^{9}$ 10^9-dan böyük deyil.

Çıxış. Hüseynin orijinal ardıcıllığını çap edin.

Problemi açıq

Bir massiv elan edin.

int a[100001];

Giriş məlumatlarını oxuyun.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Göstəriciləri $i = 0$ i = 0 və $j = n - 1$ j = n - 1 təyin edin.

i = 0; j = n - 1;

$i \leq j$ i \le j bərabərsizliyi mövcud olduqda, növbə ilə $a_{i}$ a_i və $a_{j}$ a_j -ı çap edin, eyni zamanda göstəriciləri hərəkət etdirin.

while (i <= j)
{
  printf("%d ", a[i++]);
  if (i > j) break;
  printf("%d ", a[j--]);
}

Eolymp #11389. Hüseynin oyunu

Hüseynin $0$ və $1$ simvollarından ibarət bir stringi var. Özünü əyləndirmək üçün, o aşağıdakı oyunu düzəldib. Hüseyn stringə iki əməliyyatdan birini həyata keçirə bilər:

Sol ucuna $0$ , sağ ucuna $1$ əlavə etmək;
Sağ ucuna $0$ , sol ucuna $1$ əlavə etmək;

Məsələn, $010$ stringindən Hüseyn $00101$ və ya $10100$ ala bilər.

Siz, Hüseyinin bütün əməliyyatlardan sonra əldə etdiyi stringi verirsiniz (ola bilsin ki, o, heç bir əməliyyat etməyib). Stringin əvvəllər mümkün olan ən kiçik uzunluğunu təyin edin.

Giriş. Uzunluğu $1 0^{5}$ 10^5-dan çox olmayan, yalnız $0$ və $1$ simvollarından ibarət bir string verilir.

Çıxış. Hüseyinin əvvəlki stringinin mümkün olan ən kiçik uzunluğunu çap edin.

Problemi açıq

Giriş stringini oxuyun və onun uzunluğunu hesablayın, $r es$ dəyişənində saxlayın.

cin >> s;
res = s.size();

İki göstəricini $i = 0$ i = 0 stringin başlanğıcında və $j = n - 1$ j = n - 1 stringin sonunda təyin edin.

i = 0; j = s.size() - 1;

Əgər $s_{i} \neq = s_{j}$ s_i \ne s_j olarsa, deməli, stringin sonundakı simvollar müxtəlifdir. Huseyn, substring $s [i ... j]$ -ni substring $s [i + 1... j - 1]$ s[i + 1 ... j - 1]-dən almış ola bilər.

while ((i < j) && (s[i] != s[j]))
{

Hər iki göstəricini bir mövqe içəriyə doğru hərəkət etdirin və cari $r es$ uzunluğunu azaldın.

  i++; j--;
  res -= 2;
}

Cavabı çap edin.

cout << res << endl;

Eolymp #11244. İki ədədin cəmi

Verilmiş massiv $A$ , artan sırada düzülmüş $n$ tam ədəd var. $x$ -ə bərabər olan $(A_{i}, A_{j})$ (A_i, A_j) cütünün olub olmadığını müəyyən edin, burada $i < j$ i < j.

Giriş. İlk sətirdə iki tam ədəd $n (n \leq 1 0^{5})$ n~(n \le 10^5) və $x (x \leq 1 0^{6})$ x~(x \le 10^6) var. İkinci sətirdə $n$ müsbət tam ədəd var, hər biri $1 0^{6}$ 10^6-dan böyük deyil.

Çıxış. Əgər belə bir cüt varsa "BƏLİ" yazın, əks halda "YOX" yazın.

Problemi açıq

Giriş məlumatlarını oxuyun.

scanf("%d %d", &n, &x);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Göstəriciləri təyin edin.

int i = 0, j = v.size() - 1;

Göstərici $i$ -ni irəlilədin və $j$ -ni gerilədin.

while (i < j)
{

Əgər $v_{i} + v_{j} = x$ v_i + v_j = x olarsa, tələb olunan cüt tapılmışdır. Çap edin və proqramı dayandırın.

  if (v[i] + v[j] == x)
  {
    printf("BƏLİ\n");
    return 0;
  }

Əgər $v_{i} + v_{j} < x$ v_i + v_j < x olarsa, göstərici $i$ -ni bir mövqe sağa hərəkət etdirin;

Əgər $v_{i} + v_{j} > x$ v_i + v_j > x olarsa, göstərici $j$ -ni bir mövqe sola hərəkət etdirin;

  if (v[i] + v[j] < x) i++; else j--;
}

Əgər tələb olunan cüt tapılmayıbsa, "YOX" çap edin.

printf("YOX\n");

Eolymp #11246. Üç ədədin cəmi

Verilmiş $A$ tam ədəd massivində $x$ ədədinə bərabər olan $(A_{i}, A_{j}, A_{k})$ (A_i, A_j, A_k) ədədlərini tapın. Bütün indekslər $i, j, k$ i, j, k fərqli olmalıdır.

Giriş. İlk sətirdə massiv ölçüsü $n (n \leq 3 \cdot 1 0^{4})$ n~(n \le 3 \cdot 10^4) və $x (∣ x ∣ \leq 1 0^{9})$ x~(|x| \le 10^9) dəyəri var. İkinci sətirdə $n$ tam ədəd var, hər biri $1 0^{8}$ 10^8-dan böyük deyil.

Çıxış. Əgər tələb olunan üçlük varsa, onu istənilən sırada çap edin. Əgər bir neçə üçlük varsa, hər hansı birini çap edin. Əgər tələb olunan üçlük yoxdursa, $- 1$ çap edin.

Problemi açıq

Giriş məlumatlarını oxuyun.

cin >> n >> x;
v.resize(n);
for (i = 0; i < n; i++)
  cin >> v[i];

Giriş massivini sıralayın.

sort(v.begin(), v.end());

$k = 0, 1, ..., n - 3$ k = 0, 1, ..., n - 3 dəyərləri üçün dövr edin.

for (k = 0; k < n - 2; k++)
{

$i > k$ i > k və $v_{i} + v_{j} = x - v_{k} (i < j)$ v_i + v_j = x - v_k~(i < j) indeks cütlərini tapın. $i$ və $j$ indekslərini təyin edin.

  i = k + 1; j = n - 1;
  s = x - v[k];

İki göstərici texnikasından istifadə edərək istənilən cüt $(i, j)$ -ni tapın.

  while (i < j)
  {
    if (v[i] + v[j] == s)
    {

Əgər $(i, j)$ cütü tapılmışdırsa, istənilən ədədləri $(v_{k}, v_{i}, v_{j})$ (v_k, v_i, v_j) çap edin.

      printf("%d %d %d\n", v[k], v[i], v[j]);
      return 0;
    }

Əgər $v [i] + v [j] < s$ v[i] + v[j] < s olarsa, göstərici $i$ -ni bir mövqe sağa hərəkət etdirin;

Əgər $v [i] + v [j] > s$ v[i] + v[j] > s olarsa, göstərici $j$ -ni bir mövqe sola hərəkət etdirin;

    if (v[i] + v[j] < s) i++; else j--;
  }
}

Əgər ədədlərin üçlüyü tapılmadısa, $- 1$ çap edin.

cout << -1 << endl;

Eolymp #11286. İki qat daha böyük

Verilmiş sıralanmış $A$ massivində $n$ tam ədəd var. Hər bir indeks $i$ üçün, $A_{i}$ A_i və $2 \cdot A_{i}$ 2 \cdot A_i arasında olan elementlərin sayını tapın, daxil olmaqla.

Giriş. İlk sətirdə $A$ massivinin ölçüsü $n (n \leq 1 0^{5})$ n~(n \le 10^5) var. İkinci sətirdə $n$ tam ədəd, hər biri $0$ -dan $1 0^{9}$ 10^9-a qədər, sıralanmış olaraq var.

Çıxış. $n$ tam ədəd çap edin. Hər bir $i (1 \leq i \leq n)$ i~(1 \le i \le n) üçün, $A_{i}$ A_i və $2 \cdot A_{i}$ 2 \cdot A_i arasında, daxil olmaqla, olan elementlərin sayını çap edin.

Problemi açıq

Giriş məlumatlarını oxuyun.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Göstəriciləri $i = j = 0$ i = j = 0 ilə təyin edin.

i = j = 0;

Hər bir $i < n$ i < n dəyəri üçün cavab tapana qədər göstəriciləri irəliləyin.

while (i < n) // [i..j]
{

Əgər $A_{j} \leq 2 \cdot A_{i}$ A_j \le 2 \cdot A_i (və $j$ massiv sərhədlərini keçməyibsə, yəni $j < n$ j < n), cari intervalları $A [i ... j + 1]$ A[i ... j + 1] ilə genişləndirin.

  if ((j < n) && (a[j] <= 2 * a[i])) j++;
  else
  {

Əgər $A_{j} > 2 \cdot A_{i}$ A_j > 2 \cdot A_i olarsa, $i$ indeksi üçün cavabı çap edin və $i$ -ni bir artırın.

    printf("%d ", j - i);
    i++;
  }
}

Eolymp #10682. Xorvatiya sahili boyunca otellər

Gözəl Adriatik sahili boyunca $n$ otel var. Hər bir otelin qiyməti avro ilə ifadə edilir. Petr lotereyada $m$ avro qazandı. İndi o, bu ardıcıl otellərin cəminin mümkün olduğu qədər böyük olmasını istəyir, amma $m$ -i keçməməlidir.

Maksimal mümkün qiyməti hesablamağınız lazımdır.

Giriş. İlk sətirdə iki tam ədəd $n$ və $m (1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m < 2^{31})$ m~(1 \le n \le 3 \cdot 10^5, 1 \le m < 2^{31}) var. Növbəti sətirdə $n$ müsbət tam ədəd var, sahil boyunca yerləşən otellərin qiymətləri.

Çıxış. İstənilən qiymətləri çap edin (bütün testlərdə 0-dan böyük olacaq).

Problemi açıq

Giriş məlumatlarını oxuyun.

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

İndiki dəyişənləri təyin edin:

$r es$ -də, bütün işlənmiş yaxşı intervallardakı qiymətlərin maksimumunu hesablayın;
$s$ -də, cari intervallardakı ədədlərin cəmini saxlayın. Cari intervallardakı bütün ədədlər $q$ queue-da saxlanılır;

s = res = 0;

Otel qiymətlərini ardıcıl işləyin.

for (i = 0; i < n; i++)
{

Cari otelin qiymətini oxuyun və onu queue-ya əlavə edin.

  scanf("%d", &val);
  q.push(val);

Cari intervallardakı $s$ cəmini yeniləyin. Bütün cari intervallardakı elementlər $q$ queue-da saxlanılır.

  s += val;

Əgər cari intervallardakı cəmi $s$ , $m$ -i keçərsə, intervallardan başından elementləri çıxarın.

  while (s > m)
  {
    s -= q.front();
    q.pop();
  }

Yaxşı intervallardakı ədədlərin cəmi arasında maksimum qiyməti $r es$ -i yeniləyin (otellərin qiymətləri $m$ -i keçməməlidir).

  if (s > res) res = s;
}

Cavabı çap edin.

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

Eolymp #11721. Alt massivlərin cəmi 1

Verilmiş $n$ müsbət tam ədəd massivini, $x$ -ə bərabər olan alt massivlərin sayını tapın.

Giriş. İlk sətirdə massiv ölçüsü $n (1 \leq n \leq 2 \cdot 1 0^{5})$ n~(1 \le n \le 2 \cdot 10^5) və hədəf cəmi $x (1 \leq x \leq 1 0^{9})$ x~(1 \le x \le 10^9). Növbəti sətirdə $n$ ədəd $a_{1}, a_{2}, \dots, a_{n} (1 \leq a_{i} \leq 1 0^{9})$ a_1, a_2, \ldots, a_n~(1 \le a_i \le 10^9) — massiv məzmunu.

Çıxış. Lazım olan alt massivlərin sayını çap edin.

Problemi açıq

Bir massiv elan edin.

#define MAX 200001
long long a[MAX];

Giriş məlumatlarını oxuyun.

scanf("%d %lld", &n, &x);
for (i = 0; i < n; i++)
  scanf("%lld", &a[i]);

Başlanğıc intervalını $[i ... j] = [0; 0]$ [i ... j] = [0; 0] olaraq təyin edin. Bu intervaldakı ədədlərin cəmi $s = 0$ s = 0-dir.

s = j = 0;

Hər bir $i$ dəyəri üçün ardıcıl $[i ... j]$ intervallarını işləyin.

for (i = 0; i < n; i++)
{

Sabit sol son $i$ olan $[i ... j]$ intervalında $j$ -nin ən böyük dəyərini tapın ki, cəmi $x$ -i keçməsin.

  while ((j < n) && (s + a[j] <= x)) s += a[j++];

Cari $[i ... j]$ intervalındakı ədədlərin cəmi $s$ $x$ -ə bərabər olduqda, istədiyimiz alt massiv sayını $c n t$ -ni artırın.

  if (s == x) cnt++;

$[i + 1... j]$ [i + 1 ... j] intervalındakı $s$ -ni yenidən hesablayın.

  s -= a[i];
}

Cavabı çap edin.

printf("%lld\n", cnt);

Eolymp #9631. Ardıcıllıqların müsabiqəsi

Ziya sabah ardıcıllıq müsabiqəsində iştirak edəcək. $x \geq 0$ x \ge 0 ədədi, bir ardıcıllığın zirvəsi sayılır, əgər ardıcıllıq $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ 1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1 bu ardıcıllığın alt ardıcıllığıdır. Hər bir ardıcıllığın gücü onun ən böyük zirvəsi sayılır.

Sabah bütün tələbələr müsabiqəyə gedəcəklər və ən güclü ardıcıllığın qalibi olacaq. Ziya $a_{1}, a_{2}, a_{3}, ..., a_{n}$ a_1, a_2, a_3, ..., a_n ardıcıllığına sahibdir. O, bu gün bütün ardıcıllıqlara üstünlük verərək daha güclü ardıcıllığı seçmək istəyir. Ancaq Ziya öz ardıcıllığının gücünü bilmir, lakin qalib olmaq istəyir. Ona kömək edin ki, öz ardıcıllığının gücünü hesablasın.

Giriş. İlk sətirdə Ziyanın ardıcıllığında olan ədədlərin sayı $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) var. Növbəti sətirdə $n$ tam ədəd $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ a_i~(1 \le a_i \le 10^5) — ardıcıllığın elementləridir.

Çıxış. Bir ədəd çap edin — verilmiş ardıcıllığın gücüdür.

Problemi açıq

Giriş məlumatlarını oxuyun.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Göstəriciləri $v$ massivinin başlanğıcında və sonunda yerləşdirin.

int i = 0, j = v.size() - 1;

Güc dəyişənini sayın.

k = 1;
while (i <= j)
{

Göstərici $i$ -ni sağa doğru keçirin ki, $k$ -ya bərabər olmayan ədədlərə rast gəlməyəsiniz.

  if (v[i] != k) i++;

Göstərici $j$ -ni sola doğru keçirin ki, $k$ -ya bərabər olmayan ədədlərə rast gəlməyəsiniz.

  if (v[j] != k) j--;

Hər iki göstərici $k$ -ya bərabər olduqda, $k$ -ni artırın.

  if (v[i] == k && v[j] == k) k++;
}

Cavabı çap edin.

printf("%d\n", k - 1);

İki göstərici texnikası

Problemlərin siyahısı

Şərhlər5