Псевдо строчная таблица

12/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

Входные данные

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

Выходные данные

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$	$12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$	$10$
$2 \ 3 \ 5$
$4 \ 4$	$96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$	$6$
$2 \\ 2 \\ 2$
$5 \ 3$	$430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$	$216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$	$945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$	$5$
$5$
$3 \ 7$	$210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$	$202$
$100 \ 1 \\ 100 \ 1$

Код программы

#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> m >> n;
    long long s[m][n], h=0;
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> s[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        h+=s[0][i];
    }
    cout << m*h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

long long s[m][n], h=0;

for(int i=0; i<m; i++)

{

for(int j=0; j<n; j++)

{

cin >> s[i][j];

}

for(int i=0; i<n; i++)

{

h+=s[0][i];

}

cout << m*h;

return 0;

}

Решение задачи

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Related Images:

Строчная таблица

11/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

Входные данные

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

Выходные данные

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

Тесты

Входные данные	Выходные данные
$3$	$0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$	$0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$	$0.3333 \ 0.6667$
$1 \ 2$
$3$	$0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$	$0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$	$1.0000$
$2$
$4$	$0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$	$0.9901 \ 0.0099$
$100 \ 1$
$6$	$0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$	$0.5000 \ 0.5000$
$2 \ 2$
$10$	$0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$	$0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

Код программы

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long double s[n], h=0;
    for(int i=0; i<n; i++)
    {
        cin >> s[i];
        h+=s[i];
    }
    for(int i=0; i<n; i++)
    {
        cout.precision(4);
        cout << fixed << s[i]/h << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long double s[n], h=0;

for(int i=0; i<n; i++)

{

cin >> s[i];

h+=s[i];

}

for(int i=0; i<n; i++)

{

cout.precision(4);

cout << fixed << s[i]/h << " ";

}

return 0;

}

Решение задачи

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения

Related Images:

e-olymp 2892. Сумма значений

24/06/2018 by Костя Григорян

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

Входные данные

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

Выходные данные

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные	Выходные данные
$3$	$7.833333333333333$
$1 \ 2 \ 3$
$2$	$0$
$1 \ -1$
$5$	$4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$	$10.1$
$10$

Код программы

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector <long double> x;
    int n;
    long double ans=0;
    cin >> n;
    x.resize(n);
    for(int i=0; i<n; i++) 
    {
        cin >> x[i];
    }
    for(int i=0; i<n; i++)
    {
        ans+=x[i]+1.0/x[i];
    }
    cout.precision(15);
    cout << fixed << ans;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <long double> x;

int n;

long double ans=0;

cin >> n;

x.resize(n);

for(int i=0; i<n; i++)

{

cin >> x[i];

}

for(int i=0; i<n; i++)

{

ans+=x[i]+1.0/x[i];

}

cout.precision(15);

cout << fixed << ans;

return 0;

}

Решение задачи

Мы просто суммируем значения функции в каждой точке. Тут использовали тип long double для точек и значений функции для меньшей погрешности.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 670. Поиск палиндромов

20/06/2018 by Костя Григорян

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

Входные данные

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

Выходные данные

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные	Выходные данные
$3$	$3$
$babcbab$
$1$	$5$
$abcde$
$4$	$0$
$aarreeds$
$5$	$3$
$aaaaaaa$
$3$	$0$
$CaccaC$

Код программы

String

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    string s;
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<s.size()-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

string s;

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<s.size()-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int max_length=30001; 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    char s[max_length];
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<strlen(s)-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int max_length=30001;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

char s[max_length];

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<strlen(s)-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

Решение задачи

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

Условие задачи на e-olymp
Код решения. String
Код решения. C-String

Related Images:

e-olymp 2668. Спираль

05/06/2018 by Костя Григорян

Задача

Заполнить массив размера $n × n$ единичками по спирали (см. пример).

Входные данные

Одно нечетное натуральное число $n$, не превышающее $50$.

Выходные данные

Вывести построенную спираль. Центральная клетка должна содержать $0$.

Тесты

