•Статті•12 місяців тому

Техніка двох вказівників

Техніка двох вказівників — це стратегія, яка часто використовується в комп'ютерних науках і програмуванні для вирішення задач, пов'язаних з масивами або послідовностями. Вона полягає в тому, що використовуються два вказівники, які проходять масив або послідовність з різних позицій, часто рухаючись в протилежних напрямках або з різними швидкостями. Ця техніка особливо корисна для вирішення задач, пов'язаних з пошуком, оптимізацією або маніпуляцією масивами ефективно.

Ось детальний опис того, як працює техніка двох вказівників:

Ініціалізація: Спочатку ви встановлюєте два вказівники, зазвичай на різних позиціях в масиві або послідовності.
Рух: Ви ітеративно рухаєте вказівники на основі певних умов, поки вони не зустрінуться або не досягнуть певної умови. Рух вказівників можна контролювати на основі вимог задачі. Наприклад, один вказівник може рухатися швидше, ніж інший, або вони можуть рухатися в протилежні напрямки.
Перевірка умов: На кожному кроці ітерації ви перевіряєте певні умови на основі вимог задачі. Ці умови часто визначають, чи потрібно рухати вказівники, оновлювати деякі змінні або виконувати інші операції.
Завершення: Процес триває, поки один або обидва вказівники не досягнуть кінця масиву або послідовності, або поки не буде виконана якась інша умова завершення.

Техніка двох вказівників особливо корисна в задачах, що стосуються пошуку пар або підмасивів, які відповідають певним критеріям, знаходження оптимальних рішень або маніпуляції послідовностями ефективно без використання вкладених циклів. Вона часто забезпечує більш ефективне рішення порівняно з методами брутального перебору, особливо для задач з лінійними або логарифмічними вимогами до часу складності.

Зберігайте числа в лінійному масиві. Потім виведіть їх у зворотному порядку.

Розглянемо розв'язання для реверсії масиву з використанням техніки двох вказівників.

Встановіть дві змінні $i$ та $j$ (назвемо їх вказівниками):

$i$ на початку масиву $(i = 1)$ ;
$j$ в кінці масиву $(j = n)$ ;

Далі розпочніть цикл while, в якому:

значення $m [i]$ та $m [j]$ обмінюються;
потім $i$ інкрементується на $1$ , а $j$ декрементується на $1$ ;

Ми продовжуємо цикл, поки вказівники $i$ та $j$ не зустрінуться.

Зверніть увагу, що значення $m [i]$ та $m [j]$ можуть бути обміняні за допомогою додаткової змінної $t e m p$ , виконавши три операції:

Хусейн та Ярослав грають у карткову гру. На столі викладено $n$ карт, кожна з яких має написане різне число. Гравці грають по черзі. Хусейн розпочинає гру. На кожному ходу гравець може взяти або найліву, або найправу карту. Гравець завжди вибирає карту з найбільшим числом. Гра закінчується, коли на столі не залишиться карт. Знайдіть суму чисел на картах, зібраних Хусейном та Ярославом наприкінці гри.

Вхідні дані. Перший рядок містить число карт $n (1 \leq n \leq 10000)$ на столі. Другий рядок містить $n$ позитивних цілих чисел, кожне з яких вказує число на карті. Всі числа не перевищують $1 0^{9}$ .

Вихідні дані. Виведіть суму чисел на картах, зібраних Хусейном та Ярославом наприкінці гри.

Відкрити задачу

Нехай масив $m$ містить числа, написані на картах. Ініціалізуємо вказівники $i = 0$ на початку масиву і $j = n - 1$ в кінці масиву.

На кожному ході гравець бере карту з максимальною вартістю $ma x (m [i], m [j])$ , після чого карта видаляється зі столу (виконуйте операцію $i + +$ , якщо вибрано карту $m [i]$ , і $j - -$ , якщо вибрано карту $m [j]$ ). Для кожного гравця ми відстежуємо суму обраних карт у двох змінних. Процес триває, поки всі карти не будуть видалені зі столу, тобто поки вказівники $i$ та $j$ не зустрінуться.

Приклад

Гра проходитиме наступним чином.

