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

## [1. Утренник](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2015_1)
:::spoiler Разбор
:::info
Делаем то, о чем просят в условии. Не забудем про *long long*, так как $N * A_i$ не влезет в *int*.
Асимптотика решения: $O(N)$.
:::
:::spoiler Авторское решение (Pascal)

var
   a : array [1..1000000] of integer;
   s : int64;
   n, i: longint;
   k, q : int64;
   r : longint;
begin
   read(n);
   s := 0;
   for i := 1 to n do begin
      read(a[i]);
      s := s + a[i]
   end;
   r := s mod n;
   if r = 0 then begin
      writeln('YES');
      k := 0;
      q := s div n;
      for i := 1 to n do
         if a[i] > q then k := k + (a[i] - q);
      writeln(k)
   end
   else begin
      writeln('NO');
      writeln(n - r)
   end;
end.

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

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    long long sum = 0;
    for (int i = 0; i < n; ++i)
        sum += a[i];
    if (sum % n == 0) {
        cout << "YES" << endl;
        long long S = 0;
        for (int i = 0; i < n; ++i)
            S += abs(a[i] - sum / n);
        cout << S / 2 << endl;
    } else {
        cout << "NO" << endl;
        long long kol = sum / n;
        long long S = (kol + 1) * n;
        cout << S - sum << endl;
    }
    return 0;
}

:::

## [2. Тайные письма](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2015_2)
:::spoiler Разбор
:::info
Давайте построим матрицу, которую нас просят, и выведем ее.

Можно вывести формулу очередной буквы.
Асимптотика: $O(N * M)$.
:::
:::spoiler Авторское решение (Pascal)

var
   s : ansistring;
   m, n, i, j : longint;
begin
   readln(n, m);
   readln(s);
   for i := 1 to n do
      for j := 1 to m do
         write(s[i + (j - 1) * n]);
   writeln;
end.

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

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

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cout << s[j*n+i];
    cout << endl;
    return 0;
}

:::

## [3. Новая архитектура](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2015_3)
:::spoiler Разбор
:::info
Давате посчитаем $dp_{i,j}$ -- максимальный размер квадрата, у которого правый нижний угол находится в матрице на позиции $(i,j)$.

Ответ будем считать как сумму всех $dp_{i,j}$, так как мы можем выбрать квадрат размера от $1$ до $dp_{i,j}$ (если текущая позиция не занята).

Переход:

1. $dp_{i,j} = min(\{dp_{i-1,j-1}, dp_{i - 1,j}, dp_{i,j - 1}\}) + 1$, если клетка свободная.

Асимптотика: $O(N^2)$.

:::
:::spoiler Авторское решение (Pascal)

var
   n, m, i, j : longint;
   a : integer;
   k : int64;
   s : array [1..2000] of int64;
   p, v : int64;
begin
   readln(n, m);
   k := 0;
   for j := 1 to m do begin
      read(a);
      s[j] := 1 - a;
      k := k + s[j]
   end;
   for i := 2 to n do begin
      read(a);
      p := s[1];
      s[1] := 1 - a;
      k := k + s[1];
      for j := 2 to m do begin
         read(a);
	 if a = 1 then begin
	    p := s[j];
	    s[j] := 0
	 end
	 else begin
	    v := p;
	    p := s[j];
	    if s[j - 1] < v then v := s[j - 1];
	    if s[j] < v then v := s[j];
	    s[j] := v + 1;
	 end;
	 k := k + s[j]
      end;
   end;
   writeln(k);
end.

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

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

int n, m;
vector<vector<int>> a;
vector<vector<int>> dp;

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

:::

## [4. Путешественники](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2015_4)
:::spoiler Разбор
:::info
Давайте бинарным поиском найдем ответ -- минимальное расстояние между двумя подряд посещенными городами. Перед этим отсортируем положения городов. В бинарном поиске жадным алгоритмом проверяем, можем ли мы выбрать города так, чтобы количество посещенных городов было как минимум $n$. Интуитивно понятно, что всегда выгодно начинать с самого ближнего города.

Асмптотика решения: $O(log(max(A_i)) * M)$.
:::
:::spoiler Авторское решение (Pascal)

var
   n, m, i, k: longint;
   x : longint;
   b: array[1..100000] of longint;
   idx : array[1..100000] of longint;
   lb, ub, st, st0: longint;
procedure up(i, n: longint);
var
   j: longint;
   x, mx, y: longint;
begin
   x := b[i]; y:=idx[i];
   repeat
      j := 2 * i;
      if j = n then mx := b[j]
      else if j < n then begin
         mx := b[j];
	 if b[j + 1] > mx then begin
	    mx := b[j + 1];
	    j := j + 1
	 end
      end;
      if (j <= n) and (x < mx) then begin
      	 b[i] := mx;
	 idx[i] := idx[j];
	 i := j
      end
   until i < j;
   b[i] := x;
   idx[i] := y;
end;
function min(x, y: longint): longint;
begin
   if x < y then min := x else min := y
end;
begin
   read(n, m);
   for i := 1 to m do begin read(b[i]); idx[i] := i end;
   { pyramidal sort }
   for i := m div 2 downto 1 do up(i, m);
   for i := m downto 2 do begin
      x := b[1];
      b[1] := b[i];
      b[i] := x;
      x := idx[1];
      idx[1] := idx[i];
      idx[i] := x;
      up(1, i - 1)
   end;
   { binary search }
   lb := 0;
   ub := b[m] div n;
   st0 := 0;
   while lb < ub do begin
      st := (lb + ub) div 2;
      x := st;
      k := 0;
      for i := 1 to m do
         if b[i] >= x then begin
	    k := k + 1;
	    x := b[i] + st
	 end;
      if k >= n then begin
         st0 := st;
	 lb := st + 1
      end else ub := st - 1
   end;
   k := 0;
   x := st0;
   i := 1;
   while k < n do begin
      if b[i] >= x then begin
      	 if k <> 0 then write(' ');
      	 write(idx[i]);
	 k := k + 1;
	 x := b[i] + st0
       end;
       i := i + 1
   end;
end.

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

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

int main() {
    long long n, m;
    cin >> n >> m;
    vector<pair<long long, long long>> a(m);
    for (int i = 0; i < m; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    long long l = 1, r = 1e18;
    long long ans = 0;
    while (l <= r) {
        long long mid = (l + r) >> 1;
        long long pos = mid;
        long long kol = 0;
        for (int i = 0; i < m; ++i) {
            if (a[i].first >= pos) {
                pos = a[i].first + mid;
                kol++;
            }
        }
        if (kol >= n)
            ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    long long pos = ans;
    long long kol = 0;
    for (int i = 0; i < m; ++i) {
        if (a[i].first >= pos) {
            pos = a[i].first + ans;
            kol++;
            cout << a[i].second + 1 << " ";
        }
        if (kol == n) break;
    }
    return 0;
}

:::