e-olymp 595. Новый Лабиринт Амбера

27/12/2018 by Даниель Савчак

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

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

№	Входные данные	Выходные данные
1	5 1000 2 3 1 3	6
2	2 1 2	2
3	4 1 3 100 0	3

Решение с использованием цикла

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] dp = new int [n+1];
		for(int i = 1; i<=n; ++i){
        		dp[i] = in.nextInt();
		}
		dp[0] = 0;
		dp[1] = 0;
		for(int i = 2; i<=n; ++i){
    		if(i - 3 >= 0)
        		dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);
		}
		System.out.print(dp[n]);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

int[] dp = new int [n+1];

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

dp[i] = in.nextInt();

}

dp[0] = 0;

dp[1] = 0;

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

if(i - 3 >= 0)

dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);

}

System.out.print(dp[n]);

}

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

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

e-olymp 974. Флойд-1

27/12/2018 by Даниель Савчак

Задача

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

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

В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Тесты

#	Входные данные	Выходные данные
1	2 0 0 0 0	0 0 0 0
2	4 1 2 0 0 2 2 4 4 0 0 1 1 3 4 2 1	1 0 0 0 2 2 2 2 0 0 1 0 2 2 2 1
3	2 3 2 1 1	3 2 1 1

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n;
		n = in.nextInt();
		int [][] a = new int[n][n];
		for( int i=0 ; i<n ; i++ )
    	{
        	for( int j=0 ; j<n ; j++ )
        	{
        	    a[i][j] = in.nextInt();
       		}
    	}
    
    	for( int k=0 ; k<n ; k++ )
    	{
        	for( int i=0 ; i<n ; i++ )
        	{
        	    for( int j=0 ; j<n ; j++ )
        	    {
        	    	if( i!=j )
                	{
                	    a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]);
              		}
        		}
    		}
		}
		for( int i=0 ; i<n ; i++ )
    	{
    	    for( int j=0 ; j<n ; j++ )
    	    {
    	    	System.out.print(a[i][j]);
    	    	if(j+1 == n)
    	    	{
    	    		System.out.print("\n");
    	    	}
    	    	else {
    	    		System.out.print(' ');
    	    	}
    	    }
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

int [][] a = new int[n][n];

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

{

for( int j=0 ; j<n ; j++ )

{

a[i][j] = in.nextInt();

}

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

{

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

{

for( int j=0 ; j<n ; j++ )

{

if( i!=j )

{

a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]);

}

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

{

for( int j=0 ; j<n ; j++ )

{

System.out.print(a[i][j]);

if(j+1 == n)

{

System.out.print("\n");

}

else {

System.out.print(' ');

}

Решение

Считываем число вершин, затем матрицу смежности. Записываем матрицу смежности в массив указателей. Затем для создания матрицы минимальных путей заменяем каждый элемент матрицы на минимум из непосредственного расстояния между вершинами в матрице смежности и расстоянием между ними, проходящим через одну из их общих вершин. Выводим матрицу минимальных путей.

Ссылки

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

Код решения на ideone.com.

e-olymp 7340. Поле-чудес

27/12/2018 by Даниель Савчак

Задача

Петрик і Марічка захопились грою поле-чудес: Марічка записує слово, що складається з великих англійських букв, а Петрик старається розпізнати його, причому відгадана буква відкривається на всіх позиціях, де вона міститься. За яку найменшу кількість ходів Петрик зможе відгадати задане слово.

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані	Вихідні дані
[latex]GOOGLE[/latex]	[latex]4[/latex]
[latex]ALBUS[/latex]	[latex]5[/latex]
[latex]OOO[/latex]	[latex]1[/latex]

Код програми

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
        String s;
        s = in.next();

        for (int j = 0; j < s.length(); j++) {
            int i = j + 1;
            while(i< s.length())
            {
                if (s.charAt(j) == s.charAt(i) && i!= j)
                {
                    String s1=s.substring(0, i);
                    String s2 = s.substring(i+1,s.length());
                    s=s1.concat(s2);
                }
                else i++;
            }
        }
        System.out.println(s.length());
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

Scanner in = new Scanner(System.in);

String s;

s = in.next();

for (int j = 0; j < s.length(); j++) {

int i = j + 1;

while(i< s.length())

{

if (s.charAt(j) == s.charAt(i) && i!= j)

{

String s1=s.substring(0, i);

String s2 = s.substring(i+1,s.length());

s=s1.concat(s2);

}

else i++;

}

System.out.println(s.length());

}

Рішення завдання

Створимо місце для слова і прочитаємо його,далі для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква..

Код програми з множиною

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		SortedSet <Character> set = new TreeSet<>();
		Scanner in = new Scanner(System.in);
		String s = in.next();
		for(int i = 0; i < s.length(); i++){
        	set.add(s.charAt(i));
		}
		System.out.print(set.size());
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

SortedSet <Character> set = new TreeSet<>();

Scanner in = new Scanner(System.in);

String s = in.next();

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

set.add(s.charAt(i));

}

System.out.print(set.size());

}

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

e-olymp 5282. Седловые точки

24/12/2018 by Даниель Савчак

Задача

Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.
Saddle point

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

Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].

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

Выведите количество седловых точек.

Тесты

#	Входные данные	Выходные данные
1	2 2 0 0 0 0	4
2	3 3 1 2 3 4 3 6 9 5 3	0
3	4 4 1 2 0 0 2 2 4 4 0 0 1 1 3 4 2 1	0
4	2 2 3 2 1 1	1

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static  int Unknown = 1001;
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m,uf = 0,maxi;
		//input
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		m = in.nextInt();
		int [][] x = new int[n][m]; 
    	for (int i = 0; i < n; i++) 
        	for (int j = 0; j < m; j++) 
            	x[i][j] = in.nextInt();
    	//workspace
    	int[] max = new int[m];
    	for (int i = 0; i < m; i++){
    	    max[i] = Unknown;   
    	}
		for (int i = 0; i < n; i++) {
        	int min = x[i][0];
        	for (int j = 1; j < m; j++) {
            	if ( min > x[i][j] ) {
                	min = x[i][j];
            	}
        	}
        	for (int j = 0; j < m; j++) {
            	if (x[i][j] == min) {
                	if (max[j] != Unknown){
                    	maxi = max[j];  
                	}
                	else {
                    	maxi = x[i][j];
                    	for (int l = 0; l < n; l++) {
                    	    if (maxi < x[l][j]){
                        	    maxi = x[l][j];
                        	}
                    	}
                    	max[j] = maxi;
                	}
                	if ( maxi == min) {
                    	uf++;
                	}
            	}
    		}
    	}
    	//output
		System.out.print(uf);
		}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

public static int Unknown = 1001;

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

{

int n, m,uf = 0,maxi;

//input

Scanner in = new Scanner(System.in);

n = in.nextInt();

m = in.nextInt();

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

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

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

x[i][j] = in.nextInt();

//workspace

int[] max = new int[m];

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

max[i] = Unknown;

}

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

int min = x[i][0];

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

if ( min > x[i][j] ) {

min = x[i][j];

}

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

if (x[i][j] == min) {

if (max[j] != Unknown){

maxi = max[j];

}

else {

maxi = x[i][j];

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

if (maxi < x[l][j]){

maxi = x[l][j];

}

max[j] = maxi;

}

if ( maxi == min) {

uf++;

}

//output

System.out.print(uf);

}

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

Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!

Ссылки

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

Код решения на ideone.com.

e-olymp 203. Кубики-2

24/12/2018 by Даниель Савчак

Задача

После Нового года Витэк решил стать банкиром и поэтому стал играться только кубиками с цифрами, ведь будущая профессия требовала умения четко и быстро оперировать с цифрами и числами. И опять ему нравились такие расположения кубиков, на которых последовательность изображенных на них цифр читалась в обеих направлениях одинаково.
Каждое утро, придя в детсад Витэк сразу смотрел на разложенные на полу кубики, и если последовательность не читалась в обеих направлениях одинаково, доставал какое-то количество новых кубиков и размещал их правее, чтобы получить такое размещение кубиков, которое соответствовало его требованию.
Какое наименьшее количество кубиков нужно доставить для этого Витэку?

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

В первой строке – количество разложенных перед Витэком кубиков [latex]N[/latex] [latex](1 ≤ N ≤ 100)[/latex], в следующей строке последовательность из [latex]N[/latex] цифр на кубиках через пробел.

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

Наименьшее количество кубиков, которое нужно правее доставить Витэку.

Тесты

#	Входные данные	Выходные данные
1	3 1 2 3	2
2	5 1 2 3 4 4	3
3	2 1 2	1
4	2 1 1	0

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in =  new Scanner(System.in);
		int n, h=0, k=0;
		n = in.nextInt();
    	int[] A = new int [n];
		for ( int i = 0; i < n; i++ ) {
    		A[i] = in.nextInt();
		}
		for ( int i = 0; i < n; i++ ) {
    		if ( A[n-1] == A[i] ) 
    		{
            	int t = 1;
            	for ( int j = i + 1; j < n - 1; j++ ) 
            	{
            		if ( A[j] != A[ n - 1 - t ] )
            		{
                    	k++;
                	}
                	t++;
        		}
            	if ( k == 0 ) 
            	{
            		h = i;
                	break;
            	}
            	else k = 0;
        	}
    	}
    	System.out.print(h);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n, h=0, k=0;

n = in.nextInt();

int[] A = new int [n];

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

A[i] = in.nextInt();

}

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