Оголосіть масиви. Суму чисел на картах, зібраних Хусейном та Ярославом, буде збережено в $res [0]$ та $res [1]$ , відповідно.

int m[10001], res[2];

Прочитайте вхідні дані.

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

Встановіть вказівники $i = 0$ та $j = n - 1$ .

i = 0; j = n - 1;

Гравці грають по черзі, здійснюючи в цілому $n$ ходів. Хусейн грає на парних $k$ , а Ярослав грає на непарних $k$ . Таким чином, сума Хусейна накопичуватиметься в $res [0]$ , а сума Ярослава в $res [1]$ .

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

На кожному ході гравець вибирає карту з максимальною вартістю $ma x (m [i], m [j])$ .

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

Виведіть відповідь.

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

Хусейн виклав $n$ карт в ряд з числами $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . Потім він зібрав їх і розмістив в іншому порядку: $a_{1}, a_{3}, a_{5}, ..., a_{6}, a_{4}, a_{2}$ . Це послідовність, яку він дав Ярославу. Ваше завдання — допомогти Ярославу відновити початкову послідовність Хусейна.

Наприклад, якщо Ярослав отримав послідовність $(2, 4, 9, 4, 7, 6)$ , тоді він повинен повернути послідовність $(2, 6, 4, 7, 9, 4)$ Хусейну.

Вхідні дані. Перший рядок містить одне ціле число $n (1 \leq n \leq 10000)$ , що представляє кількість карт. Другий рядок містить $n$ позитивних цілих чисел, написаних на картах. Всі числа не перевищують $1 0^{9}$ .

Вихідні дані. Виведіть початкову послідовність Хусейна.

Відкрити задачу

Хусейн має рядок, що складається з символів $0$ та $1$ . Щоб розважити себе, він вигадував таку гру. Хусейн може виконати одну з двох операцій зі рядком:

додати $0$ на лівий кінець, а $1$ на правий кінець;
додати $0$ на правий кінець, а $1$ на лівий кінець;

Наприклад, з рядка $010$ Хусейн може отримати $00101$ або $10100$ .

Вам дано рядок, отриманий після всіх операцій Хусейна (можливо, він не виконував жодної операції). Визначте найменшу можливу довжину, яку рядок міг спочатку мати.

Вхідні дані. Один рядок довжиною не більше $1 0^{5}$ , що складається лише з символів $0$ та $1$ .

Вихідні дані. Виведіть найменшу можливу довжину рядка, який Хусейн міг спочатку мати.

Відкрити задачу

Розглянемо вхідний рядок $s$ — отриманий рядок після того, як Хусейн виконав всі операції. Ініціалізуйте два вказівники: $i = 0$ на початку рядка та $j = n - 1$ в його кінці.

Якщо $s_{i} \neq = s_{j}$ , тоді символи на кінцях рядка різні: або $0$ зліва, а $1$ справа, або $1$ зліва, а $0$ справа. Це означає, що попередній рядок міг бути розширений, застосувавши одну з вказаних операцій. У цьому випадку перемістіть обидва вказівники $i$ та $j$ на одну позицію один до одного і знову перевірте, чи можна отримати підрядок $s [i ... j]$ через операції Хусейна.

Як тільки поточний підрядок $s [i ... j]$ задовольняє умові $s_{i} = s_{j}$ , його більше не можна отримати за допомогою вказаних операцій. Виведіть його довжину — це початковий рядок, який мав Хусейн.

Приклад

Розглянемо операції Хусейна в зворотному порядку.

Рядок $s = "1"$ спочатку був рядком Хусейна.

Прочитайте вхідний рядок і обчисліть його довжину, зберігши її в змінній $res$ .

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

Ініціалізуйте два вказівники: $i = 0$ на початку та $j = n - 1$ в кінці рядка.

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

Якщо $s_{i} \neq = s_{j}$ , тоді символи на кінцях рядка різні. Хусейн міг отримати підрядок $s [i ... j]$ з підрядка $s [i + 1... j - 1]$ .

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

Перемістіть обидва вказівники $i$ та $j$ на одну позицію один до одного та зменшіть поточний розмір $res$ підрядка $s [i ... j]$ .

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

Виведіть відповідь.

cout << res << endl;

Дано масив $A$ , відсортований у зростаючому порядку та що містить $n$ цілих чисел. Визначте, чи існує пара чисел $(A_{i}, A_{j})$ , де $i < j$ , така що їхня сума дорівнює $x$ .

Вхідні дані. Перший рядок містить два цілі числа $n (n \leq 1 0^{5})$ та $x (x \leq 1 0^{6})$ . Другий рядок містить $n$ невід'ємних цілих чисел, кожне з яких не більше $1 0^{6}$ .

Вихідні дані. Виведіть "YES", якщо така пара елементів існує, і "NO" в іншому випадку.

Відкрити задачу

Нехай $v$ буде вхідним масивом чисел. Ініціалізуйте вказівники $i = 0$ на початку масиву та $j = n - 1$ в кінці масиву. Масив вже відсортовано відповідно до умов задачі.

Поки вказівники $i$ та $j$ не зустрінуться, виконуйте такі дії:

Якщо $v_{i} + v_{j} = x$ , тоді бажана пара елементів знайдена. Виведіть її та завершіть програму.
Якщо $v_{i} + v_{j} < x$ , перемістіть вказівник $i$ на одну позицію вправо. У цьому випадку сума $v_{i} + v_{j}$ зросте;
Якщо $v_{i} + v_{j} > x$ , перемістіть вказівник $j$ на одну позицію вліво. У цьому випадку $v_{i} + v_{j}$ зменшиться;

Приклад

Розглянемо перший тест. Ініціалізуйте вказівники. Моделюйте роботу алгоритму. Значення $x = 13$ , ми шукаємо два числа, сума яких дорівнює $13$ .

Прочитайте вхідні дані.

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

Ініціалізуйте вказівники.

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

Перемістіть вказник $i$ вперед і вказник $j$ назад.

