# Разбор задач 2013 года
Если Вы не знали как решать какую-то задачу и Вам было лень разбираться в коде на Pascal, то это пост специально для Вас.
:::warning
Убедительная просьба не копировать коды и не пересылать их. Помните -- Вы решаете задачи для себя!
:::

## [1. Считалки](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2013_1)
:::spoiler Разбор
:::info
Самым коротким решением в этой задаче является моделирование считалок. Теперь нам нужна структура данных, которая может удалять $k$-ю порядковую статистику. Для этого идеально подойдет *ordered_set*.

Давайте хранить в *ordered_set* номера всех детей. На очередном ходу будем высчитывать номер игрока, который выйдет из круга. Удалим его из *ordered_set*. Такую несложную операцию повторим $N - 1$ раз.

Асоптотика: $O(N * log(N))$.
:::
:::spoiler Авторское решение (Pascal)

program solution;
var
   left, right, parent : array[1..25000] of longint;
   part		       : array[1..25000] of longint;
   v, node_number      : array[0..25000] of longint;
   root		       : longint;
   n, i, j	       : longint;
   cur		       : longint;
   sum		       : int64;

function init_tree(l,r,p : longint):longint;
var
   t : longint;
begin
   if l>r then init_tree:=0
   else begin
      t := (l+r) div 2;
      left[t] := init_tree(l, t-1, t);
      right[t] := init_tree(t+1, r, t);
      parent[t]:= p;
      node_number[t] := 1;
      if left[t]<>0 then
	 node_number[t] := node_number[t] + node_number[left[t]];
      if right[t]<>0 then
	 node_number[t] := node_number[t] + node_number[right[t]];
      init_tree:=t
   end
end; { init_tree }

procedure forget_node(x, y : longint);
begin
   if parent[x] = 0 then root := y
   else if left[parent[x]] = x then left[parent[x]] := y
   else right[parent[x]] := y;
   if y<>0 then parent[y] := parent[x]
end; { forget_node }

procedure delete_node(x	: longint);
var
   y,z : longint;
begin
   if left[x]=0 then forget_node(x, right[x])
   else if right[x] = 0 then forget_node(x, left[x])
   else begin
      y := right[x];
      while left[y] <> 0 do y := left[y];
      z:=part[y];
      part[y]:=part[x];
      part[x]:=z;
      forget_node(y, right[y]);
      x:=y;
   end;
   x:=parent[x];
   while x<>0 do begin
      node_number[x] := node_number[x] - 1;
      x := parent[x];
   end
end; { delete_node }

function index(i : longint):longint;
var
   t : longint;
begin
   t:=root;
   while i <> node_number[left[t]]+1 do
      if i <= node_number[left[t]] then t:=left[t]
      else begin
	 i:=i-1-node_number[left[t]];
	 t:=right[t]
      end;
   index := t;
end; { index }

begin
   read(n);
   sum:=0;
   for i:=1 to n do begin
      read(v[i]);
      part[i]:=i;
      sum:=sum+v[i];
   end;
   node_number[0]:=0;
   root:=init_tree(1,n,0);
   cur := 0;
   for i := n downto 2 do begin
      cur := (sum + cur) mod i;
      if cur = 0 then j := index(i)
      else begin
	 j:=index(cur);
	 cur := cur - 1
      end;
      sum := sum - v[part[j]];
      delete_node(j)
   end;
   writeln(part[root]);
end.

:::
:::spoiler Код (C++, автор: [Zhdun](https://codeforces.com/profile/Zhdun))

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template <typename T> using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

int main() {
    int n;
    cin >> n;
    ordered_set<int> all;
    ll sum = 0;
    int a[n + 1];
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        all.insert(i);
        sum += x;
        a[i] = x;
    }
    int nach = 1;
    int del;
    int kol;
    int pos;
    while(n > 1) {
        pos = (sum + nach - 1) % n;
        if (!pos) pos = n;
        int x = *all.find_by_order(pos - 1);
        sum -= a[x];
        all.erase(x);
        nach = pos;
        if (n - 1 < nach) nach = 1;
        n--;
    }
    cout << *all.find_by_order(0) << endl;
    return 0;
}

:::

## [2. Тренировка (упрощённая версия)](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2013_2)
:::spoiler Разбор
:::info
Считаем динамику $dp_i$ -- количество способов дойти в точку $i$.

Переход: $dp_i = \begin{cases} dp_{i - 2} + dp_{i - 3} \text{, если } i-3 \geq 0 \\ dp_{i - 2} \text{, если } i - 3 < 0 \end{cases}$

Асимптотика: $O(N)$.
:::
:::spoiler Авторское решение (Pascal)

program solution;
var 
   n,i : integer;
   f   : array[1..160] of qword;
begin
   readln(n);
   f[1]:=1;
   f[2]:=0;
   f[3]:=1;
   for i:=4 to n do
      f[i]:=f[i-2] + f[i-3];
   writeln(f[n]);
end.

:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<unsigned long long> dp(n, 0);
    dp[0] = 1;
    dp[1] = 0;
    for (int i = 2; i < n; ++i)
        dp[i] = dp[i - 2] + (i - 3 >= 0 ? dp[i - 3] : 0);
    cout << dp[n - 1] << endl;
    return 0;
}

:::

## [3. Две строки](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2013_3)
:::spoiler Разбор
:::info
Давайте переберем начало подстроки в первой строке и будем жадно набирать подпоследовательность во второй строке.

Асиптотика: $O(N^2)$.
:::
:::spoiler Авторское решение (Pascal)

program solution;
var
   s1, s2  : ansistring;
   i, j, k : integer;
   m, s, f : integer;
begin
   readln(s1);
   readln(s2);
   m:=0;
   s:=1; f:=0;
   for i:=1 to length(s1) do begin
      j:=i;
      k:=1;
      while (j<=length(s1)) and (k<=length(s2)) do begin
	 if (k<=length(s2)) and (s1[j]=s2[k]) then j:=j+1;
	 k:=k+1;
      end;
      j:=j-1;
      if m<j-i+1 then
      begin
	 m:=j-i+1;
	 s:=i;
	 f:=j;
      end;
   end;
   writeln(copy(s1,s,f-s+1));
end.

:::
:::spoiler Код (C++, автор: [Adamenko](https://codeforces.com/profile/Adamenko))

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = int(s.size());
    int m = int(t.size());
    int st_ = -1;
    int fn_ = -1;
    int ma = 0;
    for (int z = 0; z < n; ++z) {
        int i = z;
        int j = 0;
        while (i < n && j < m) {
            if (j < m && s[i] == t[j]) i++;
            j++;
        }
        --i;
        if (ma < i - z + 1) ma = i - z + 1, st_ = z, fn_ = i;
    }
    if (st_ == -1) return 0;
    for (int i = st_; i <= fn_; ++i) cout << s[i];
    return 0;
}

:::