e-olymp 1327. Ладьи на шахматной доске

04/10/2020 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

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

import java.math.BigInteger;
import java.util.Scanner;

class Main
{
	public static void main (String[] args) 
	{
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		BigInteger factorial = BigInteger.valueOf(1); 
		/* присваиваем результату 1, приводя к типу BigInteger;
		1 - нейтральный элемент относительно умножения */
		if(n == 0) {
			System.out.println(1);
		}
		else {
			for(int i = 1; i <=n; i++) {
				factorial = factorial.multiply(BigInteger.valueOf(i)); 
				// приводим i к типу BigInteger
			}
			System.out.println(factorial);
		}
	}
}

import java.math.BigInteger;

import java.util.Scanner;

class Main

{

public static void main (String[] args)

{

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

BigInteger factorial = BigInteger.valueOf(1);

/* присваиваем результату 1, приводя к типу BigInteger;

1 - нейтральный элемент относительно умножения */

if(n == 0) {

System.out.println(1);

}

else {

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

factorial = factorial.multiply(BigInteger.valueOf(i));

// приводим i к типу BigInteger

}

System.out.println(factorial);

}

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

Детали реализации

Для реализации алгоритма я использовала класс java.math.BigInteger, подробнее о нем можно почитать здесь.
Также для ввода данных я использовала класс java.util.Scanner, подробнее о нем можно почитать тут и вот тут.

Ссылки :
Задача на e-olymp
Код на ideone
Засчитанное решение

e-olymp 8659. Байтик та шахи

19/09/2020 by Паша Мацалышенко

Задача

Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.

Вхідні дані

Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.

Вихідні дані

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

Тести

№	Входные данные	Выходные данные
1	3	14
2	10	385
3	99	328350
4	999	332833500
5	10000	333383335000

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

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 i = new Scanner(System.in);
		long n = i.nextInt();
		long result = n*(n + 1)*(2*n + 1) / 6;
		System.out.println(result);
	}
}

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 i = new Scanner(System.in);

long n = i.nextInt();

long result = n*(n + 1)*(2*n + 1) / 6;

System.out.println(result);

}

Рішення

Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.

Посилання

e-olymp 399. Последствия гриппа в Простоквашино

19/09/2020 by Никита Репнин

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

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

Я сначала обрадовался, так как помню, что из шахматной доски он не мог выпилить больше 64-х квадратиков. Но скоро понял, что я глубоко ошибался.

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

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

Тесты

№	Входные данные	Выходные данные
1	3 2 3 4	1 0 2
2	5 3 11 7 43 27	0 0 0 0 0
3	6 2 28 42 14 64 0	1 2674440 24466267020 429 55534064877048198 1

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) throws java.lang.Exception{
		Scanner in = new Scanner(System.in);
		int n, k;
		long[] brackets = new long[33];
		brackets[0] = 1;
		for(int i = 1; i <= 32; ++ i){
			brackets[i] = 0;
			for(int j = 0; j < i; ++ j){
				brackets[i] += brackets[j] * brackets[i - 1 - j];
			}
		}
		n = in.nextInt();
    	        for (int i = 0; i < n; i ++) {
			k = in.nextInt();
			System.out.println(k % 2 == 0 ? brackets[k / 2] : 0);
		}
	}
}

import java.util.Scanner;

class Main{

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

Scanner in = new Scanner(System.in);

int n, k;

long[] brackets = new long[33];

brackets[0] = 1;

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

brackets[i] = 0;

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

brackets[i] += brackets[j] * brackets[i - 1 - j];

}

n = in.nextInt();

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

k = in.nextInt();

System.out.println(k % 2 == 0 ? brackets[k / 2] : 0);

}

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

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

java@Cat

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

Tag Archives: шахматная доска

e-olymp 1327. Ладьи на шахматной доске

Задача

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

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

Тесты

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

Алгоритм решения

Детали реализации

e-olymp 8659. Байтик та шахи

Задача

Вхідні дані

Вихідні дані

Тести

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

Рішення

Посилання

e-olymp 399. Последствия гриппа в Простоквашино

Задача

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

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

Тесты

Код

Решение