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

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

Задача

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

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

Одно число $n$ $(1 \leqslant n \leqslant 5000).$

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

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

Тесты

#	Входные данные	Выходные данные
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]);

}

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

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

Ссылки

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

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

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

Задача

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

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

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

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

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

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

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

Тесты

#	Входные данные	Выходные данные
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);

}

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

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

Ссылки

Ссылка на e-olymp

Ссылка на ideone

e-olymp 19. The degree of symmetry

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

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

Условие

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

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

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

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

Вывести степень симметрии числа $n$ .

Тесты:

Ввод	Вывод
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:

Алгоритм:

Ссылки: