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

## [1. Самый маленький огород](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2017_1)
:::spoiler Разбор
:::info
$S_{трапеции} = \frac{a + b}{2} * h = (a + b) * \frac{h}{2}$.
По условию $h = 50$, тогда ответ равен $min(L_i + L_{i - 1}) * 25$ для всех $i$ от $2$ до $n$.

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

var
n,i:longint;
a,b,s,ms:longint;
begin
   read(n);
   read(a,b);
   ms:=(a+b)*25;
   while not seekeof(input) do begin
      a:=b;
      read(b);
      s:=(a+b)*25;
      if s < ms then ms := s;
   end;
   writeln(ms);
end.

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

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

int main() {
    int n;
    cin >> n;
    long long last;
    cin >> last;
    long long ot = 1e18;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        ot = min((last + x) * 25, ot);
        last = x;
    }
    cout << ot << endl;
    return 0;
}

:::

## [2. Выбор костюма](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2017_2)
:::spoiler Разбор
:::info
Давайте для каждого $a_i$ посчитаем максимальное значение ($mx\_b[a_i]$) $b_i$ и их количество $kol[a_i]$. Заметим, что немаксимальные значения $b_i$ для каждого из $a_i$ не входят в ответ.

Теперь пройдемся по всем $a$ с конца и будем хранить максимальное значение ($mx$) среди всех $mx\_b[i]$ ($a \leq i \leq 1000$). Если мы обновляем значение $mx$, то мы точно сохраним эти платья. Другие платья удалятся, т.к мы идем с конца и значение текущего $mx > mx\_b[a]$.

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

var
mb:array[1..1000] of integer;
mbk:array[1..1000] of integer;
n,i,r:longint;
a,b,maxb:integer;
begin
   for i:=1 to 1000 do begin
      mb[i]:=0;
      mbk[i]:=0;
   end;
   read(n);
   for i:=1 to n do begin
      read(a,b);
      if b > mb[a] then begin
	 mb[a]:=b;
	 mbk[a]:=1;
      end
      else if b = mb[a] then mbk[a]:=mbk[a]+1;
   end;
   r:=0;
   maxb:=0;
   for i:=1000 downto 1 do
      if mb[i]>maxb then begin
	 r:=r+mbk[i];
	 maxb:=mb[i];
      end;
   writeln(r);
end.

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

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

int main() {
    int n;
    cin >> n;
    map<int, int> mp;
    map<int, int> kol;
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        if (mp[a] < b) mp[a] = b, kol[a] = 1;
        else if (mp[a] == b) kol[a]++;
    }
    int ans = 0;
    int ma = 0;
    for (int i = 1000; i >= 0; --i)
        if (mp[i] > ma) ma = mp[i], ans += kol[i];
    cout << ans << endl;
    return 0;
}

:::

## [3. Четные цифры](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2017_3)
:::spoiler Разбор
:::info
Давайте напишем ДП по цифрам: $dp[префикс][флажок] = ответ$.

Давайте напишем наше $dp$ с 3-мя флажками.

$i$ -- 0-индексация.

$dp[i][0]$ -- количество четных цифр для всех чисел длины $i + 1$. Все числа строго меньше нашего префикса длины $i$.
$dp[i][1]$ -- количество четных цифр для всех чисел длины $i + 1$. Все числа равны нашему префиксу длины $i$.
$dp[i][2]$ -- количество четных цифр для всех чисел длины $i + 1$. Все числа строго больше нашего префикса длины $i$.

Самое главное в этой задаче -- заметить, что когда мы добавляем очередную
четную цифру, то ответ увеличивается не на $1$, а на количество чисел, которые
соответсвуют $[префикс][флажок]$.
Тогда нам нужно поддерживать количество чисел, которые имеют длину нашего
текущего префикса и, взависимости от флажка, либо $<$, либо $=$, либо $>$.

Для тренировки мы можем считать такую матрицу с помощью ДП по цифрам.

Асимптотика: $O(len * 10)$, где $len$ -- длина исходного числа.
:::
:::spoiler Авторское решение (Pascal)

var
zn, bl: array[0..11] of int64;
procedure initc;
var
i :integer;
pw :int64;   
begin
   zn[0]:=0;
   bl[0]:=0;
   pw:=1;
   for i:=1 to 11 do begin
      zn[i]:=4*pw+9*bl[i-1];
      bl[i]:=5*pw+10*bl[i-1];
      pw:=pw*10;
   end;