while (i < j)
{

Якщо $v_{i} + v_{j} = x$ , тоді бажана пара елементів знайдена. Виведіть її та завершіть програму.

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

Якщо $v [i] + v [j] < x$ , тоді перемістіть вказник $i$ на одну позицію вправо;

Якщо $v [i] + v [j] > x$ , тоді перемістіть вказник $j$ на одну позицію вліво;

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

Якщо бажана пара не знайдена, виведіть "NO".

printf("NO\n");

Дано масив цілих чисел $A$ та ціле число $x$ . Знайдіть трійку чисел $(A_{i}, A_{j}, A_{k})$ у масиві, чия сума дорівнює $x$ . Всі індекси $i, j, k$ повинні бути різними.

Вхідні дані. Перший рядок містить розмір масиву $n (n \leq 3 \cdot 1 0^{4})$ та значення $x (∣ x ∣ \leq 1 0^{9})$ . Другий рядок містить $n$ цілих чисел, кожне з яких не перевищує $1 0^{8}$ за абсолютним значенням.

Вихідні дані. Якщо потрібна трійка існує, виведіть її в будь-якому порядку. Якщо існує кілька трійок, виведіть будь-яку з них. Якщо бажана трійка не існує, виведіть $- 1$ .

Відкрити задачу

Прочитайте вхідні дані.

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

Відсортуйте вхідний масив.

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

Переберіть значення $k = 0, 1, ..., n - 3$ .

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

Знайдіть пару індексів $(i, j)$ таку, що $i > k$ та $v_{i} + v_{j} = x - v_{k} (i < j)$ . Ініціалізуйте індекси $i$ та $j$ .

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

Використовуйте техніку двох вказівників для знаходження бажаної пари $(i, j)$ .

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

Якщо пара $(i, j)$ знайдена, виведіть бажану трійку чисел $(v_{k}, v_{i}, v_{j})$ .

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

Якщо $v [i] + v [j] < s$ , тоді перемістіть вказник $i$ на одну позицію вправо;

Якщо $v [i] + v [j] > s$ , тоді перемістіть вказник $j$ на одну позицію вліво;

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

Якщо трійка чисел не знайдена, виведіть $- 1$ .

cout << -1 << endl;

Дано відсортований масив $A$ з $n$ цілих чисел. Для кожного індексу $i$ знайдіть кількість елементів у масиві, які лежать між $A_{i}$ та $2 \cdot A_{i}$ включно.

Вхідні дані. Перший рядок містить розмір $n (n \leq 1 0^{5})$ масиву $A$ . Другий рядок містить $n$ цілих чисел, які перебувають у відсортованому порядку.

Вихідні дані. Виведіть $n$ цілих чисел. Для кожного індексу $i (1 \leq i \leq n)$ масиву виведіть кількість елементів, які лежать між $A_{i}$ та $2 \cdot A_{i}$ включно.

Відкрити задачу

Інтервал $A [i ... j]$ буде називатися добрим, якщо числа в ньому лежать в межах $[A_{i}; 2 \cdot A_{i}]$ включно (означає, що $A_{j} \leq 2 \cdot A_{i}$ ).

Ми реалізуємо зсувне вікно, використовуючи два вказівники $i$ та $j$ та підтримуватимемо його так, щоб поточне інтервал $[i ... j]$ був добрим, поки інтервал $[i ... j + 1]$ є поганим.

Наприклад, для наступної послідовності:

інтервали $[2; 2], [2; 3], [2; 4]$ , і $[2; 5]$ є добрими.
інтервали $[2; 6], [2; 7]$ є поганими.

Якщо $A_{j} \leq 2 \cdot A_{i}$ , розширте поточний інтервал до $А [i ... j + 1]$ . В іншому випадку, скоротіть його до $А [i + 1... j]$ . Перед тим, як перемістити вказник $i$ , виведіть кількість елементів, які лежать між $A_{i}$ та $2 \cdot A_{i}$ включно. Вона дорівнює $j - i$ .

Складність алгоритму лінійна, тобто $O (n)$ .

Приклад

Розглянемо переміщення вказівників для даного прикладу.

Для заданої умови $A_{j} \leq 2 \cdot A_{i}$ , отже, ми переміщаємо вказівник $j$ вперед.

Тепер $A_{j} > 2 \cdot A_{i}$ . Ми повинні перемістити вказник $i$ вперед. Проте, перш ніж перемістити його, виведіть кількість елементів, які лежать між $A_{i}$ та $2 \cdot A_{i}$ включно. Вона дорівнює $j - i = 6 - 2 = 4$ .

Перемістіть $j$ вперед, поки $A_{j} \leq 2 \cdot A_{i}$ .

Тепер $A_{j} > 2 \cdot A_{i}$ . Виведіть відповідь для $i = 3$ (вона дорівнює $j - i = 8 - 3 = 5$ ) та збільшіть $i$ на $1$ .

Вдоль прекрасного Адріатичного узбережжя знаходяться $n$ готелів. Кожен готель має свою вартість у євро. Петро виграв $m$ євро в лотереї. Тепер він хоче купити послідовність сусідніх готелів один за одним так, щоб сума витрат на ці сусідні готелі була якомога більшою, але не перевищувала $m$ .

Вам потрібно обчислити цю максимальну можливу загальну вартість.

Вхідні дані. Перший рядок містить два цілі числа $n$ та $m (1 \leq n \leq 3 \cdot 1 0^{5}, 1 \leq m < 2^{31})$ . Наступний рядок містить $n$ позитивних цілих чисел, які представляють витрати на готелі в порядку їх розташування уздовж узбережжя.

Вихідні дані. Виведіть бажану максимальну вартість (вона буде більшою за $0$ в усіх тестах).

Відкрити задачу

Зберігайте витрати на готелі в масиві $a$ . Позначимо інтервал $[i ... j]$ як добрий, якщо сума витрат у ньому не перевищує $m$ .

Реалізуємо зсувне вікно, використовуючи два індекси $i$ та $j$ , і підтримуватимемо його так, щоб поточний інтервал $[i ... j]$ був добрим. Нехай $s$ буде сумою витрат у межах інтервалу $[i ... j]$ . Якщо $s + a [j + 1] \leq m$ , тоді розширюємо поточний інтервал до $a [i ... j + 1]$ . Інакше скорочуємо його до $a [i + 1... j]$ . Знайдіть максимум серед витрат усіх розглянутих добрих інтервалів.

Приклад

Розглянемо переміщення вказівників для даного прикладу.

Коли $i = 0, j$ рухається вперед, поки сума чисел у інтервалі $[i ... j]$ не перевищить $m = 12$ . Зупиніться на інтервалі $[0...3]$ , тому що сума там дорівнює $10$ , тоді як сума в інтервалі $[0...4]$ дорівнює $15$ .
Коли $i = 1$ , ми не можемо перемістити $j$ вперед, оскільки сума в інтервалі $[1...4]$ дорівнює $13$ .
Коли $i = 2$ , перемістіть $j$ вперед до інтервалу $[2...4]$ .

Максимальне значення серед усіх добрих інтервалів дорівнює $12$ і досягається в інтервалі $[2...4]$ .

Прочитайте вхідні дані.

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

Ініціалізуйте змінні:

в $res$ обчислюється максимальне значення серед витрат усіх оброблених добрих інтервалів;
в $s$ підтримується сума чисел у поточному інтервалі $[i ... j]$ . Всі числа в поточному інтервалі $[i ... j]$ зберігаються в черзі $q$ ;

s = res = 0;

Обробляйте витрати на готелі послідовно.

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

Прочитайте та додайте витрати $v a l$ поточного готелю до черги.

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

Оновіть суму $s$ в межах інтервалу. Всі елементи поточного інтервалу зберігаються в черзі $q$ .

  s += val;

Якщо сума чисел у поточному інтервалі перевищує $s$ , видалите елементи з початку інтервалу.

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

Обчисліть максимальне значення $res$ серед сум елементів у добрих інтервалах (де витрати на готелі не перевищують $m$ ).

  if (s > res) res = s;
}