Входные данные	Выходные данные
[latex]7[/latex]	[latex]1111111 \\ 0000001 \\ 1111101 \\ 1000101 \\ 1011101 \\ 1000001 \\ 1111111[/latex]
[latex]1[/latex]	[latex]0[/latex]
[latex]3[/latex]	[latex]111 \\ 001 \\ 111[/latex]
[latex]5[/latex]	[latex]11111 \\ 00001 \\ 11001 \\ 10001 \\ 11111[/latex]

Код программы

#include <iostream>
using namespace std;

bool s[50][50];

int main() {
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        s[0][i]=1;
        s[n-1][i]=1;
        s[i][n-1]=1;
    }
    int h=n-2, d=n-2;
    int pointx=n-1, pointy=0; 
    while(1)
    {
        for(int i=0; i<h; i++)
        {
            s[pointx-i][pointy]=1;
        }
        pointx-=h-1;
        h-=2;
        if(h<=0)
            break;
        for(int i=0; i<d; i++)
        {
            s[pointx][pointy+i]=1;
        }
        pointy+=d-1;
        d-=2;
        if(d<=0)
            break;
            for(int i=0; i<h; i++)
        {
            s[pointx+i][pointy]=1;
        }
        pointx+=h-1;
        h-=2;
        if(h<=0)
            break;
        for(int i=0; i<d; i++)
        {
            s[pointx][pointy-i]=1;
        }
        pointy-=d-1;
        d-=2;
        if(d<=0)
            break;
    }
    s[n/2][n/2]=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout << s[i][j];
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool s[50][50];

int main() {

int n;

cin >> n;

for(int i=0; i<n; i++)

{

s[0][i]=1;

s[n-1][i]=1;

s[i][n-1]=1;

}

int h=n-2, d=n-2;

int pointx=n-1, pointy=0;

while(1)

{

for(int i=0; i<h; i++)

{

s[pointx-i][pointy]=1;

}

pointx-=h-1;

h-=2;

if(h<=0)

break;

for(int i=0; i<d; i++)

{

s[pointx][pointy+i]=1;

}

pointy+=d-1;

d-=2;

if(d<=0)

break;

for(int i=0; i<h; i++)

{

s[pointx+i][pointy]=1;

}

pointx+=h-1;

h-=2;

if(h<=0)

break;

for(int i=0; i<d; i++)

{

s[pointx][pointy-i]=1;

}

pointy-=d-1;

d-=2;

if(d<=0)

break;

}

s[n/2][n/2]=0;

for(int i=0; i<n; i++)

{

for(int j=0; j<n; j++)

{

cout << s[i][j];

}

cout << endl;

}

return 0;

}

Решение задачи

Для начала мы верхнюю, нижнюю и правую грани зразу заполним единицами. Далее идем поочередно в четырех направления (вверх, вправо, вниз, влево). Мы имеем два параметра: ширину и высоту заполняемого единицами отрезка (ширине соответствуют движения вправо и влево, высоте — вверх и вниз). На каждом шаге уменьшаем соответствующий заполняемый отрезок (ширину или высоту) на $2$ и проверяем, чтобы он был больше $0$, иначе заканчиваем. На протяжении всего решения храним еще два параметра: координаты точки, откуда начнем следующий шаг.
P.s. На сайте www.e-olymp.com это решение не проходит полностью из-за неправильности $5$-го теста. У них в $5$-ом тесте центральный элемент $1$, что противоречит условию.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 84. Transfer

26/05/2018 by Костя Григорян

Task

Vasya has one package of mobile phone operator Ratsviyk and $S_0$ tugriks on its account. (Tugrik is the currency in Vasya’s country. $0.01$ of tugrik is a cent). Also he has $n$ packages of Eciujd which is the satellite of Ratsviyk. There are $S_i$ tugriks on the account of the $i$-th package of Eciujd. There was a new tariff plan on Ratsviyk and Vasya want to go into it. For this purpose it is necessary to have at least $S$ tugriks on the account. Vasya hasn’t any money, that is why he don’t want to buy new bill replenishment, to fill up the Ratsviyk account to the necessary sum. But the escape exists.
On Ratsviyk there is such possibility as to transfer money between each others. The transfer is the sending of some money from one account to another. It is possible to send only an integer amounts of tugriks, not smaller than $5$. The cost of the transfer is $10$ cents which is draw from the account from which money was sended. Transfer can be made only if after it on the account remains at least $5$ tugriks. Since Eciujd is the satellite of Ratsviyk, then subscribers of Eciujd also can participate in this transfers.
Giving $S_0, S, n, S_i (1 \leq i \leq n)$ find whether it is possible to go into new tariff plan without buying new bill replenishment and if so find the minimum number of transfers needed for this.

