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

## [1. Движение по кольцу](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2016_1)
:::spoiler Разбор
:::info
Паша может жить либо на $m$ остановок левее школы, либо на $m$ остановок правее школы. Считаем местоположение дома Паши. Не забудем, что его можно определить однозначно.

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

var
n,m,k,x1,x2:longint;
begin
   read(n,k,m);
   x1:=(k + m) mod n + 1;
   x2:=(n + k - m - 2) mod n + 1;
   if 2*m+2>=n then
      if x1=x2 then writeln(x1)
      else if x1<x2 then writeln(x1, ' ', x2)
      else writeln(x2, ' ', x1)
end.

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

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

int main() {
    long long n, m, k;
    cin >> n >> k >> m;
    m++;
    set<long long> ans;
    long long ost_1 = k - m;
    if (ost_1 >= 1)
        ans.insert(ost_1);
    else ans.insert(ost_1 + n);
    long long ost_2 = k + m;
    if (ost_2 <= n)
        ans.insert(ost_2);
    else ans.insert(ost_2 - n);
    for (auto to : ans)
        cout << to << " ";
    cout << endl;
    return 0;
}

:::

## [2. Крутейший спуск](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2016_2)
:::spoiler Разбор
:::info
В этой задаче нам нужно найти максимальное отношение перепада высот к расстоянию между отметками по горизонтали. Мы делаем ровно то, о чем нас просят. Единственный момент: чтобы избежать неточностей, давайте заменим отношение умножением крест-накрест ($\frac{A}{B} = \frac{C}{D}$ равносильно $A * D = B * C$).
Асимптотика: $O(N)$.
:::
:::spoiler Авторское решение (Pascal)

function abs(x:longint):longint;
begin
   if x<0 then abs:=-x else abs:=x
end;
var
n,xp,hp,xc,hc,i,mp,dx,dh,mdx,mdh:longint;
begin
   read(n);
   read(xp,hp,xc,hc);
   mp:=1;
   mdx:=abs(xp-xc);
   mdh:=abs(hp-hc);
   for i:=2 to n-1 do begin
      xp:=xc;hp:=hc;
      read(xc,hc);
      dx:=abs(xp-xc);
      dh:=abs(hp-hc);
      if int64(dh)*mdx>int64(mdh)*dx then begin
	 mp:=i;
	 mdx:=dx;
	 mdh:=dh
      end
   end;
   writeln(mp)
end.

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

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

int main() {
    int n;
    cin >> n;
    int lasth, lastd;
    cin >> lastd >> lasth;
    int d, h;
    cin >> d >> h;
    int H = abs(lasth - h);
    int D = abs(lastd - d);
    int otH = H, otD = D, nom = 1, j = 1;
    for (int i = 2; i < n; i++) {
        j++;
        lastd = d;
        lasth = h;
        cin >> d >> h;
        H = abs(lasth - h);
        D = abs(lastd - d);
        if (otH * D < H * otD) {
            otH = H;
            otD = D;
            nom = j;
        }
    }
    cout << nom << endl;
    return 0;
}

:::

## [3. Самый длинный слог](https://codeforces.com/group/skz9fIV5Hq/contest/261187/problem/2016_3)
:::spoiler Разбор
:::info
Это очень запарная и неприятная реализация. Разбираем все случаи (они описаны в условии). Выводим ответ.

Асимптотика: $O(N + |allS|)$, где $|allS|$ -- длина всех строк.
:::
:::spoiler Авторское решение (Pascal)

var
i,st,p,m,mp,k:longint;
s:ansistring;
begin
   readln(s);
   st:=1;
   p:=0;
   m:=0; mp:=0;
   for i:=1 to length(s) do
      case s[i] of
	    ' ': begin
	        if m < i-st then begin m:=i-st; mp:=st end;
	        st:=i+1;
	        p:=0
	    end;
	    'a','e','i','o','u','y'	: begin
	        if p<>0 then begin
	            if (s[p] = 'y') or (i<=p+2) then k := p else k:=p+1;
	            if m < k + 1 - st then begin m := k + 1 - st; mp:=st end;
	            st := k + 1
	        end;
	        p:=i
	    end
    end;
   k:=length(s);
   if m < k + 1 - st then begin m := k + 1 - st; mp:=st end;
   writeln(copy(s,mp,m))