Виведіть відповідь.

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

Реалізуємо зсувне вікно, використовуючи два вказівники $i$ та $j$ . Для кожного фіксованого $i = 1, 2, ...$ , розширюйте інтервал $[i ... j]$ наскільки це можливо, так щоб сума його елементів не перевищувала $x$ . Іншими словами, для кожного $i$ шукайте найбільше можливе $j$ , так що сума елементів в інтервалі $[i ... j]$ не перевищує $x$ , тоді як сума елементів в інтервалі $[i ... j + 1]$ перевищує $x$ .

Нехай $s$ буде сумою чисел в інтервалі $[i ... j]$ . Якщо $s + a [j + 1] \leq m$ , розширте інтервал до $[i ... j + 1]$ . В іншому випадку скоротіть його до $[i + 1... j]$ . Підрахуйте кількість інтервалів з сумою $x$ .

Приклад

Розглянемо переміщення вказників для даного прикладу.

$i = 0$ , $j$ рухається вперед, поки сума чисел в інтервалі $[i ... j]$ не перевищить $x = 7$ . Ми зупиняємося на інтервалі $[0...2]$ , оскільки сума чисел в ньому дорівнює $7$ , тоді як в інтервалі $[0...3]$ сума чисел вже дорівнює $9$ .
$i = 1$ , $j$ рухається вперед до $3$ . Сума чисел в інтервалі $[1...3]$ дорівнює $7$ , тоді як в інтервалі $[1...4]$ вже дорівнює $14$ .
$i = 2$ , розглянутий інтервал — $[2...3]$ . Сума чисел у ньому дорівнює $3$ , але ми не можемо рухати індекс $j$ вперед, оскільки сума чисел в інтервалі $[2...4]$ перевищує $10$ , що є більшим, ніж $x = 7$ .
$i = 3$ , розглянутий інтервал — $[3...3]$ . Сума чисел у ньому дорівнює $2$ , але ми не можемо рухати індекс $j$ вперед, оскільки сума чисел в інтервалі $[3...4]$ перевищує $9$ , що є більшим, ніж $x = 7$ .
$i = 4$ , розглянутий інтервал — $[4...4]$ . Сума чисел у ньому дорівнює $7$ .

Кількість підмасивів з сумою $x = 7$ дорівнює $3$ . Вони починаються на індексах $0, 1$ та $4$ .

Оголосіть масив.

#define MAX 200001
long long a[MAX];

Прочитайте вхідні дані.

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

Спочатку встановіть поточний інтервал $[i ... j] = [0; 0]$ . Сума чисел у цьому інтервалі дорівнює $s = 0$ .

s = j = 0;

Для кожного значення $i$ послідовно обробляйте інтервали $[i ... j]$ .

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

Для фіксованого лівого краю $i$ інтервалу $[i ... j]$ шукайте найбільше $j$ , так що сума елементів у цьому інтервалі не перевищує $x$ .

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

Якщо сума чисел $s$ у поточному інтервалі $[i ... j]$ дорівнює $x$ , збільшуйте підрахунок бажаних підмасивів $c n t$ на $1$ .

  if (s == x) cnt++;

Перепідрахуйте суму $s$ для інтервалу $[i + 1... j]$ .

  s -= a[i];
}

Виведіть відповідь.

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

Зія візьме участь у конкурсі послідовностей завтра. Число $x \geq 0$ називається вершиною деякої послідовності, якщо послідовність $1, 2, 3, ..., x - 1, x, x - 1, ..., 3, 2, 1$ є підпослідовністю цієї послідовності. Сила кожної послідовності вважається її найбільшою вершиною.

Завтра всі студенти візьмуть участь у конкурсі, а переможець найсильнішої послідовності буде переможцем. Зія має послідовність $a_{1}, a_{2}, a_{3}, ..., a_{n}$ . Він хоче зайняти систему оцінювання конкурсу, видаливши з неї послідовності з більшою силою, ніж у себе. Однак Зія не знає сили своєї власної послідовності, але дуже хоче виграти. Допоможіть йому обчислити силу своєї послідовності.

Вхідні дані. Перший рядок містить число $n (1 \leq n \leq 1 0^{5})$ чисел у послідовності Зії. Наступний рядок містить $n$ цілих чисел $a_{i} (1 \leq a_{i} \leq 1 0^{5})$ — елементи послідовності.

Вихідні дані. Виведіть одне число — силу даної послідовності.

Відкрити задачу

Нехай $v$ буде вхідним масивом чисел. Ініціалізуйте вказівники $i = 0$ на початку масиву та $j = n - 1$ в кінці масиву. Ми будемо підраховувати силу послідовності у змінній $k$ . Спочатку встановіть $k = 1$ .

Поки вказівники $i$ та $j$ не зустрінуться, виконуйте такі дії:

Перемістіть вказівник $i$ на одну позицію вправо, якщо він не вказує на число $k$ .
Перемістіть вказівник $j$ на одну позицію вліво, якщо він не вказує на число $k$ .
Якщо обидва вказівники вказують на число $k$ , збільшіть $k$ на одиницю та перемістіть кожен вказівник на одну позицію в відповідному напрямку.

Після завершення алгоритму відповідь буде значенням $k - 1$ .

Приклад

Розглянемо другий тест. Ініціалізуйте вказівники. Перемістіть вказівник $i$ вправо та вказівник $j$ вліво, поки вони обидва не вкажуть на число $1$ .

Перемістіть вказник $i$ вправо та вказник $j$ вліво, поки вони обидва не вкажуть на число $2$ .

Вказівники зустрічаються, ми зупиняємо алгоритм. Відповідь буде значенням $k = 2$ .

Прочитайте вхідні дані.

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

Встановіть вказники на початок та кінець масиву $v$ .

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

У змінній $k$ ми підраховуємо силу послідовності.

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

Перемістіть вказник $i$ вправо, поки він не зустріне число $k$ .

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

Перемістіть вказник $j$ вліво, поки він не зустріне число $k$ .

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

Якщо обидва вказники вказують на число $k$ , тоді збільшуйте $k$ на одиницю.

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

Виведіть відповідь.

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

Список задач

Коментарі (5)

azimzadenihad•11 місяців тому

thanks for all

Eltaj13•12 місяців тому

Thanks for the problems!

drizzy•1 рік тому

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

medv•1 рік тому•2-а ревізія

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•1 рік тому

medv Please continue this series of topic wise contests. Thanks

Завантаження

Секундочку, отримую дані з серверу