e-olymp 657. Игра с монетами

22/06/2019 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Однокопеечные монетки разложены в стопки (в стопках может быть различное количество монет), а стопки поставлены на столе в ряд слева направо. Двое противников по очереди делают ходы. Ход состоит в том, что один из игроков берет слева несколько стопок подряд, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более $ K$ стопок. Игра заканчивается, когда стопок не остается. Требуется найти максимальное число монет, которое может получить первый участник после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

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

В первой строке находится сначала число стопок $ N,$ за ним идут $ N$ чисел, задающих количество монет в стопках слева направо, а затем число $ K.$ Все числа в строке разделены пробелами.
$ 1 \leqslant N \leqslant 180, 1 \leqslant K \leqslant 80,$ количество монет в стопке — не менее $ 1$ и не более $ 20 000$.

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

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

Тесты

№	Inputs	Outputs
1	3 4 9 1 3	14
2	4 1 2 2 7 3	5
3	5 3 4 8 1 7 2	18
4	12 67 8 6 12 6 90 54 89 145 32 45 65 4	357
5	14 32 53 5 52 9 8 17 5 87 44 51 12 15 56 10	312
6	14 76 112 3 1 98 4 172 33 65 90 2 71 18 32 14	777

Код

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){
    if(sum[l][k][p]){
        return sum[l][k][p];
    }
    int ans = 0;
    if(arr.size() - l <= k){
        for(int i = l; i < arr.size(); i++){
            ans += arr[i];
        }
        if(p == 2){
            sum[l][k][p] = 0;
            return sum[l][k][p];
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    if(p == 1){
        int temp = 0;
        for(int i = 1; i <= k; i++){
            temp += arr[(l-1) + i];
            ans = max(ans, temp + solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
    else{
        int ans = INT_MAX;
        for(int i = 1; i <= k; i++){
            ans = min(ans, solution(arr, l+i, i, 3-p));
        }
        sum[l][k][p] = ans;
        return sum[l][k][p];
    }
}

int main() {
    int n, k, a;
    vector<int> coins;
    cin >> n;
    for(int i = 0; i > a;
        coins.push_back(a);
    }
    cin >> k;
    cout << solution(coins, 0, k, 1);
    return 0;
}

#include <iostream>

#include <vector>

#include <limits.h>

using namespace std;

int sum[190][90][3];

int solution(vector<int>&arr, int l, int k, int p){

if(sum[l][k][p]){

return sum[l][k][p];

}

int ans = 0;

if(arr.size() - l <= k){

for(int i = l; i < arr.size(); i++){

ans += arr[i];

}

if(p == 2){

sum[l][k][p] = 0;

return sum[l][k][p];

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

if(p == 1){

int temp = 0;

for(int i = 1; i <= k; i++){

temp += arr[(l-1) + i];

ans = max(ans, temp + solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

else{

int ans = INT_MAX;

for(int i = 1; i <= k; i++){

ans = min(ans, solution(arr, l+i, i, 3-p));

}

sum[l][k][p] = ans;

return sum[l][k][p];

}

int main() {

int n, k, a;

vector<int> coins;

cin >> n;

for(int i = 0; i > a;

coins.push_back(a);

}

cin >> k;

cout << solution(coins, 0, k, 1);

return 0;

}

Решение

Анализируя задачу, становится понятно, что ее можно решить методами динамического программирования, а именно трехмерная динамика по параметрам: количество уже взятых стопок — l, количество стопок, которые можно взять kи какой игрок сейчас ходит p. Каждый игрок старается ходить оптимально, тогда для первого игрока задача взять максимальное количество монет, а для второго игрока задача оставить наименьшее количество монет оппоненту. Решение исполнено с помощью рекурсии, где терминальный случай-когда в массиве осталось количество стопок, меньшее или равное тому, сколько игрок может взять. Также стоит проверять высчитывалась ли раньше данная позиция, иначе задача не зайдет по времени.

Ссылки

Related Images:

e-olymp 8361. Робот

25/12/2018 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Движение робота управляется программой. Программа состоит из следующих команд:

[latex]S[/latex] — сделать шаг вперед
[latex]L[/latex] — повернуться на [latex]90°[/latex] влево
[latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

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

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

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

Выведите одно число, количество шагов, которое будет сделано (то есть выполнено команд [latex]S[/latex]) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите число [latex]-1[/latex].

Тесты

№	Inputs	Outputs
1	SSLSLSLSSRSRS	5
2	LSSSS	-1
3	LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS	15
4	LLLLLLLL	-1
5	SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL	7

Код

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

struct point{
    int x, y;
    point(){
        x = 0;
        y = 0;
    }
    point(int x1,int y1){
        x=x1;
        y=y1;
    }
    bool isequal(point&a, point&b);
}my_point;
 
bool point::isequal(point&a, point&b){
    return a.x == b.x and a.y == b.y;
} 
 
int main() {
    int counter = 0, x = 0, y = 0, res = 0;
    point a;
    char c;
    bool stop = false;
    vector coor(1);
    while(cin >> c and stop == false){
        if(c == 'L'){
            counter = (counter + 1)%4;
        }
        else if(c == 'R'){
            counter = ((counter - 1) + 4)%4;
        }
        else{
            if(counter == 0){
                y++;
            }
            else if(counter == 1){
                x--;
            }
            else if(counter == 2){
                y--;
            }
            else{
                x++;
            }
            res++;
            point a(x,y);
            for(int j = 1; j < coor.size();j++){
                if(my_point.isequal(coor[j],a)){
                    stop = true;
                }
            }
            coor.push_back(a);
        }
    }
    cout << ((stop == true) ? res : -1);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct point{

int x, y;

point(){

x = 0;

y = 0;

}

point(int x1,int y1){

x=x1;

y=y1;

}

bool isequal(point&a, point&b);

}my_point;

bool point::isequal(point&a, point&b){

return a.x == b.x and a.y == b.y;

}

int main() {

int counter = 0, x = 0, y = 0, res = 0;

point a;

char c;

bool stop = false;

vector coor(1);

while(cin >> c and stop == false){

if(c == 'L'){

counter = (counter + 1)%4;

}

else if(c == 'R'){

counter = ((counter - 1) + 4)%4;

}

else{

if(counter == 0){

y++;

}

else if(counter == 1){

x--;

}

else if(counter == 2){

y--;

}

else{

x++;

}

res++;

point a(x,y);

for(int j = 1; j < coor.size();j++){

if(my_point.isequal(coor[j],a)){

stop = true;

}

coor.push_back(a);

}

cout << ((stop == true) ? res : -1);

return 0;

}

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

Related Images:

e-olymp 8524. Сумма положительных в матрице

24/12/2018 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Задана матрица размера [latex]n\times n[/latex]. Найдите сумму ее положительных элементов.

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

Первая строка содержит число [latex]n[/latex] [latex]\left(1 \leq n \leq 100 \right)[/latex]. Следующие строки содержат матрицу [latex]n\times n[/latex]. Элементы матрицы по модулю не больше [latex]100[/latex].

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

Выведите сумму положительных элементов матрицы.

Тесты

№	Inputs	Outputs
1	3 4 -2 5 1 -4 -12 0 1 -3	11
2	4 -4 -2 -5 -7 -1-14 -4 -12 -12 -1 -3 -53	0
3	3 0 0 0 0 1 0 0 0 0	1
4	0	0
5	5 89 76 54 32 33 46 57 89 40 32 12 45 63 78 65 13 76 54 89 67 13 67 89 90 43	1412

Код

#include <iostream>
using namespace std;

int main() {
    int n, a, sum = 0;
    cin >> n;
    for(int i = 0; i < n*n; i++)
        cin >> a;
        if(a > 0){
            sum += a;
        }
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, sum = 0;

cin >> n;

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

cin >> a;

if(a > 0){

sum += a;

}

cout << sum;

return 0;

}

Решение

В условии сказано, что задана матрица размера [latex]n\times n[/latex], тогда вводов тоже будет, соответственно, [latex]n\cdot n[/latex]. В цикле ввода используется условный оператор для проверки на то, положительно число или нет.

Ссылки

Related Images:

e-olymp 176. Выборы вождя

22/12/2018 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.
Старейшины орков всегда наблюдают за выборами и любят предугадывать кто победит на них. Однако далеко не всегда можно предсказать не то, что общую победу на выборах, но даже победителя в одном конкретном бою. Конечно же все зависит от силы сражающихся – кто сильнее, тот и победит, однако в случае равенства сил может победить любой из них – тут уж как звезды станут.
Старейшины обратились к вам с просьбой написать программу для определения количества претендентов, которые могут стать вождями.

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

В первой строке входного файла записано количество [latex]N[/latex] претендентов на звание вождя в этом году [latex]\left(1 \leq N \leq 1000000 \right)[/latex], а во второй – [latex]N[/latex] целых чисел в пределах от [latex]1[/latex] до [latex]10000[/latex], каждое из которых определяет силу соответствующего кандидата.

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

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

Тесты

№	Inputs	Outputs
1	5 1 2 3 4 5	1
2	6 2 2 2 2 2 2	6
3	6 3 2 1 3 1 1	2
4	0	0
5	1 5	1
6	10 712 1056 783 856 783 822 1056 322 543 222	2
7	20 10 30 70 80 90 20 90 40 60 40 80 90 10 30 60 50 30 10 20 30	3

Код

#include <iostream>
using namespace std;

int main() {
    int n, a, max = 0, num = 1;
    cin >> n;
    for(int i = 0; i < n; i++){ 
        cin >> a;
        if(a > max){
            max = a;
            num = 1;
        }
        else if(a == max){
            num++;
        }
    }
    cout << num;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, max = 0, num = 1;

cin >> n;

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

cin >> a;

if(a > max){

max = a;

num = 1;

}

else if(a == max){

num++;

}

cout << num;

return 0;

}

Решение

Условие задачи на первый взгляд довольно устрашающее из-за своего объема, но в нем стоит выделить главный момент — вождем становится самый сильный из орков, так как он победит все поединки, а если сила «орков-победителей» равна, то победить может любой из них. Таким образом, находим самого сильного(сильных) из орков. Для этого при каждом вводе силы орка сравниваем ее с максимальным значением, которое изначально было равно [latex]0[/latex] и если она больше, то присваиваем максимальному значению значение силы. Так же нужна проверка на равенство элементов максимуму, ведь если максимальных элементов будет больше чем один, то кандидатов будет тоже больше одного.

Ссылки

Related Images:

e-olymp 8523. Окружность

22/12/2018 by Богдан Подгорный

Задача взята с сайта e-olymp

Условие

Задан радиус окружности [latex]r[/latex]. Найдите длину окружности и ее площадь.

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

Радиус окружности [latex]r (r >0)[/latex], являющийся действительным числом.

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

Вывести в одной строке длину окружности и ее площадь с [latex]4[/latex] десятичными знаками.

Тесты

№	Inputs	Outputs
1	1.234	7.7535 4.7839
2	3.5	7.7535 4.7839
3	0	0.0000 0.0000
4	10	62.8319 314.1539
5	313	1966.6370 307778.6907

Код

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    double r;
    cin >> r;
    cout << fixed << setprecision(4) << 2*M_PI*r << " " << M_PI*r*r;
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

double r;

cin >> r;

cout << fixed << setprecision(4) << 2*M_PI*r << " " << M_PI*r*r;

return 0;

}

Решение

По известным формулам длины окружности [latex]l = 2\pi r[/latex] и площади окружности [latex]S = \pi r^{2}[/latex] находим их. С помощью setprecison() выводим числа с нужной нам точностью.