end;
function count(x : longint):int64;
var
pw:int64;
k:int64;
n,d:integer;
begin
   pw:=1;
   n:=1;
   k:=0;
   while x >= 10*pw do begin
      k:=k+zn[n];
      n:=n+1;
      pw:=pw*10;
   end;
   d:=x div pw;
   x:=x-d*pw;
   k:=k+(d-1)*bl[n-1]+((d-1) div 2 )*pw;
   if (d>0) and (d mod 2 = 0) then k := k+x+1;
   n:=n-1;
   pw:=pw div 10;
   while n > 0 do begin
      d:=x div pw;
      x:=x-d*pw;
      k:=k+d*bl[n-1]+((d+1) div 2 )*pw;
      if d mod 2 = 0 then k := k+x+1;
      n:=n-1;
      pw:=pw div 10;
   end;
   count:=k;
end;
var
   a,b	 : longint;
   ka,kb : int64;
   f	 : text;
begin
   initc;
   read(a,b);
   ka:=count(a-1);
   kb:=count(b);
   writeln(kb-ka);
end.

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

#include <bits/stdc++.h>

#define ll long long
#define pb push_back

#pragma GCC optimize("Ofast")

using namespace std;

ll dp[10][3];
int kol[10][3];

ll solve(int val){
    if (!val)return 0;
    for (int i = 0;i < 10; ++i){
        for (int j = 0;j < 3; ++j){
            dp[i][j] = 0;
            kol[i][j] = 0;
        }
    }
    vector < int > a;
    while(val){
        a.pb(val % 10);
        val /= 10;
    }
    reverse(a.begin(), a.end());
    int n = a.size();
    for (int i = 1;i <= 9; ++i){
        if (i < a[0])dp[0][0] += !(i % 2), kol[0][0]++;
        else if (i == a[0])dp[0][1] += !(i % 2), kol[0][1]++;
        else dp[0][2] += !(i % 2), kol[0][2]++;
    }
    for (int i = 1;i < n; ++i){
        for (int c = 0;c < 10; ++c){
            int need = !(c % 2);
            kol[i][0] += kol[i - 1][0];
            kol[i][2] += kol[i - 1][2];

            dp[i][0] += dp[i - 1][0] + need * kol[i - 1][0];
            dp[i][2] += dp[i - 1][2] + need * kol[i - 1][2];

            if (c < a[i]){
                kol[i][0] += kol[i - 1][1];
                dp[i][0] += dp[i - 1][1] + need * kol[i - 1][1];
            }else if (c == a[i]){
                kol[i][1] += kol[i - 1][1];
                dp[i][1] += dp[i - 1][1] + need * kol[i - 1][1];
            }else{
                kol[i][2] += kol[i - 1][1];
                dp[i][2] += dp[i - 1][1] + need * kol[i - 1][1];
            }
        }
    }
    ll ans = 0;
    for (int i = 0;i < n; ++i){
        if (i == n - 1)ans += dp[i][0] + dp[i][1];
        else ans += dp[i][0] + dp[i][1] + dp[i][2];
    }
    return ans;
}

int32_t main() {
    int a, b;
    cin >> a >> b;
    cout << solve(b) - solve(a - 1) << endl;
    return 0;
}

:::

## [4. Неинтересный лабиринт](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2017_4)
:::spoiler Разбор
:::info
Давайте посчитаем $dp_i$ -- минимальное количество энергии, которая потребуется, чтобы дойти от $i$ до $n$. Считаем динамику с конца.
Переход: $dp_i = min(dp_{i + 1} + a_{i + 1}, dp_{i + 2} + a_{i + 2})$

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

var
n,i:longint;
a:array[1..1000000]of longint;
r:array[0..1000000]of int64;
begin
   read(n);
   for i:=1 to n do
      read(a[i]);
   r[n]:=0;
   r[n-1]:=a[n];
   for i:=n-2 downto 1 do begin
      if r[i+1]+a[i+1] < r[i+2]+a[i+2] then r[i]:=a[i+1]+r[i+1]
      else r[i]:=a[i+2]+r[i+2];
      if r[i]<0 then r[i]:=0;
   end;
   writeln(r[1]);
end.

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

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

int main() {
    int n;
    cin >> n;
    long long dp[n+1];
    int a[n+1];
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    dp[n] = 0;
    dp[n-1] = a[n];
    for (int i = n-2; i >= 1; --i) {
        dp[i] = min(dp[i+1] + a[i+1], dp[i+2] + a[i+2]);
        if (dp[i] < 0)
            dp[i] = 0;
    }
    cout << dp[1] << endl;
    return 0;
}

:::