end.

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

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

vector<string> w;

int main() {
    string s;

    getline(cin,s);
    string cur = "";
    for (int i = 0; i < s.size(); i++)
        if (s[i] == ' ') {
            w.push_back(cur);
            cur = "";
        } else cur += s[i];
    if (cur != "")
        w.push_back(cur);

    int ma=0;
    string ans;

    for (int i = 0; i < w.size(); i++) {
        vector<int> gl;
        int pr = -1;
        for (int j = 0; j < w[i].size(); j++)
            if (w[i][j]=='a' || w[i][j]=='e' || w[i][j]=='y' || w[i][j]=='i' || w[i][j]=='o' || w[i][j]=='u')
                gl.pb(j);
        int cur = 0;
        string t;

        for (int j = 0; j < w[i].size(); j++)
            if (cur == 0 && j < gl[0])
                t += w[i][j];
            else if(cur == gl.size()-1 && j >= gl[cur])
                t+=w[i][j];
            else if (gl[cur] == j && cur != gl.size()-1) {
                t += w[i][j];
                cur++;
                if (gl[cur] - gl[cur-1] <= 2 || w[i][j] == 'y') {
                    if (t.size() > ma) {
                        ans = t;
                        ma = t.size();
                    }
                    t = "";
                }
            } else if (gl[cur-1] == j-1) {
                t += w[i][j];
                if (t.size()>1) {
                    if (t.size() > ma) {
                        ans = t;
                        ma = t.size();
                    }
                    t = "";
                }
            } else t+=w[i][j];

        if(t != "") {
            if (t.size() > ma) {
                ans = t;
                ma = t.size();
            }
            t = "";
        }
    }

    cout << ans << endl;
}

:::

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

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

var
n,k,i,ig,wani4ka,ib,x,mx:integer;
rg,rs,rb:integer;
g,s,b:array[1..300]of byte;
f:array[0..300,0..60,0..60,0..60] of integer;
{p:array[1..300,0..60,0..60,0..60] of (gold,silver,bronze,none);}
function greater:boolean;
begin
   if g[i]=g[k] then
      if s[i]=s[k] then greater:=b[i]>b[k]
      else greater:=s[i]>s[k]
   else greater:=g[i]>g[k]
end;
function byGold:integer;
var dg:integer;
begin
   dg:=g[k]-g[i]+1;
   if dg<=ig then byGold:=f[i-1,ig-dg,wani4ka,ib]+1
   else byGold:=0
end;
function bySilver:integer;
var dg,ds:integer;
begin
   dg:=g[k]-g[i];
   ds:=s[k]-s[i]+1;
   if ds < 0 then ds := 0;
   if (dg<=ig) and (ds<=wani4ka) then bySilver:=f[i-1,ig-dg,wani4ka-ds,ib]+1
   else bySilver:=0
end;
function byBronze:integer;
var dg,ds,db:integer;
begin
   dg:=g[k]-g[i];
   ds:=s[k]-s[i];
   if ds >= 0 then begin
      db:=b[k]-b[i]+1;
      if db < 0 then db := 0;
      if (dg<=ig) and (ds<=wani4ka) and (db<=ib) then
	 byBronze:=f[i-1,ig-dg,wani4ka-ds,ib-ib]+1
      else byBronze:=0;
   end else byBronze:=0;
end;
begin
   read(n,k,rg,rs,rb);
   for i:=1 to n do read(g[i],s[i],b[i]);
   for ig:=0 to rg do
      for wani4ka:=0 to rs do
	 for ib:=0 to rb do
	    f[0,ig,wani4ka,ib]:=0;
   for i:=1 to n do
      if i=k then
	 for ig:=0 to rg do
	    for wani4ka:=0 to rs do
	       for ib:=0 to rb do begin
		  f[i,ig,wani4ka,ib]:=f[i-1,ig,wani4ka,ib];
//		  p[i,ig,wani4ka,ib]:=none;
	       end
      else if greater then
	 for ig:=0 to rg do
	    for wani4ka:=0 to rs do
	       for ib:=0 to rb do begin
		  f[i,ig,wani4ka,ib]:=f[i-1,ig,wani4ka,ib]+1;