Input

In the first line of input there is an integer $n (0 \leq n \leq 1000), S_0$ and $S$. In the second line are written down through a blank numbers $S_1, S_2,$…$,S_n$. All numbers $S, S_i (0 \leq i \leq n)$ — real numbers from the interval $[0.01, 10000.00]$ with exactly with two digits after a decimal point.

Output

Output the minimum number of transfers needed to go into new tariff plan or $-1$ if it is impossible without buying a new bill replenishment.

Tests

Input	Output
[latex]2\, 10.00\, 16.00[/latex]	[latex]2[/latex]
[latex]10.10\, 6.10[/latex]
[latex]3\, 100.00\, 50.00[/latex]	[latex]0[/latex]
[latex]2.00\, 19.05\ 30.20[/latex]
[latex]3\ 10.00\ 14.00[/latex]	[latex]-1[/latex]
[latex]2.00\ 10.05\ 10.00[/latex]
[latex]2\ 142.10\ 143.00[/latex]	[latex]2[/latex]
[latex]6.05\ 7.00[/latex]

Code

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    double s0, s;
    double A[n], B[n];
    cin >> s0 >> s;
    if(s0>=s)
        cout << 0;
    else
    {
        for(int i=0; i<n; i++)
        {
            cin  >> A[i];
            B[i]=A[i];
        }
        sort(B, B+n);
        int ans=0;
        for(int i=n-1; i>=1; i--)
        {
            if(B[i]>=10.1)
            {
                if((int)(B[i]-5.1)+s0>=s){
                    ans++;
                    cout << ans;
                    return 0;
                }
                else
                {
                    ans++;
                    B[i-1]+=(int)(B[i]-5.1);
                }
            }
            else
            {
                break;
            }
        }
        if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))
            cout << ans+1;
        else
        {
            sort(A, A+n);
            if(s0>=10.1)
            {
                A[n-1]+=(int)(s0-5.1);
                s0-=(int)(s0-5.1);
                                s0-=0.1;
                ans=1;
                for(int i=n-1; i>=1; i--)
                {
                    if(A[i]>=10.1)
                    {
                        if((int)(A[i]-5.1)+s0>=s){
                            ans++;
                            cout << ans;
                            return 0;
                        }
                        else
                        {   
                            ans++;
                            A[i-1]+=(int)(A[i]-5.1);
                        }
                    }
                    else
                    {
                        break;
                    }
                }
                if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))
                    cout << ans+1;
                else
                    cout << -1;
            }
            else
                cout << -1;
        }   
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int n;

cin >> n;

double s0, s;

double A[n], B[n];

cin >> s0 >> s;

if(s0>=s)

cout << 0;

else

