e-olymp 798. Платформы

02/12/2020 by Анна Цивинская

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

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

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

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

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) {
		final int MAX = 100001;
		Scanner sc = new Scanner(System.in);
        int amount_of_pltf = sc.nextInt();
        int[] energy, platforms,  list_of_pltf;
        int[] heights = new int[MAX];
        for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();
        
        energy = new int[MAX];
        platforms = new int[MAX];
        energy[1] = 0;
    	energy[2] = Math.abs(heights[2] - heights[1]);
    	platforms[1] = -1;
    	platforms[2] = 1;
    	
    	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
	    for (int j = 3; j <= amount_of_pltf; j++){
	        if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){
	            energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);
	            platforms[j] = j - 1;
	        } else {
	            energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);
	            platforms[j] = j - 2;
	        }
	    }
	    
	    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
	    int final_amount = 0;
	    list_of_pltf = new int[MAX];
	    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
	    
    	System.out.println(energy[amount_of_pltf] + "\n" + final_amount);
	    for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");
	}
}

import java.util.Scanner;

class Main{

public static void main (String[] args) {

final int MAX = 100001;

Scanner sc = new Scanner(System.in);

int amount_of_pltf = sc.nextInt();

int[] energy, platforms, list_of_pltf;

int[] heights = new int[MAX];

for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();

energy = new int[MAX];

platforms = new int[MAX];

energy[1] = 0;

energy[2] = Math.abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

list_of_pltf = new int[MAX];

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

System.out.println(energy[amount_of_pltf] + "\n" + final_amount);

for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

e-olimp 7848. Переставить соседние

20/09/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int arr[] = new int[n];
		for(int k = 0; k < n; k++){
        	arr[k] = i.nextInt();
		} 
    	for(int k = 1; k < n; k+=2){
        	int q = arr[k];
        	arr[k] = arr[k-1];
        	arr[k-1] = q;
		}
		for(int k = 0; k < n; k++){
    		System.out.print(arr[k] + " ");
		}
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int arr[] = new int[n];

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

arr[k] = i.nextInt();

}

for(int k = 1; k < n; k+=2){

int q = arr[k];

arr[k] = arr[k-1];

arr[k-1] = q;

}

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

System.out.print(arr[k] + " ");

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olimp 9536. Сумма матриц

20/09/2020 by Елизавета Савицкая

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

Входные данные	Выходные данные
1 1 2 3	5
1 5 4 3 7 2 1 3 2 2 1 6	7 5 9 3 7
2 2 0 4 2 3 5 4 1 6	5 8 3 9
3 4 3 4 5 6 1 2 3 4 7 6 5 4 0 0 -3 -2 -1 3 4 5 5 6 1 2	3 4 2 4 0 5 7 9 12 12 6 6
3 3 2 -128 47 -365 5 56 243 42 12 678 43 76 4 345 -23 97 -453 18	680 -85 123 -361 350 33 340 -411 30

Код

class Main{
	public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		int m = i.nextInt();
		int array1[][] = new int[n][m];
		int array2[][] = new int[n][m];
		int array_sum[][] = new int[n][m];
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array1[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array2[k][j] = i.nextInt();
    		}
		}
		for(int k = 0; k < n; k++){
        	for(int j = 0; j < m; j++){
        		array_sum[k][j] = array1[k][j] + array2[k][j];
        		System.out.print (array_sum[k][j] + " ");
    		}
    		System.out.println();
		}
	}
}

class Main{

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

int m = i.nextInt();

int array1[][] = new int[n][m];

int array2[][] = new int[n][m];

int array_sum[][] = new int[n][m];

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

for(int j = 0; j < m; j++){

array1[k][j] = i.nextInt();

}

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

for(int j = 0; j < m; j++){

array2[k][j] = i.nextInt();

}

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

for(int j = 0; j < m; j++){

array_sum[k][j] = array1[k][j] + array2[k][j];

System.out.print (array_sum[k][j] + " ");

}

System.out.println();

}

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olimp 1658. Факториал

19/09/2020 by Елизавета Савицкая

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные	Выходные данные
3	6
0	1
20	2432902008176640000

Решение №1

class Main {
	public static void main (String[] args) throws java.lang.Exception {
		java.util.Scanner i = new java.util.Scanner(System.in);
		int n = i.nextInt();
		long factorial = 1;
    	for(int k = 1; k <= n; k++) {
        	factorial *= k;
    	}
    	System.out.print(factorial);
	}
}

class Main {

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

java.util.Scanner i = new java.util.Scanner(System.in);

int n = i.nextInt();

long factorial = 1;

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

factorial *= k;

}

System.out.print(factorial);

}

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Решение №2

public class Main{
	public static long factorial(int a){
		if (a == 0)
        	return 1;
        else
        	return a*factorial(a - 1);
    }
    public static void main (String[] args) throws java.lang.Exception 	{
		java.util.Scanner i = new java.util.Scanner(System.in);
		int a;
		int n = i.nextInt();
        System.out.print(factorial(n));
	}
}

public class Main{

public static long factorial(int a){

if (a == 0)

return 1;

else

return a*factorial(a - 1);

}

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

java.util.Scanner i = new java.util.Scanner(System.in);

int a;

int n = i.nextInt();

System.out.print(factorial(n));

}

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

e-olymp 8680. Чётные соседи

19/09/2020 by Аліна Малихіна

Условие задачи

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

Программный код

public class Main
{
	public static void main(String[] args) {
		java.util.Scanner Javain = new java.util.Scanner(System.in);
	    int i=1, n, prev, pres, fut, count = 0;
        n = Javain.nextInt();
        prev = Javain.nextInt(); //вводим предыдущий элемент
        pres = Javain.nextInt(); //вводим текущий элемент
        while (i <= n - 2) {
            fut = Javain.nextInt();
            if (prev % 2 == 0 && fut % 2 == 0) 
                count++;
                prev = pres; //приравниваем предыдущий к текущему
                pres = fut; //приравниваем текущий к будущему
                i++;
        }
        System.out.print(count); 
	}
}

public class Main

{

public static void main(String[] args) {

java.util.Scanner Javain = new java.util.Scanner(System.in);

int i=1, n, prev, pres, fut, count = 0;

n = Javain.nextInt();

prev = Javain.nextInt(); //вводим предыдущий элемент

pres = Javain.nextInt(); //вводим текущий элемент

while (i <= n - 2) {

fut = Javain.nextInt();

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

System.out.print(count);

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

e-olymp 4439. Возведение в степень

17/09/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

class Main{
  public static long pow(long a, long b){
    if(b == 0){ 
      return 1; 
    } 
    if(b % 2 == 0){ 
      return pow(a * a, b / 2); 
    } 
    return a * pow(a, b - 1);
  }
  public static void main (String[] args){
    java.util.Scanner in = new java.util.Scanner(System.in);
    long a = in.nextLong(), b = in.nextLong();
    System.out.println(pow(a,b));
  }
}

class Main{

public static long pow(long a, long b){

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

public static void main (String[] args){

java.util.Scanner in = new java.util.Scanner(System.in);

long a = in.nextLong(), b = in.nextLong();

System.out.println(pow(a,b));

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

e-olymp 8283. Музыка

13/09/2020 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

import java.util.Scanner;

class Main {
	public static void main (String[] args) {
		int counter = 1;
		Scanner in = new Scanner(System.in);
		int quantity = in.nextInt();
		int instrument = in.nextInt();
		if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
			System.out.print(0);
		} else if (quantity == instrument) {
			for (int num = 1; num % quantity != 0; num += 6) {
				if (num != 1 && num % quantity == 1){
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		} else {
			for (int num = 1; num % quantity != instrument; num += 6) {
				if (num != 1 && num % quantity == 1) {
					System.out.print(0);
					System.exit(0);
				} else {
					counter++;
				}
			}
			System.out.print(counter);
		}
	}
}

import java.util.Scanner;

class Main {

public static void main (String[] args) {

int counter = 1;

Scanner in = new Scanner(System.in);

int quantity = in.nextInt();

int instrument = in.nextInt();

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

System.out.print(0);

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1){

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

System.out.print(0);

System.exit(0);

} else {

counter++;

}

System.out.print(counter);

}

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

e-olymp 8671. Представимые суммой квадратов

09/09/2020 by Алина Зозуля

Задача

Найдите все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

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

Одно натуральное число $n$ $( n \leqslant 10000)$.

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

Выведите в одной строке в возрастающем порядке все числа от $1$ до $n$, представимые в виде суммы двух квадратов различных натуральных чисел.

Тесты

№	Входные данные	Выходные данные
1	5	5
2	10	5 10
3	13	5 10 13
4	20	5 10 13 17 20
5	30	5 10 13 17 20 25 26 29

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

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

public class Ideone{
	static boolean check(int n)
	{
	    
	    for (int i = 1; i * i < n; i++) // перебор всех i
	    {   
	        double j = Math.sqrt (n - i * i);
	        if ((j == Math.floor(j)) && (j != i)) // проверка j целое или дробное 
	            {
	                return true; // комбинация найдена - возвращаем true
	            }
	    } 
	    return false; // комбинация не найдена - возвращаем false
	}
	public static void main(String a[]) {
	    Scanner in = new Scanner(System.in);
		int n = in.nextInt();	 // считываем число, до которого будем искать
	    for (int k = 5; k <= n; k++) // проверка для каждого k
	        if (check(k))
	            System.out.print(k + " ");
		in.close();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Ideone{

static boolean check(int n)

{

for (int i = 1; i * i < n; i++) // перебор всех i

{

double j = Math.sqrt (n - i * i);

if ((j == Math.floor(j)) && (j != i)) // проверка j целое или дробное

{

return true; // комбинация найдена - возвращаем true

}

return false; // комбинация не найдена - возвращаем false

}

public static void main(String a[]) {

Scanner in = new Scanner(System.in);

int n = in.nextInt(); // считываем число, до которого будем искать

for (int k = 5; k <= n; k++) // проверка для каждого k

if (check(k))

System.out.print(k + " ");

in.close();

}

Решение

Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.

Ссылки

Условие задачи на e-olymp

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

e-olymp 8946. Шаблон

09/09/2020 by Алина Зозуля

Условие

По заданному натуральному числу $n$ вывести изображение размером $n\times n$, образованное символами звездочка и пробел как показано в примере.

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

Одно натуральное число $n$.

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

Вывести изображение $n \times n$.

Тесты

№

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

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

* 
 *

* *

 *

* *

* *

* *

 * *

* *

* *

* * *

 * *

* * *

 * *

* * *

* * *

* *

* * *

* *

* * *

* * *

 * * *

* * *

 * * *

* * *

 * * *

* * *

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n;
    	String s1 = "", s2 = "";
    	Scanner myObj = new Scanner(System.in);
    	n = myObj.nextLong();

    	for (int i = 0; i < n; i++){//заполняем строки 
	        if (i % 2 == 0){
	            s1 += "*";
	            s2 += " ";
	        }
	        else {
	            s2 += "*";
	            s1 += " ";
	        }
	    }
	    for (int i = 0; i < n; i++){
	        if (i % 2 == 0){//выводим s1, если строка имеет четный номер
	           System.out.println(s1);
	        }
	        else System.out.println(s2);//выводим s2, если строка имеет нечетный номер
	    }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

{

long n;

String s1 = "", s2 = "";

Scanner myObj = new Scanner(System.in);

n = myObj.nextLong();

for (int i = 0; i < n; i++){//заполняем строки

if (i % 2 == 0){

s1 += "*";

s2 += " ";

}

else {

s2 += "*";

s1 += " ";

}

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

if (i % 2 == 0){//выводим s1, если строка имеет четный номер

System.out.println(s1);

}

else System.out.println(s2);//выводим s2, если строка имеет нечетный номер

}

Решение

Для того, чтобы вывести изображение как на рисунке достаточно заметить, что выводятся строки только двух видов и то поочерёдно. Первый вид — первым символом строки является $\ast$ и затем чередуется $\ast$ и пробел. Второй вид — первым символом строки является пробелом и затем чередуется $\ast$ и пробел. Мы заполняем две строки, по одной каждого вида. Нам остается только выводить строку необходимого нам вида, сделаем это в цикле.

Ссылки

Условие задачи на e-olymp

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

e-olymp 419. Задача 3n + 1

19/02/2019 by Александра Филистович

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

input n
print n
if n = 1 then STOP
if n is odd then n = 3 * n + 1
else n = n / 2
GOTO 2

input n

print n

if n = 1 then STOP

if n is odd then n = 3 * n + 1

else n = n / 2

GOTO 2

Например, для [latex]n = 22[/latex] будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n = 1[/latex] для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых [latex]0 < n < 1,000,000[/latex].
Длиной цикла числа [latex]n[/latex] будем называть количество сгенерированных чисел в последовательности включая [latex]1[/latex]. В приведенном примере длина цикла числа [latex]22[/latex] равна [latex]16[/latex].
Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше [latex]1000000[/latex] и больше [latex]0[/latex]. Считайте, что для вычислений достаточно использовать [latex]32[/latex] битный целочисленный тип.

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

Для каждой пары чисел [latex]i[/latex] и [latex]j[/latex] выведите числа [latex]i[/latex] и [latex]j[/latex] в том же порядке, в каком они поступили на вход. После чего выведите максимальную длину цикла среди всех целых чисел между [latex]i[/latex] и [latex]j[/latex] включительно. Для каждого теста три числа следует выводить в отдельной строке, разделяя одним пробелом.

Тесты

Входные данные	Выходные данные
1 10 100 200 201 210 900 1000	1 10 20 100 200 125 201 210 89 900 1000 174
1 10 10 1	1 10 20 10 1 20
5 25 70 54 38 250	5 25 24 70 54 113 38 250 128

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

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int i, j, ait;
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()) {
			i = scan.nextInt();
			j = scan.nextInt();
			int it, maxIt;
			maxIt = 0;
			for (int a = min(i, j); a <= max(i, j); a++) {
				it = 1;
				ait = a;
				while(ait != 1){
					if(ait % 2 == 1){
						ait = ait * 3 + 1;
					}
					else{
						ait = ait / 2;
					}
					it++;
				}
				if (it > maxIt) {
					maxIt = it;
				}
			}
			System.out.println(i + " " + j + " " + maxIt);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Main

{

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

{

int i, j, ait;

Scanner scan = new Scanner(System.in);

while(scan.hasNext()) {

i = scan.nextInt();

j = scan.nextInt();

int it, maxIt;

maxIt = 0;

for (int a = min(i, j); a <= max(i, j); a++) {

it = 1;

ait = a;

while(ait != 1){

if(ait % 2 == 1){

ait = ait * 3 + 1;

}

else{

ait = ait / 2;

}

it++;

}

if (it > maxIt) {

maxIt = it;

}

System.out.println(i + " " + j + " " + maxIt);

}

Решение

Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone