e-olymp 9036. Комбинация игральных костей

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

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
public class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
	    int ans = 0;
	    Scanner myObj = new Scanner(System.in);
	    n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок
	    int a[] = new int[n+1]; //создаем массив
	    Arrays.fill(a, 0);
	    if (n == 1) ans = 1;
	    if (n == 2) ans = 2;
	    if (n == 3) ans = 4;
	    if (n == 4) ans = 8;
	    if (n == 5) ans = 16;
	    if (n == 6) ans = 32;
	    // частные случаи
	    
	    if (n > 6)
	    {
	        a[1] = 1; 
	        a[2] = 2; 
	        a[3] = 4; 
	        a[4] = 8;
	        a[5] = 16; 
	        a[6] = 32; 
	        for (int i = 7; i < n + 1; i++)
	        {
	            a[i]=0;
	            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
	                a[i] = ( a[i] + a[i-j] ) % 1000000007;
	        }
	        ans = a[n];
	    }
	    
	    System.out.println(ans);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

public class Ideone

{

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

{

int n;

int ans = 0;

Scanner myObj = new Scanner(System.in);

n = myObj.nextInt(); //считываем сумму, для которой будем считать количество перестановок

int a[] = new int[n+1]; //создаем массив

Arrays.fill(a, 0);

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

System.out.println(ans);

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

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

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

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

java@Cat

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

Author Archives: Алина Зозуля

e-olymp 9036. Комбинация игральных костей

Задача

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

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

Тесты

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

Решение

Ссылки

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

Задача

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

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

Тесты

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

Решение

Ссылки

e-olymp 8946. Шаблон

Условие

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

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

Тесты

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

Решение

Ссылки