•Article•11 ay ö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.

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)$ 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}$ -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

Hüseyn $n$ kartı bir sıra düzülərək $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}$ . 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)$ verilibsə, o zaman o, Hüseyinə $(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)$ 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}$ -dan böyük deyil.

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

Problemi açıq

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}$ -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

Gəlin $s$ giriş stringini nəzərdən keçirək — Huseyn bütün əməliyyatları etdikdən sonra əldə edilən string. İki göstəricini: $i = 0$ stringin başında və $j = n - 1$ sonunda təyin edək.

Əgər $s_{i} \neq = s_{j}$ olarsa, deməli, stringin sonundakı simvollar müxtəlifdir: ya solda $0$ və sağda $1$ , ya da solda $1$ və sağda $0$ . Bu, əvvəlki stringin $s [i + 1... j - 1]$ -dan genişləndirilə biləcəyini bildirir. Bu halda, hər iki göstəricini bir mövqe içəriyə doğru hərəkət etdirib $s [i ... j]$ -nin Huseynin əməliyyatları ilə əldə olunub-olunmadığını yenidən yoxlayın.

Halbuki, cari $s [i ... j]$ substringi $s_{i} = s_{j}$ olana qədər bu əməliyyatdan davam edə bilməz. Uzunluğunu çap edin — bu, Huseynin saxladığı orijinal stringdir.

Nümunə

Hüseynin əməliyyatlarını əks etdirək.

String $s = "1"$ idi, bu da Huseynin əvvəlki stringidir.

Gəlin $v$ giriş ədədləri massivini nəzərdən keçirək. İki göstəricini $i = 0$ massivinin başlanğıcında və $j = n - 1$ massivinin sonunda təyin edin. Massiv artıq problem şərtlərinə əsasən sıralanmışdır.

Göstəricilər $i$ və $j$ görüşmədiyi müddətdə, aşağıdakı əməliyyatları yerinə yetirin:

Əgər $v_{i} + v_{j} = x$ olarsa, tələb olunan cüt tapılmışdır. Çap edin və proqramı dayandırın.
Əgər $v_{i} + v_{j} < x$ olarsa, göstərici $i$ -ni bir mövqe sağa hərəkət etdirin. Bu halda $v_{i} + v_{j}$ artacaq;
Əgər $v_{i} + v_{j} > x$ olarsa, göstərici $j$ -ni bir mövqe sola hərəkət etdirin. Bu halda $v_{i} + v_{j}$ azalacaq;

Nümunə

Gəlin ilk testi nəzərdən keçirək. Göstəriciləri başla. Alqoritmin işləməsini simulyasiya edək. $x = 13$ -dir, $13$ -ə bərabər olan iki ədəd axtarırı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$ dəyərləri üçün dövr edin.

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

$i > k$ və $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})$ çap edin.

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

Əgər $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$ 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;

$A [i ... j]$ intervalı yaxşı sayılır əgər içindəki ədədlər $[A_{i}; 2 \cdot A_{i}]$ intervalında yerləşirsə (yəni $A_{j} \leq 2 \cdot A_{i}$ ).

İki göstərici $i$ və $j$ istifadə edərək bir sürüşdürmə pəncərəsi yaradaq və onu saxlayaraq belə bir şəkildə saxlayaq ki, cari interval $[i ... j]$ yaxşı olsun, eyni zamanda $[i ... j + 1]$ isə pis olsun.

Məsələn, aşağıdakı ardıcıllıq üçün:

$[2; 2], [2; 3], [2; 4]$ və $[2; 5]$ intervalı yaxşıdır.
$[2; 6], [2; 7]$ intervalı pisdir.

Əgər $A_{j} \leq 2 \cdot A_{i}$ olarsa, cari intervalı $A [i ... j + 1]$ ilə genişləndirin. Əks halda, onu $A [i + 1... j]$ ilə daraldın. $i$ -ni hərəkət etdirmədən əvvəl $A_{i}$ və $2 \cdot A_{i}$ arasında, daxil olmaqla, olan elementlərin sayını çap edin. Bu, $j - i$ -yə bərabərdir.

Alqoritmin mürəkkəbliyi xətti, yəni $O (n)$ -dir.

Nümunə

Verilmiş nümunə üçün göstəricilərin hərəkətini düşünək.

Verilmiş şərtlər üçün $A_{j} \leq 2 \cdot A_{i}$ olduğuna görə, göstərici $j$ -ni irəliləyin.

İndi $A_{j} > 2 \cdot A_{i}$ . Göstərici $i$ -ni irəliləmək lazımdır. Lakin, onu hərəkət etdirməzdən əvvəl $A_{i}$ və $2 \cdot A_{i}$ arasında, daxil olmaqla, olan elementlərin sayını çap edin. Bu, $j - i = 6 - 2 = 4$ -ə bərabərdir.

$A_{j} \leq 2 \cdot A_{i}$ olduğu müddətdə $j$ -ni irəliləyin.

İndi $A_{j} > 2 \cdot A_{i}$ . $i = 3$ üçün cavabı çap edin (bu, $j - i = 8 - 3 = 5$ -dir) və $i$ -ni 1 artırın.

Giriş məlumatlarını oxuyun.

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

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

$res$ -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 $res$ -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);

Gəlin iki göstərici $i$ və $j$ ilə sürüşdürmə pəncərəsi tətbiq edək. Hər bir sabit $i = 1, 2, ...$ üçün $[i ... j]$ intervalını mümkün qədər genişləndirin, belə ki, elementlərinin cəmi $x$ -i keçməsin. Başqa sözlə, hər $i$ üçün, $[i ... j]$ intervalındakı elementlərin cəminin $x$ -i keçmədiyi, $[i ... j + 1]$ intervalındakı elementlərin cəminin $x$ -i keçdiyi ən böyük $j$ -ni axtarın.

Gəlin $s$ -ni $[i ... j]$ intervalındakı ədədlərin cəmi ilə saxlayırıq. Əgər $s + a [j + 1] \leq m$ olarsa, $[i ... j + 1]$ intervalını genişləndirin. Əks halda, $[i + 1... j]$ intervalını daraldın. $x$ -ə bərabər olan alt massivlərin sayını hesablayın.

Nümunə

Gəlin verilmiş nümunə üçün göstəricilərin hərəkətini araşdıraq.

$i = 0$ , $j$ irəliləyir ki, $[i ... j]$ intervalındakı ədədlərin cəmi $x = 7$ -i keçməsin. $[0...2]$ intervalında dayanırıq, çünki burada ədədlərin cəmi $7$ -dir, $[0...3]$ intervalında isə cəmi artıq $9$ -dur.
$i = 1$ , $j$ irəliləyir ki, $[i ... j]$ intervalındakı ədədlərin cəmi $x = 7$ -i keçməsin. $[1...3]$ intervalında dayanırıq, çünki burada cəmi $7$ -dir, $[1...4]$ intervalında isə cəmi $14$ -dür.
$i = 2$ , nəzərdən keçirilən interval $[2...3]$ -dür. Burada ədədlərin cəmi $3$ -dür, amma $[2...4]$ intervalında cəmi $10$ -dur, bu da $7$ -dən çoxdur.
$i = 3$ , nəzərdən keçirilən interval $[3...3]$ -dür. Burada ədədlərin cəmi $2$ -dir, amma $[3...4]$ intervalında cəmi $9$ -dur, bu da $7$ -dən çoxdur.
$i = 4$ , nəzərdən keçirilən interval $[4...4]$ -dür. Burada ədədlərin cəmi $7$ -dir.

$x = 7$ olan alt massivlərin sayı $3$ -dür. Onlar $0, 1$ və $4$ indekslərində başlayırlar.

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]$ olaraq təyin edin. Bu intervaldakı ədədlərin cəmi $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]$ intervalındakı $s$ -ni yenidən hesablayın.

  s -= a[i];
}

Cavabı çap edin.

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

Ziya sabah ardıcıllıq müsabiqəsində iştirak edəcək. $x \geq 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$ 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}$ 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})$ var. Növbəti sətirdə $n$ tam ədəd $a_{i} (1 \leq a_{i} \leq 1 0^{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

Gəlin $v$ giriş ədədləri massivini nəzərdən keçirək. İki göstəricini $i = 0$ massivinin əvvəlində və $j = n - 1$ massivinin sonunda təyin edək. Gücünü dəyişəndə $k$ -ni sayırıq. Başlanğıcda, $k = 1$ -dir.

Göstəricilər $i$ və $j$ görüşənə qədər aşağıdakı əməliyyatları yerinə yetirin:

$k$ -ya bərabər olmayan ədədlərə rast gəlmədiyi müddətdə, göstərici $i$ -ni sağa doğru bir yerə keçirin.
$k$ -ya bərabər olmayan ədədlərə rast gəlmədiyi müddətdə, göstərici $j$ -ni sola doğru bir yerə keçirin.
Hər iki göstərici $k$ -ya bərabər olduqda, $k$ -ni bir artırın və hər bir göstəricini müvafiq istiqamətdə bir mövqe irəlilədin.

Alqoritm tamamlandıqda, cavab $k - 1$ dəyəri olacaq.

Nümunə

İkinci testi nəzərdən keçirək. Göstəriciləri başla. Göstərici $i$ -ni sağa, göstərici $j$ -ni sola doğru hərəkət etdirin ki, hər iki göstərici $1$ -ə bərabər olsun.

Göstərici $i$ -ni sağa, göstərici $j$ -ni sola doğru hərəkət etdirin ki, hər iki göstərici $2$ -yə bərabər olsun.

Göstəricilər görüşür, alqoritmi dayandırın. Cavab $k = 2$ olacaq.

Problemlərin siyahısı

Şərhlər (5)

azimzadenihad•11 ay öncə

thanks for all

Eltaj13•11 ay öncə

Thanks for the problems!

drizzy•12 ay öncə

Thanks for the problems! Will there be future topic contests like these ?

medv•12 ay öncə•2-ci təftiş

drizzy Thanks a lot if you liked it. By the way, problems "Competition of sequences", "The best team" and "Radio 106 FM" are taken from the past official Azerbaijan School Competitions

drizzy•12 ay öncə

medv Please continue this series of topic wise contests. Thanks

Yüklənir

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