e-olymp 5741. Стек шаров

16/12/2017 by Антон Куперман

Задание

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

Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю.

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

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

Каждый тест задается в нескольких строках. Первая строка содержит количество рядов [latex]N (1 ≤ N ≤ 1000)[/latex] в стеке. [latex]i[/latex]-ая из следующих [latex]N [/latex] строксодержит [latex]i[/latex] целых чисел [latex]B_{ij} (-10^{5}≤ B_{ij}≤ 10^{5}[/latex] для [latex]1 ≤ j ≤ i ≤ N)[/latex]; значение [latex]B_{ij}[/latex] равно числу, записанному на [latex]j[/latex]-ом шаре в [latex]i[/latex]-ом ряду стека (первый ряд — самый верхний, в каждом ряду первым шаром является самый левый).

За последним тестом следует строка, содержащая один ноль.

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

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

Тесты

Ввод	Вывод
4 3 -5 3 -8 2 -8 3 9 -2 7 2 -2 1 -10 3 1 -5 3 6 -4 1 0	7 0 6
3 7 2 1 3 4 6 2 5 9 2 1 2 0	23 16 2

Код

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		int[][] s = new int[1001][1001];
		while (in.hasNextInt()) 
		{
			int n = in.nextInt();
			int ans = 0;
			if(n==0)
			{
				break;
			} else {
				for (int i = 1; i <= n; i++) 
				{
					for (int j = 1; j <= i; j++) 
					{
						s[i][j] = in.nextInt();
						s[i][j] += s[i - 1][j];
					}
				}
				for (int j = 1; j <= n; j++)
				{
					for (int i = j; i <= n; i++) 
					{
						s[i][j] += s[i - 1][j - 1];
					}
					for (int i = n - 1; i >= j; i--) {
						s[i][j] = Math.max(s[i][j], s[i + 1][j]);
					}
				}
				for (int i = 1; i <= n; i++) {
					ans = Math.max(ans, s[i][i]);
				}
				System.out.println(ans);
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int[][] s = new int[1001][1001];

while (in.hasNextInt())

{

int n = in.nextInt();

int ans = 0;

if(n==0)

{

break;

} else {

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

{

for (int j = 1; j <= i; j++)

{

s[i][j] = in.nextInt();

s[i][j] += s[i - 1][j];

}

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

{

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

{

s[i][j] += s[i - 1][j - 1];

}

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

s[i][j] = Math.max(s[i][j], s[i + 1][j]);

}

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

ans = Math.max(ans, s[i][i]);

}

System.out.println(ans);

}

Решение

Иницианилизируем двумерный массив [latex]s[/latex], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.

Ссылки

e-olymp 6122. Простой стек

30/06/2017 by Шостак Дмитрий

Задача

Формулировка задания на e-olymp.

Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n — Добавить в стек число n (значение n задается после команды). Вывести ok.
pop — Удалить из стека последний элемент. Программа должна вывести его значение.
back — Вывести значение последнего элемента, не удаляя его из стека.
size — Вывести количество элементов в стеке.
clear — Очистить стек и вывести ok.
exit — Вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

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

Каждая строка содержит одну команду.

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

Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

Входные данные	Выходные данные
push 2 push 3 push 5 back size pop size push 7 pop clear size exit	ok ok ok 5 3 5 2 ok 7 ok 0 bye

Отмечу так же, что программа успешно прошла все тесты на сайте e-olymp со следующими результатами.

Решение

class Stack {

	Vector<Integer> storage;
	
	public Stack()
	{
		storage = new Vector<Integer>();
	}
	
	void push(int number)
	{
		this.storage.add(number);
	}
	
	int pop()
	{
		int lastNumber = storage.lastElement();
		storage.remove(storage.size() - 1);
		return lastNumber;
	}
	
	int back()
	{
		int lastNumber = storage.lastElement();
		return lastNumber;
	}
	
	int size()
	{
		return storage.size();
	}
	
	void clear()
	{
		storage.clear();
	}
	
	String exit()
	{
		return "bye";
	}
	
}


public class Main {

	public static void main(String[] args) {
		Stack stack = new Stack();
		Scanner input = new Scanner(System.in);
		int number;
		String request;
		while(input.hasNextLine())
		{	
			request = input.next();
			if(request.equals("push"))
			{
				number = input.nextInt();
				stack.push(number);
				System.out.println("ok");
			}
			else if(request.equals("pop")) System.out.println(stack.pop());
			else if(request.equals("back")) System.out.println(stack.back());
			else if(request.equals("size")) System.out.println(stack.size());
			else if(request.equals("clear")) 
			{
				stack.clear();
				System.out.println("ok");
			}
			else if(request.equals("exit"))
			{
				System.out.println(stack.exit());
				break;
			}
		}
	}
}

class Stack {

Vector<Integer> storage;

public Stack()

{

storage = new Vector<Integer>();

}

void push(int number)

{

this.storage.add(number);

}

int pop()

{

int lastNumber = storage.lastElement();

storage.remove(storage.size() - 1);

return lastNumber;

}

int back()

{

int lastNumber = storage.lastElement();

return lastNumber;

}

int size()

{

return storage.size();

}

void clear()

{

storage.clear();

}

String exit()

{

return "bye";

}

public class Main {

public static void main(String[] args) {

Stack stack = new Stack();

Scanner input = new Scanner(System.in);

int number;

String request;

while(input.hasNextLine())

{

request = input.next();

if(request.equals("push"))

{

number = input.nextInt();

stack.push(number);

System.out.println("ok");

}

else if(request.equals("pop")) System.out.println(stack.pop());

else if(request.equals("back")) System.out.println(stack.back());

else if(request.equals("size")) System.out.println(stack.size());

else if(request.equals("clear"))

{

stack.clear();

System.out.println("ok");

}

else if(request.equals("exit"))

{

System.out.println(stack.exit());

break;

}

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Структура класса Stack из себя представляет следующее:

Динамический массив storage типа Vector<Integer> , который, по сути, и является хранилищем элементов стека;
Конструктор, в котором происходит инициализация вектора storage ;
Метод push(int number) типа void , который принимает как параметр число, и заносит это число в стек;
Метод pop() типа int , который возвращает значение верхнего элемента стека и извлекает его;
Метод back() типа int , который возвращает значение верхнего элемента стека, без его извлечения;
Метод size() , который возвращает количество элементов, находящихся в стеке;
Метод clear() , который очищает стек;
Метод exit() типа String , который возвращает строку «bye».

e-olymp 6123. Стек с защитой от ошибок

26/08/2016 by Дарья Пиндус

Задача

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

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

Команды для стека.

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

Соответствующие значения для каждой команды(см. выше).

Тесты

№	Последовательность	Результат
1	push 2 back pop size pop push 1 size exit	ok 2 2 0 error ok 1 bye
2	push 3 push 1 push 5 size pop size exit	ok ok ok 3 5 2 bye
3	back push 9 pop pop exit	error ok 9 error bye
4	size push 1 size back pop exit	0 ok 1 1 1 bye

Код

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
class Stack {
 
    private int pointer;
    private int[] stack;
    private int size;
 
 
    public Stack() {
        this(20);
    }
 
    public Stack(int capacity) {
            size = capacity;
            stack = new int[size];
            pointer = -1;
    }
 
    public void push(int element) {
        stack[++pointer] = element;
    }
 
    public int pop() {
        int i = stack[pointer];
        stack[pointer--] = 0;
        return i;
    }
 
    public int back() {
        return stack[pointer];
    }
 
    public void clear() {
        Arrays.fill(stack, 0);
        pointer = -1;
    }
 
    public boolean isEmpty() {
        if (pointer < 0)
            return true;
        else
            return false;
    }
 
    public int size() {
        return this.pointer + 1;
    }
 
    public static void main(String[] args) {
        Stack stack = new Stack();
 
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();
 
        while (!command.equals("exit")) {
            if (command.matches("^push [0-9]")) {
                String[] comm = command.split(" ");
                stack.push(Integer.parseInt(comm[1]));
                System.out.println("OK");
            } else if (command.equals("pop")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.pop());
                }
            } else if (command.equals("size")) {
                System.out.println(stack.size());
            } else if (command.equals("back")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.back());
                }
            } else if (command.equals("clear")) {
                stack.clear();
                System.out.println("OK");
            } else {
                System.out.println("Command doesn't exist");
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
 
    }
}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

class Stack {

private int pointer;

private int[] stack;

private int size;

public Stack() {

this(20);

}

public Stack(int capacity) {

size = capacity;

stack = new int[size];

pointer = -1;

}

public void push(int element) {

stack[++pointer] = element;

}

public int pop() {

int i = stack[pointer];

stack[pointer--] = 0;

return i;

}

public int back() {

return stack[pointer];

}

public void clear() {

Arrays.fill(stack, 0);

pointer = -1;

}

public boolean isEmpty() {

if (pointer < 0)

return true;

else

return false;

}

public int size() {

return this.pointer + 1;

}

public static void main(String[] args) {

Stack stack = new Stack();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.matches("^push [0-9]")) {

String[] comm = command.split(" ");

stack.push(Integer.parseInt(comm[1]));

System.out.println("OK");

} else if (command.equals("pop")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.pop());

}

} else if (command.equals("size")) {

System.out.println(stack.size());

} else if (command.equals("back")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.back());

}

} else if (command.equals("clear")) {

stack.clear();

System.out.println("OK");

} else {

System.out.println("Command doesn't exist");

}

command = scanner.nextLine();

}

System.out.println("bye");

}

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя $cursor$ . $cursor$ указывает на последний элемент в строке. Изначально $cursor$ , т.к. элементы в массиве, на которые бы он указывал, отсутствуют.

$push n$ записывает в ячейку с номером $cursor$ элемент $n$ . $size$ возвращает $cursor$ т.е. действительный размер стека. $pop$ возвращает последний помещённый в стек элемент, то есть элемент с номером $pointer+1$ , при этом удаляя его из стека. $back$ возвращает последний помещённый в стек элемент, то есть элемент с номером $cursor-1$ .В обоих случаях для проверки того, пуст ли стек, используется логическая функция $error$ . $clear$ обнуляет массив $cursor$ и присваивает $cursor$ начальное значение = -1.Команды считываются и выполняются пока не будет введено $exit$ , после чего выведется соответствующее сообщение и программа завершится.