if ( A[n-1] == A[i] )

{

int t = 1;

for ( int j = i + 1; j < n - 1; j++ )

{

if ( A[j] != A[ n - 1 - t ] )

{

k++;

}

t++;

}

if ( k == 0 )

{

h = i;

break;

}

else k = 0;

}

System.out.print(h);

}

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

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

Ссылки

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

Код решения на ideone.com.

e-olymp 1317. Дни рождения

24/12/2018 by Даниель Савчак

Задача

Известно, что в группе из [latex]23[/latex] или более человек вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает [latex]50 \% [/latex]. Этот факт может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день – ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, факт не является парадоксом в строгом научном смысле – логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

Для заданного количества людей вычислить вероятность того, что двое из них родились в один день года. Год считать равным [latex]365[/latex] дням.

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

Каждая строка является отдельным тестом и содержит количество людей [latex]n[/latex] [latex](1 < n < 400)[/latex].

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

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

Тесты

Входные данные	Выходные данные
[latex]12[/latex]	[latex]16.70247888\%[/latex]
[latex]28[/latex]	[latex]65.44614723\%[/latex]
[latex]399[/latex]	[latex]100.00000000\%[/latex]

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double k = 1;
		int n;
		Scanner in = new Scanner(System.in);
			while (in.hasNextInt())
			{
				n = in.nextInt();
				for ( int i = 366 - n; i <= 365; i++ ) {
        			k = k * i;
        			k = k / 365;
        		}
        		System.out.printf("%.8f",100 * ( 1 - k ));
        		System.out.println("%");
        		k=1;
			}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