{

for(int i=0; i<n; i++)

{

cin >> A[i];

B[i]=A[i];

}

sort(B, B+n);

int ans=0;

for(int i=n-1; i>=1; i--)

{

if(B[i]>=10.1)

{

if((int)(B[i]-5.1)+s0>=s){

ans++;

cout << ans;

return 0;

}

else

{

ans++;

B[i-1]+=(int)(B[i]-5.1);

}

else

{

break;

}

if((B[0]>=10.1)&&((int)(B[0]-5.1)+s0>=s))

cout << ans+1;

else

{

sort(A, A+n);

if(s0>=10.1)

{

A[n-1]+=(int)(s0-5.1);

s0-=(int)(s0-5.1);

s0-=0.1;

ans=1;

for(int i=n-1; i>=1; i--)

{

if(A[i]>=10.1)

{

if((int)(A[i]-5.1)+s0>=s){

ans++;

cout << ans;

return 0;

}

else

{

ans++;

A[i-1]+=(int)(A[i]-5.1);

}

else

{

break;

}

if((A[0]>=10.1)&&((int)(A[0]-5.1)+s0>=s))

cout << ans+1;

else

cout << -1;

}

else

cout << -1;

}

return 0;

}

Solution

To begin with, if we have enough money in our account, then we do not need to do anything. Otherwise, we have three options: when we can collect the required amount without manipulating the main account, when we can collect the necessary amount by manipulating the main account and when we can not collect the required amount at all.
For the first option, we will transfer the largest possible amount to smaller ones from large side accounts and check whether we can switch to a new tariff by transferring the current account amount to the main account. In cases of a positive answer, the problem is solved.
If in the end you did not manage to get the right amount, go to the second option. We simply transfer the maximum possible amount from the main account to the largest collateral account. Then we do everything the same as in the first version. In cases of a positive answer, the problem is solved.
Otherwise, you can not get the right amount.

References

The task at E-Olymp
My solution at ideone

Related Images:

e-olymp 49. Кот учёный

09/05/2018 by Костя Григорян

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

Входные данные

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

Выходные данные

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

Код программы

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, n, k, count=0;
    cin >> l >> n >> k;
    for(int i=0; i<n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
            count++;
        else
        {
            int a, b, c;
            int deltaX=x2-x1;
            int deltaY=y2-y1;
            a=deltaY;
            b=-deltaX;
            c=y1*deltaX-x1*deltaY;
            if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))
                count++;
        }
    }
    cout << count/k+1 << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int l, n, k, count=0;

cin >> l >> n >> k;

for(int i=0; i<n; i++)

{

int x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else

{

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))

count++;

}

cout << count/k+1 << endl;

return 0;

}

Решение задачи

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 161. Роботы

01/03/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

Входные данные

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

Выходные данные

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

Код программы

#include <iostream>
#include <set>
#include <climits>
using namespace std;

int inf = INT_MAX;

int main() {
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    int na;
    cin >> na;
    multiset<pair<int, int> > s;
    int a[na];
    int resa[n];
    for(int i=0; i<na; i++)
    {
        cin >> a[i];
        s.insert({a[i], a[i]});
    }
    for(int i=0; i<n; i++)
    {
        auto it=s.begin();
        int val=it->first;
        int t=it->second;
        s.erase(it);
        s.insert({val+t, t});
        resa[i]=val;
    }
    int nb;
    cin >> nb;
    int b[nb];
    for(int i=0; i<nb; i++)
    {
        cin >> b[i];
    }
    multiset<pair<int, int> > q;
    long long l=resa[n-1], r=10000100;
    while(l<r)
    {
        int w=0;
        int m=(l+r)/2;
        for(int i=0; i<nb; i++)
        {
            q.insert({b[i], b[i]});
        }
        q.insert({inf, inf});
        for(int i=n-1; i>=0; i--)
        {
            int y=m-resa[i];
            auto x=q.begin();
            if(y<(x->first))
            {
                w++;
                break;
            }
            else{
                auto it=q.lower_bound({y, -1});
                int z=it->first;
                if(z>y)
                    it--;
                int val=it->first;
                int t=it->second;
                q.erase(it);
                q.insert({val+t, t});
            }
        }
        if(w==0)
            r=m;
        else
            l=m+1;
        q.clear();  
    }
    cout << l;
    return 0;
}

#include <iostream>

#include <set>

#include <climits>

using namespace std;

int inf = INT_MAX;

