Антон Куперман

Задание

Над целым числом можно производить следующие операции:

Если число делится на 3, то делить его на 3;

Если число делится на 2, то делить его на 2;

Вычитать 1.

По заданному натуральному числу [latex]n[/latex] найти наименьшее количество операций, после выполнения которых получится 1.

Код

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

public class Main
{
	int[] x = new int[1000001];
	
	public int operations(int n)
	{
		x[1] = 0;
		for (int i = 2; i <= n; i++)
		{
			x[i] = x[i-1] + 1;
			if (i%2 == 0)
			{
				x[i] = Math.min(x[i], x[i/2] + 1);
			}
			if (i%3 == 0)
			{
				x[i] = Math.min(x[i], x[i/3] + 1);
			}
		}
		return x[n];
	}

	
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		Main x = new Main();
		while (in.hasNextInt())
		{
			int n = in.nextInt();
			System.out.println(x.operations(n));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

int[] x = new int[1000001];

public int operations(int n)

{

x[1] = 0;

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

{

x[i] = x[i-1] + 1;

if (i%2 == 0)

{

x[i] = Math.min(x[i], x[i/2] + 1);

}

if (i%3 == 0)

{

x[i] = Math.min(x[i], x[i/3] + 1);

}

return x[n];

}

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

Main x = new Main();

while (in.hasNextInt())

{

int n = in.nextInt();

System.out.println(x.operations(n));

}

Решение

Заведём массив на максимальное количество элементов. x[1] всегда будет равен 0, так как чтобы добраться от единицы к единице нужно 0 шагов. Затем, начиная со второго элемента, пробежимся по всему массиву до [latex]n[/latex], присваивая элементам значения предыдущих элементов, добавляя к ним единицу. Теперь остается выбрать минимум из самого элемента или элемента являющегося результатом деления(на 2 или на 3) с прибавлением единицы.

Задание

Телеканал 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], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.

Ввод	Вывод
1 5 10	0 3 3
12 7 21	3 3 4
256 1037 8771 9022 102651	8 11 13 13 19

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Антон Куперман

e-olymp 1560. Уменьшающееся число

Задание

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

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

Тесты

Код

Решение

Ссылки

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

Задание

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

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

Тесты

Код

Решение

Ссылки