/* Name of the class has to be "Main" only if the class is public. */

class Main

{

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

{

double k = 1;

int n;

Scanner in = new Scanner(System.in);

while (in.hasNextInt())

{

n = in.nextInt();

for ( int i = 366 - n; i <= 365; i++ ) {

k = k * i;

k = k / 365;

}

System.out.printf("%.8f",100 * ( 1 - k ));

System.out.println("%");

k=1;

}

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

Посчитаем вероятность того, что дни рождения не совпадут. Вероятность того, что у двух людей дни рождения не совпадут равна [latex](1 — \frac{1}{365})[/latex]. Взяв третьего человека, вероятность того, что его день рождения не совпадет с предыдущими равна [latex](1 — \frac{2}{365})[/latex] и так далее до последнего человека, у которого вероятность не совпадения дня рождения с остальными равна [latex](1 — \frac{n-1}{365})[/latex]. Перемножив все эти значения через цикл получим вероятность того, что у всех [latex]n[/latex] человек из группы дни рождения не совпадут[latex]( \frac{365!}{(365-n)! \cdot 365^n})[/latex]. Так как вероятность не может быть больше [latex]1[/latex], то от [latex]1[/latex] отнимем кол-во неблагоприятных исходов и получим нужное. Но по условию ответ необходимо вывести в процентах, поэтому умножим на [latex]100[/latex] полученное. И так как [latex]n[/latex] будет вводиться пока пользователю угодно , запишем вышесказанное в цикл [latex]while[/latex].

Ссылки

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

Код решения на ideone.com.

e-olymp 513. Проблема Николая

05/11/2018 by Даниель Савчак

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

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

Вывести искомое количество способов.

Тесты

Входные данные	Выходные данные
[latex]500[/latex] [latex]2001[/latex]	[latex]0[/latex]
[latex]4[/latex] [latex]5[/latex]	[latex]4[/latex]
[latex]4[/latex] [latex]7[/latex]	[latex]3[/latex]
[latex]15[/latex] [latex]213[/latex]	[latex]147[/latex]
[latex]10[/latex] [latex]3[/latex]	[latex]0[/latex]

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

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n, m, k = 1;
    	n = in.nextInt();
    	m = in.nextInt();
    	if ( n >= m) 
    	{
        	System.out.print(0);
    	}
    	else 
    	{
    		for ( int i = 2; i <= n; i++ ) 
    		{
            	k = ( k * i ) % m;
        	}
        	System.out.print(k); 
    	}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n, m, k = 1;

n = in.nextInt();

m = in.nextInt();

if ( n >= m)

{

System.out.print(0);

}

else

{

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

{

k = ( k * i ) % m;

}

System.out.print(k);

}

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

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

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

Код решения на ideone.com.

e-olymp-7410.Маршрутне таксі

05/11/2018 by Даниель Савчак

Задача

У годину пік на зупинку одночасно під’їхали три маршрутних таксі, які слідують по одному маршруту, в які тут же набилися пасажири. Водії виявили, що кількість людей у різних маршрутках різна, і вирішили пересадити частину пасажирів так, щоб у кожній маршрутці було порівну пасажирів. Потрібно визначити, яку найменшу кількість пасажирів доведеться при цьому пересадити.

Вхідні дані

Три натуральних числа, що не перевищують [latex]100[/latex] — кількості пасажирів у першій, другій і третій маршрутках відповідно.

Вихідні дані

Виведіть одне число — найменшу кількість пасажирів, яку потрібно пересадити. Якщо це неможливо, виведіть слово [latex]IMPOSSIBLE[/latex] (великими літерами).

Тести

Вхідні дані	Вихідні дані
[latex]1[/latex] [latex]1[/latex] [latex]4[/latex]	[latex]2[/latex]
[latex]1[/latex] [latex]2[/latex] [latex]4[/latex]	[latex]IMPOSSIBLE[/latex]
[latex]1[/latex] [latex]3[/latex] [latex]5[/latex]	[latex]2[/latex]
[latex]9[/latex] [latex]3[/latex] [latex]9[/latex]	[latex]4[/latex]

Код програми

/* package whatever; // don't place package name! */

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

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int m1,m2,m3,x;
		m1 = in.nextInt();
		m2 = in.nextInt();
		m3 = in.nextInt();
		if ( ( m1 + m2 + m3 ) % 3 == 0 ) 
		{
			if ( m1 != m2 && m1 != m3 && m2 != m3 ) 
			{
				System.out.print(Math.max ( Math.max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ));
			}
			else if ( m1 == m2 ) 
			{ 
            	x = ( m3 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x); 
            	} 
            	else System.out.print(x);
    		}
    		else if ( m1 == m3 ) { 
            	x = ( m2 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x);
            	} 
            	else System.out.print(x);
    		}
    		else if ( m2 == m3 ) { 
            	x = ( m1 - ( m1 + m2 + m3 ) / 3 );
            	if ( x < 0 ) 
            	{ 
                	System.out.print(-x); 
            	} 
            	else System.out.print(x);
            }
		}
		else System.out.print("IMPOSSIBLE");
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

import java.lang.Math;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int m1,m2,m3,x;

m1 = in.nextInt();

m2 = in.nextInt();

m3 = in.nextInt();

if ( ( m1 + m2 + m3 ) % 3 == 0 )

{

if ( m1 != m2 && m1 != m3 && m2 != m3 )

{

System.out.print(Math.max ( Math.max ( m1 , m2 ) , m3 ) - ( ( m1 + m2 + m3 ) / 3 ));

}

else if ( m1 == m2 )

{

x = ( m3 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else if ( m1 == m3 ) {

x = ( m2 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else if ( m2 == m3 ) {

x = ( m1 - ( m1 + m2 + m3 ) / 3 );

if ( x < 0 )

{

System.out.print(-x);

}

else System.out.print(x);

}

else System.out.print("IMPOSSIBLE");

}

Рішення завдання

Спочатку відріжемо усі варіанти при яких розподілити пасажирів порівну не вийде так, що коли іх загальна кількість не ділиться націло на [latex]3[/latex] виводимо [latex]IMPOSSIBLE[/latex]. Коли розподілити пасажирів можна, розглядаємо [latex]4[/latex] випадки : коли у різних маршрутках кількість людей різна та коли у будь-яких двох маршрутках кількість однакова. Коли кількість різна, від максимальної кількості людей у трьох маршрутках віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей(у кінці ми маємо отримати це число, як кількість пасажирів у всіх маршрутних таксі), коли у двох маршрутках кількість однакова , то від кількості людей(у маршрутці, де іх більше або менше) віднімаємо число, яке дорівнює [latex]{{1}\over{3}}[/latex] від загальної кількості людей. Якщо відповідь менше [latex]0[/latex] то помножуюмо на [latex]-1[/latex].

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

e-olymp.472.Вероятность

05/11/2018 by Даниель Савчак

Задача

Вася придумал новую игру. Для игры требуется полоска из трёх стоящих в ряд клеток, фишки $n$ различных видов и непрозрачный мешок.

В начале игры одинаковое количество фишек каждого вида помещается в мешок. Игра заключается в том, что игрок вытаскивает из мешка фишки одну за другой и помещает эти фишки в клетки полоски в том порядке, в котором он их вытащил. Игра считается выигранной, если на каких-нибудь двух соседних клетках оказались одинаковые фишки.

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

Чтобы оценить среднюю частоту выигрышей, Вася решил найти такую величину: количество выигрышных вариантов заполнения полоски разделить на количество всех вариантов заполнения полоски. Количество всех вариантов заполнения полоски Вася нашёл самостоятельно (получилось $n^3$), а вот для нахождения количества выигрышных вариантов он обратился к своему знакомому, лучше разбирающемуся в математике и программировании, т.е. к Вам.

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

В первой строке входных данных находится число ($1 \leq n \leq 10$)— количество видов фишек.

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

Выведите одно число — количество выигрышных способов заполнить полоску из трёх клеток такими фишками.

Тесты

Входные данные	Выходные данные
[latex]2[/latex]	[latex]6[/latex]
[latex]3[/latex]	[latex]15[/latex]
[latex]5[/latex]	[latex]45[/latex]
[latex]7[/latex]	[latex]91[/latex]
[latex]9[/latex]	[latex]153[/latex]

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n;
		n = in.nextInt();
		System.out.print(2 * n * n - n);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n;

n = in.nextInt();

System.out.print(2 * n * n - n);

}

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

При проигрышных вариантах на выбранной полоске из трех позиций на первое место мы можем поставить [latex]n[/latex] вариантов фишек, а на вторую позицию [latex]n[/latex] — [latex]1[/latex],так как мы можем поставить все варианты кроме того вида, что использовали ранее, аналогично с третьей позицией. Теперь вычтем из кол-ва всех вариантов заполнения [latex]n^3[/latex] кол-во проигрышных [latex]n\cdot(n-1)^2[/latex] и получим кол-во выигрышных способов заполнить полоску. Все варианты могут быть выигрышными только в том случае, если у нас 1 вариант фишек.

Ссылки

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

Код решения на ideone.com.