int main() {

cin.sync_with_stdio(false);

int n;

cin >> n;

int na;

cin >> na;

multiset<pair<int, int> > s;

int a[na];

int resa[n];

for(int i=0; i<na; i++)

{

cin >> a[i];

s.insert({a[i], a[i]});

}

for(int i=0; i<n; i++)

{

auto it=s.begin();

int val=it->first;

int t=it->second;

s.erase(it);

s.insert({val+t, t});

resa[i]=val;

}

int nb;

cin >> nb;

int b[nb];

for(int i=0; i<nb; i++)

{

cin >> b[i];

}

multiset<pair<int, int> > q;

long long l=resa[n-1], r=10000100;

while(l<r)

{

int w=0;

int m=(l+r)/2;

for(int i=0; i<nb; i++)

{

q.insert({b[i], b[i]});

}

q.insert({inf, inf});

for(int i=n-1; i>=0; i--)

{

int y=m-resa[i];

auto x=q.begin();

if(y<(x->first))

{

w++;

break;

}

else{

auto it=q.lower_bound({y, -1});

int z=it->first;

if(z>y)

it--;

int val=it->first;

int t=it->second;

q.erase(it);

q.insert({val+t, t});

}

if(w==0)

r=m;

else

l=m+1;

q.clear();

}

cout << l;

return 0;

}

Решение задачи

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $ T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Related Images:

e-olymp 130. Прямоугольник

04/12/2017 by Костя Григорян

Задача №130 (дубль — №7379)

Заданы координаты трёх вершин прямоугольника. Найдите координаты четвертой вершины.

Входные данные

В единственной строке записано шесть чисел — координаты трёх точек.

Выходные данные

Два числа, координаты искомой вершины прямоугольника. Все входные и выходные данные — целые числа, не превышающие по модулю [latex]100[/latex].

Тесты

Входные данные	Выходные данные
[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]1[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]2[/latex] [latex]0[/latex]
[latex]1\, 4\, 4\, 0\, 0\, 2[/latex]	[latex]5\, 2[/latex]
[latex]-100[/latex] [latex]-100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]100[/latex] [latex]-100[/latex]	[latex]-100[/latex] [latex]100[/latex]
[latex]2[/latex] [latex]-1[/latex] [latex]3[/latex] [latex]1[/latex] [latex]-2[/latex] [latex]1[/latex]	[latex]-1[/latex] [latex]3[/latex]
[latex]8\, 0\, 1\, 6\, 0\, 4[/latex]	[latex]9\, 2[/latex]

Код программы

#include <iostream>
using namespace std;

int main() {
    int x1, x2, x3, y1, y2, y3;
    cin  >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)
    {
        cout << x2+x3-x1 << " " << y2+y3-y1;
    }
    else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)
    {
        cout << x1+x3-x2 << " " << y1+y3-y2;
    }
    else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)
    {
        cout << x1+x2-x3 << " " << y1+y2-y3;
    }   
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x1, x2, x3, y1, y2, y3;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

if ((x2-x1)*(x3-x1)+(y2-y1)*(y3-y1)==0)

{

cout << x2+x3-x1 << " " << y2+y3-y1;

}

else if ((x2-x1)*(x3-x2)+(y2-y1)*(y3-y2)==0)

{

cout << x1+x3-x2 << " " << y1+y3-y2;

}

else if ((x3-x1)*(x3-x2)+(y3-y1)*(y3-y2)==0)

{

cout << x1+x2-x3 << " " << y1+y2-y3;

}

return 0;

}

Решение задачи

Прямоугольник

Координаты четвертой вершины будут равны сумме координат прилежащих вершин минус координаты противоположной вершины, т. е: [latex]x_4=x_1+x_3-x_2[/latex] и [latex]y_4=y_1+y_3-y_2[/latex]. Но мы не знаем какая из входных вершин противоположна четвертой, а какие — прилежащие. Так как наша фигура это прямоугольник, то противоположная вершина будет при угле [latex]90^{\circ}[/latex]. Произведение перпендикулярных векторов дает [latex]0[/latex]. Перебрав три варианта произведения векторов, заданных входными вершинами, находим вершину при угле [latex]90^{\circ}[/latex]. Остальные две, соответственно, будут прилежащими. Находим координаты четвертой вершины по формуле, заданной выше.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 2364. Часы

06/11/2017 by Костя Григорян

Задача

Ослик Иа-Иа и часы

На очередной день рождения ослику Иа-Иа подарили наручные стрелочные часы. Теперь у него появилось новое развлечение — смотреть на бег стрелок. На то, как минутная догоняет часовую, обходит и тут же продолжает бежать за ней. Вот и в этот раз Кенга застала ослика за этим занятием. Она присоединилась к наблюдением и через некоторое время ей стало интересно, сколько уже моментов, когда минутная стрелка обгоняет часовую, видел Иа-Иа. Для этого она спросила у ослика во сколько он начал смотреть на часы, записала это и текущее время и побежала к Сове с этим вопросом. Но Сова оказалось очень занята и поэтому попросила вас помочь. Как известно, за один день часовая стрелка делает два оборота, а минутная целых [latex]24[/latex]. Continue reading →