//		  p[i,ig,wani4ka,ib]:=none;
	       end		  
      else
	 for ig:=0 to rg do
	    for wani4ka:=0 to rs do
	       for ib:=0 to rb do begin
		  f[i,ig,wani4ka,ib]:=f[i-1,ig,wani4ka,ib];
//		  p[i,ig,wani4ka,ib]:=none;
		  x:=byGold;
		  if x>f[i,ig,wani4ka,ib] then begin
		     f[i,ig,wani4ka,ib]:=x;
//		     p[i,ig,wani4ka,ib]:=gold
		  end;
		  x:=bySilver;
		  if x>f[i,ig,wani4ka,ib] then begin
		     f[i,ig,wani4ka,ib]:=x;
//		     p[i,ig,wani4ka,ib]:=silver
		  end;		     
		  x:=byBronze;
		  if x>f[i,ig,wani4ka,ib] then begin
		     f[i,ig,wani4ka,ib]:=x;
//		     p[i,ig,wani4ka,ib]:=bronze
		  end
	       end;
   mx:=0;
   for ig:=0 to rg do
      for wani4ka:=0 to rs do
	 for ib:=0 to rb do
	    if f[n,ig,wani4ka,ib]>mx then begin
	       mx:=f[n,ig,wani4ka,ib];
{	       mig:=ig;
	       mis:=wani4ka;
	       mib:=ib}
	    end;
   writeln(mx);
{   i:=n;
   while i>0 do begin
      case p[i,mig,mis,mib] of
	gold   : begin
		    writeln(i);
		    mig:=mig-(g[k]-g[i]+1)
		 end;
	silver : begin
		    writeln(i);
		    mig:=mig-(g[k]-g[i]);
		    mis:=mis-(s[k]-s[i]+1)
		 end;
	bronze : begin
		    writeln(i);
		    mig:=mig-(g[k]-g[i]);
		    mis:=mis-(s[k]-s[i]);
		    mib:=mib-(b[k]-b[i]+1)
		 end;
      end;
      i:=i-1
   end}
end.

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

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

struct node {
    int Gold, Silver, Bronze;
    int id;
    node() {
        Gold = 0;
        Silver = 0;
        Bronze = 0;
        id = -1;
    }
    bool operator < (const node &x) {
        if (x.Gold != Gold) return x.Gold > Gold;
        else if (x.Silver != Silver) return x.Silver > Silver;
        else return x.Bronze > Bronze;
    }
};

vector<node> all;

int kol_Gold = 0;
int kol_Silver = 0;
int kol_Bronze = 0;

int main() {
    int n, k;
    cin >> n >> k >> kol_Gold >> kol_Silver >> kol_Bronze;
    all.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> all[i].Gold >> all[i].Silver >> all[i].Bronze;
        all[i].id = i + 1;
    }
    sort(all.rbegin(), all.rend());
    int ans = 0;
    bool ok = 1;
    node Team;
    for (int i = 0; i < n; ++i) {
        if (all[i].id != k && ok) {
            ans++;
            continue;
        }
        if (all[i].id == k) {
            ok = 0;
            Team = all[i];
            continue;
        }
        int need_Gold = -all[i].Gold + Team.Gold;
        int need_Silver = -all[i].Silver + Team.Silver;
        int need_Bronze = -all[i].Bronze + Team.Bronze;
        if (need_Gold <= kol_Gold && need_Silver <= kol_Silver && need_Bronze + 1 <= kol_Bronze) {
            kol_Gold -= (need_Gold < 0 ? 0 : need_Gold);
            kol_Silver -= (need_Silver < 0 ? 0 : need_Silver);
            kol_Bronze -= (need_Bronze >= 0 ? need_Bronze + 1 : 0);
            ans++;
            continue;
        }
        if (need_Gold <= kol_Gold && need_Silver + 1 < kol_Silver) {
            kol_Gold -= (need_Gold < 0 ? 0 : need_Gold);
            kol_Silver -= (need_Silver >= 0 ? need_Silver + 1 : 0);
            ans++;
            continue;
        }
        if (need_Gold + 1 <= kol_Gold) {
            kol_Gold -= (need_Gold >= 0 ? need_Gold + 1 : 0);
            ans++;
            continue;
        }
    }
    cout << ans << endl;
    return 0;
}

:::