e-olymp 44. Единицы

27/12/2018 by Валерия Ларикова

Задача

В арифметическом выражении разрешается использовать число [latex]1[/latex], операции сложения, умножения и скобки. Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число [latex]n[/latex]?

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

Одно число [latex]n[/latex] [latex](1 \leqslant n \leqslant 5000).[/latex]

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

Искомое количество единиц.

Тесты

#	Входные данные	Выходные данные
1	7	6
2	22	10
3	90	13
4	157	16
5	985	21

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
 
class Main
{
	public static int max = 5001;
	static int [] x = new int[max];
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k;
		x[1] = 1;
		x[2] = 2;
		for (int i = 3; i <= n; i++) {
			x[i] = x[i-1]+1;
			for (int j = 2; j <= Math.sqrt(n); j++) {
				if(i % j == 0) {
					k = x[j] + x[i/j];
					if( k < x[i]) x[i] = x[j] + x[i/j];
				}
			}
		}
		System.out.println(x[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

public static int max = 5001;

static int [] x = new int[max];

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k;

x[1] = 1;

x[2] = 2;

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

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

for (int j = 2; j <= Math.sqrt(n); j++) {

if(i % j == 0) {

k = x[j] + x[i/j];

if( k < x[i]) x[i] = x[j] + x[i/j];

}

System.out.println(x[n]);

}

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

Нам нужно найти минимальное количество [latex]1,[/latex] с помощью которых можно составить заданное число. Если последней операцией будет сложение, то первое слагаемое будет состоять из [latex]f(i)[/latex] единиц, а второе — из [latex]f(n-i).[/latex] Значение [latex]i[/latex] будем выбирать таким, чтобы сумма этих двух слагаемых была минимальной. Если [latex]n[/latex] нацело делится на [latex]i[/latex], то последней операцией будет умножение. Первый множитель будет состоять из [latex]f(i)[/latex] единиц, а второй — [latex]\displaystyle f \left (\frac{n}{i} \right).[/latex] Тогда значение [latex]i[/latex] будем перебирать до [latex]\sqrt{n},[/latex] чтобы сумма этих слагаемых была минимальной. Затем выводим искомое количество единиц на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

e-olymp 2803. МаркЕрованные кубики

26/12/2018 by Валерия Ларикова

Задача

У Витека есть набор кубиков, на котором изображены английские буквы, причём как маленькие, так и большие. Недавно мама подарила ему ещё и набор кубиков с цифрами, в результате чего Витек научился быстро считать в пределах [latex]10-[/latex]ти. А вот папа имел неосторожность подарить ему набор разноцветных маркеров, после чего Витек начал экспериментировать с кубиками с цифрами: он зарисовывал очередную цифру и на её месте рисовал цифру на единицу большую. Так как он прекрасно понимал, что цифры [latex]10[/latex] не существует, он вместо числа [latex]10[/latex] всегда писал цифру [latex]0.[/latex]

Учтите, что иногда мама звала Витека покушать и он не успевал завершить начатую работу и написать новую цифру – в этом случае кубик навсегда оставался пустым, такие кубики обозначены символом пробела.

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

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

Единственная строка, состоящая из описанных выше символов. Длина строки не превышает [latex]255[/latex] символов.

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

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

Тесты

#	Входные данные	Выходные данные
1	abc1234567890ABC	abc2345678901ABC
2	fgrt7645gft5	fgrt8756gft6
3	65748909674	76859010785
4	6ASD4890gf9674	7ASD5901gf0785
5	RFT768S7dfr	RFT879S8dfr

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		String str = bufferedReader.readLine();
		char[] s = str.toCharArray();
		for(int i = 0; i < str.length(); i++) {
			if(s[i]>='0' && s[i]<'9'){
				s[i]++;
			}
			else if(s[i]=='9') s[i]='0';
		}
		System.out.println(s);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String str = bufferedReader.readLine();

char[] s = str.toCharArray();

for(int i = 0; i < str.length(); i++) {

if(s[i]>='0' && s[i]<'9'){

s[i]++;

}

else if(s[i]=='9') s[i]='0';

}

System.out.println(s);

}

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

Для решения задачи вводим строку [latex]str[/latex] и преобразовываем её в массив символов. Так как у Витека есть кубики с буквами и цифрами, то проверяем, является ли элемент строки числом. Если да, то увеличиваем значение символа на [latex]1,[/latex] а если это [latex]9,[/latex] то заменяем её на [latex]0.[/latex]

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 19. The degree of symmetry

07/07/2016 by Владислав Козачков

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

Условие

Степенью симметрии натурального числа назовём количество пар его десятичных цифр, в которых цифры совпадают и расположены симметрично относительно середины десятичной записи этого числа. Если некоторая цифра стоит посередине десятичной записи, её тоже нужно учитывать в паре с ней самой. Найти степень симметрии числа [latex]n[/latex].

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

Одно натуральное число [latex]n < 2\cdot10^9.[/latex]

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

Вывести степень симметрии числа [latex]n[/latex].

Тесты:

Ввод	Вывод
123322	2
100	1
1010	0
1234321	4
1234567891	1

Код на Java:

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

class Main {
	public static void main (String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int i = 0;
		int j = 0;
		int num[] = new int[10];
		if (n == 0) {
			num[0] = 0;
		} else {
			while (n > 0) {
				num[j] = n % 10;
				n /= 10;
				j++;
			}
			j--;
		}
		int count = 0;
		while (i <= j) {
			if (num[i] == num[j]) count++;
			i++;
			j--;
		}
		System.out.print(count);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static void main (String[] args) {

Scanner scan = new Scanner(System.in);

int n = scan.nextInt();

int i = 0;

int j = 0;

int num[] = new int[10];

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

}

Алгоритм:

Вначале считываем число. Затем раскладываем его по цифрам внутри массива (в обратном порядке, но для нашей задачи порядок цифр значения не имеет):

if (n == 0) {
	num[0] = 0;
} else {
	while (n > 0) {
		num[j] = n % 10;
		n /= 10;
		j++;
	}
	j--;
}

if (n == 0) {

num[0] = 0;

} else {

while (n > 0) {

num[j] = n % 10;

n /= 10;

j++;

}

j--;

}

Затем подсчитываем собственно степень симметрии, двигаясь внутри массива от крайних цифр к центру, а после выводим результат:

int count = 0;
while (i <= j) {
	if (num[i] == num[j]) count++;
	i++;
	j--;
}
System.out.print(count);

int count = 0;

while (i <= j) {

if (num[i] == num[j]) count++;

i++;

j--;

}

System.out.print(count);

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

java@Cat

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

Tag Archives: числа

e-olymp 44. Единицы

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 2803. МаркЕрованные кубики

Задача

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

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

Тесты

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

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

Ссылки

e-olymp 19. The degree of symmetry

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки: