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

## [1. Тренировка (усложнённая версия)](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2012_1)
:::spoiler Разбор
:::info
Давайте посчитаем динамику $dp_i$ -- максимальная сумма чисел, которую мы можем собрать, дойдя до клетки под номером $i$.

Два перехода:
1. $dp_i = dp_{i - 2} + a_i$
2. $dp_i = dp_{i - 3} + a_i$

__Не забываем хранить предков!__

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

program z1221s1;
const
  max_n=1000;
var
  A:array[1..max_n] of integer;
  F:array[1..max_n] of longint;
  P,S:array[1..max_n] of byte;
  n,i,k:integer;
begin
  readln(n);
  for i:=1 to n do
    read(a[i]);
  f[1]:=a[1];p[1]:=2;
  f[2]:=a[2];p[2]:=3;
  if n>2 then begin
    f[3]:=f[1]+a[3];p[3]:=2;
    for i:=4 to n do
      if f[i-2]+a[i]<f[i-3]+a[i] then
        begin f[i]:=f[i-3]+a[i];p[i]:=3 end
      else
        begin f[i]:=f[i-2]+a[i]; p[i]:=2 end
  end;
  k:=1;
  if f[n]>f[n-1] then s[1]:=2 else s[1]:=3;
  i:=n+2-s[1];
  while i>2 do begin
    k:=k+1;
    s[k]:=p[i];
    i:=i-s[k]
  end;
  k:=k+1;
  s[k]:=i+1;
  writeln(k);
  for i:=k downto 2 do
    write(s[i],' ');
  writeln(s[1]);
end.

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

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

const ll mod = 1e9 + 7;
const int FFTM = 998244353;
const int N = 1e3 + 15;
const int SX[4] = {0 , 1 , -1 , 0};
const int SY[4] = {1 , 0 , 0 , -1};
const int rx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int ry[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int kx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int ky[8] = {2, -2, 2, -2, 1, -1, 1, -1};

long long dp[N];
int pr[N];

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    dp[0] = a[0];
    pr[0] = -1;
    dp[1] = a[1];
    pr[1] = -1;
    for (int i = 2; i < n; ++i)
        if (i == 2) {
            dp[i] = dp[i - 2] + a[i];
            pr[i] = i - 2;
        } else if (dp[i - 2] + a[i] > dp[i - 3] + a[i])
            dp[i] = dp[i - 2] + a[i], pr[i] = i - 2;
        else dp[i] = dp[i - 3] + a[i], pr[i] = i - 3;
    int posl;
    int pos = -1;
    vector<int> ans;
    if (dp[n - 1] < dp[n - 2])
        posl = 3, pos = n - 2;
    else posl = 2, pos = n - 1;
    while (pos != -1) {
        int x = pos;
        pos = pr[pos];
        if (pos == -1) {
            if (x == 1) ans.push_back(3);
            else ans.push_back(2);
        } else ans.push_back(x - pos);
    }
    cout << ans.size() + 1 << endl;
    reverse(ans.begin(), ans.end());
    for (auto to : ans) cout << to << " ";
    cout << posl << endl;
    return 0;
}

:::

## [2. Паша и системы счисления](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2012_2)
:::spoiler Разбор
:::info
Самое сложное в этой задаче -- это понять ее условие.

Сначала нам нужно перевести данную нам строку в число, по описанному в условии алгоритму. Затем нужно перевести полученное число обратно в строку, по описанному в условии алгоритму. Если полученная строка совпадает со строкой из входных данных, то нам нужно вывести число, иначе строку.

Асимптотика: $O(len)$, где $len$ -- это длина числа.

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

program z1222s1;
var
  wu,wh,wf:array[0..3] of char;
function vCode(k,d:byte):string;
begin
    case d of
      0:vCode:='';
      1:vCode:=wu[k];
      2:vCode:=wu[k]+wu[k];
      3:vCode:=wh[k]+wu[k];
      4:vCode:=wh[k];
      5:vCode:=wu[k]+wh[k];
      6:vCode:=wf[k]+wu[k]
    end
end;
function cValue(c:char):word;
begin
  case c of
    'T':cValue:=1;
    'W':cValue:=4;
    'Y':cValue:=7;
    'Z':cValue:=28;
    'K':cValue:=49;
    'E':cValue:=196;
    'F':cValue:=343;
    'H':cValue:=1372
  end
end;
var
  s,c:string[30];
  v,x,v0,v1:word;
  i,k:integer;
begin
  wu[0]:='T';wh[0]:='W';wf[0]:='Y';
  wu[1]:='Y';wh[1]:='Z';wf[1]:='K';
  wu[2]:='K';wh[2]:='E';wf[2]:='F';
  wu[3]:='F';wh[3]:='H';wf[3]:=#0;
  readln(s);
  v0:=cValue(s[1]);
  v:=v0;
  for i:=2 to length(s) do begin
    v1:=v0;
    v0:=cValue(s[i]);
    if v0>=v1 then v:=v+v0 else v:=v-v0
  end;
  x:=v;
  k:=0;
  c:='';
  while x>0 do begin
    v0:=x mod 7;
    x:=x div 7;
    c:=c+vCode(k,v0);
    k:=k+1
  end;
  if c=s then writeln(v) else writeln(c);
end.

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

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

map<int, string> ss;
vector<string> kek;

void change(int j) {
    j *= 2;
    ss[1] = kek[j];
    ss[2] = kek[j] + kek[j];
    ss[3] = kek[j + 1] + kek[j];
    ss[4] = kek[j + 1];
    ss[5] = kek[j] + kek[j + 1];
    ss[6] = kek[j + 2] + kek[j];
}

int32_t main() {
    string s;
    cin >> s;
    map<char, int> mp;
    mp['T'] = 1;
    mp['W'] = 4;
    mp['Y'] = 7;
    mp['Z'] = 28;
    mp['K'] = 49;
    mp['E'] = 196;
    mp['F'] = 343;
    mp['H'] = 1372;
    kek.push_back("T"); kek.push_back("W"); kek.push_back("Y"); kek.push_back("Z"); kek.push_back("K"); kek.push_back("E"); kek.push_back("F"); kek.push_back("H"); kek.push_back("a");
    int n = s.size();
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        a[i] = mp[s[i]];
    int ans = a[0];
    for(int i = 1; i < n; ++i) {
        int z = 1;
        if(a[i] < a[i - 1]) z = -1;
        ans += z * a[i];
    }
    int x = ans;
    int sz = 0;
    vector<int> b;
    while(x) {
        b.pb(x % 7);
        x /= 7;
        ++sz;
    }
    string res = "";
    for (int i = 0; i < b.size(); ++i) {
        change(i);
        if(b[i] == 0) continue;
        res += ss[b[i]];
    }
    cout << (s == res ? ans : res) << endl;
    return 0;
}

:::

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

Теперь зная порядковый номер каждой книжки, мы легко можем найти номер ряда, шкафа, полки и позиции данной книжки.

Уточнить формулы нахождения ряда, шкафа, полки и позиции Вы можете, посмотрев код.

Асимптотика: $O(min(M * N, 10^7))$.

*P.S:*
*Вывести формулки лучше самому, чем их копипастить.*

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

program z1223s5;

const
  max_n=100000;
  max_m=10000;
  max_k=100000;
  max_v=1000;
  max_books=10000000;
  max_b=100;
  max_s=10;
  max_r=1000;

var
  qtitle:array[1..max_k]of integer;
  qindex,qplace,qans:array[1..max_k] of longint;
  title,damount:array[1..max_n] of integer;
  tamount:array[1..max_m] of longint;
  qtstart,qtend:array[1..max_m] of longint;
  n,k,i,j,p:longint;
  m,r:integer;
  b,s:byte;

procedure PrintPlace(var p:longint);
var
  ri,bi,si:longint;
begin
  p:=p-1;
  si:=p div b;
  p:=p mod b;
  bi:=si div s;
  si:=si mod s;
  ri:=bi div r;
  bi:=bi mod r;
  writeln(ri+1,' ',bi+1,' ',si+1,' ',p+1)
end;

function compare(t1,i1,t2,i2:longint):longint;
begin
  if t1<>t2 then compare:=t1-t2
  else compare:=i1-i2
end;

procedure swap(j,k:longint);
var
  tmp:longint;
begin
  tmp:=qtitle[j];qtitle[j]:=qtitle[k];qtitle[k]:=tmp;
  tmp:=qindex[j];qindex[j]:=qindex[k];qindex[k]:=tmp;
  tmp:=qplace[j];qplace[j]:=qplace[k];qplace[k]:=tmp
end;

procedure SortRequests;
var
  i,j,d:longint;
begin
  for i:=2 to k do begin
    j:=i;
    d:=j div 2;
    while (j>1)and (compare(qtitle[j],qindex[j],qtitle[d],qindex[d])>0) do begin
      swap(j,d);
      j:=d;
      d:=j div 2
    end
  end;
  for i:=k downto 2 do begin
    swap(i,1);
    j:=1;
    d:=2*j;
    while (d+1<i) and ((compare(qtitle[j],qindex[j],qtitle[d],qindex[d])<0) or
          (compare(qtitle[j],qindex[j],qtitle[d+1],qindex[d+1])<0)) do
      if compare(qtitle[d],qindex[d],qtitle[d+1],qindex[d+1])>0 then begin
        swap(j,d);
        j:=d;
        d:=2*j
      end
      else begin
        swap(j,d+1);
        j:=d+1;
        d:=2*j
      end;
    if (d<i) and (compare(qtitle[j],qindex[j],qtitle[d],qindex[d])<0) then
      swap(j,d)
  end
end;

begin
  readln(b,s,r);
  readln(m,n);
  for i:=1 to n do
    readln(title[i],damount[i]);
  readln(k);
  for i:=1 to k do begin
    readln(qtitle[i],qindex[i]);
    qplace[i]:=i
  end;
  SortRequests;
  j:=1;
  for i:=1 to k do
    while j<=qtitle[i] do begin
      qtstart[j]:=i;
      j:=j+1
    end;
  while j<=m do begin
    qtstart[j]:=k+1;
    j:=j+1
  end;
  for i:=1 to m-1 do qtend[i]:=qtstart[i+1];
  qtend[m]:=k+1;
  p:=0;
  for i:=1 to m do tamount[i]:=0;
  for i:=1 to n do begin
    j:=title[i];
    while (qtstart[j]<qtend[j]) and
          (qindex[qtstart[j]]<=tamount[j]+damount[i]) do begin
      qans[qplace[qtstart[j]]]:=p+qindex[qtstart[j]]-tamount[j];
      qtstart[j]:=qtstart[j]+1
    end;
    p:=p+damount[i];
    tamount[j]:=tamount[j]+damount[i]
  end;
  for i:=1 to k do
    PrintPlace(qans[i]);
end.

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

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

int b, s, r;
int n, m;

map<int, vector<int>> mp;

void get_pos(int x) {
    int nom_rad = x / (b * s * r) + 1;
    x -= (nom_rad - 1) * (b * s * r);
    int nom_shkaf = x / (b * s) + 1;
    x -= (nom_shkaf - 1) * (b * s);
    int nom_polka = x / b + 1;
    x -= (nom_polka - 1) * b;
    if (!x) nom_polka--, x = b;
    if (!nom_polka) nom_polka = s, nom_shkaf--;
    if (!nom_shkaf) nom_shkaf = r, nom_rad--;
    cout << nom_rad << " " << nom_shkaf << " " << nom_polka << " " << x << endl;
}

int main() {
    cin >> b >> s >> r >> m >> n;
    int pos = 1;
    for (int i = 0; i < n; ++i) {
        int type, kol;
        cin >> type >> kol;
        for (int i = 0; i < kol; ++i) {
            mp[type].pb(pos);
            pos++;
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int type, nomber;
        cin >> type >> nomber;
        int x = mp[type][nomber - 1];
        get_pos(x);
    }
    return 0;
}
 

:::