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 4557. Одинокий король

26/12/2018 by Андрей Лисовой

Задача

Позиция короля на шахматной доске

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

Определите, побывал ли король дважды на одном и том же поле за свои $n$ ходов.

Возможные ходы короля

Вводные данные

В первой строке задано общее число ходов короля $n$ $(0 \leq n \leq 1000)$. В последующих $n$ строках заданы направления перемещения короля: строка под номером $i+1$ задаёт направление перемещения короля на $i$-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами $(x_1, y_1)$ и $(x_2, y_2)$ определяется по формуле: $d=|x_2 — x_1| + |y_2 — y_1|$.

Тесты

Входные данные	Выходные данные
$5\;1\;2\;4\;7\;4$	$4$
$5\;1\;2\;4\;6\;4$	$Ok$ $2$
$8\;3\;3\;7\;7\;5\;5\;3\;3$	$3$
$12\;2\;3\;4\;1\;3\;2\;5\;6\;8\;2\;1\;7$	$10$
$9\;2\;2\;3\;3\;4\;4\;7\;7\;7$	$Ok$ 2

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int[][] x = new int[2001][2001];
		int n = in.nextInt();
		int move;
		int xPos=1001, yPos=1001;
		for(int i = 0; i < n; i++) {
			move = in.nextInt();
			if(x[xPos][yPos] == 1) { 
            	System.out.print(i);
            	return;
        	}
        	else x[xPos][yPos]=1;
	        if(move == 1) {
	            xPos--;
	            yPos++;
	        }
	        if(move == 2) {
	            yPos++;
	        }
	        if(move == 3) {
	            xPos++;
	            yPos++;
	        }
	        if(move == 4) {
	            xPos++;
	        }
	        if(move == 5) {
	            xPos++;
	            yPos--;
	        }
	        if(move == 6) {
	            yPos--;
	        }
	        if(move == 7) {
	            xPos--;
	            yPos--;
	        }
	        if(move == 8) {
	            xPos--;
	        }
		}
		System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int[][] x = new int[2001][2001];

int n = in.nextInt();

int move;

int xPos=1001, yPos=1001;

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

move = in.nextInt();

if(x[xPos][yPos] == 1) {

System.out.print(i);

return;

}

else x[xPos][yPos]=1;

if(move == 1) {

xPos--;

yPos++;

}

if(move == 2) {

yPos++;

}

if(move == 3) {

xPos++;

yPos++;

}

if(move == 4) {

xPos++;

}

if(move == 5) {

xPos++;

yPos--;

}

if(move == 6) {

yPos--;

}

if(move == 7) {

xPos--;

yPos--;

}

if(move == 8) {

xPos--;

}

System.out.print("Ok" + "\n" + (Math.abs(xPos-1001)+Math.abs(yPos-1001)));

}

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

Создаем массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим $1$, и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

java@Cat

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

Tag Archives: шахматы

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

Задача

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

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

Тесты

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

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

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

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

Задача

Вхідні дані

Вихідні дані

Тести

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

Рішення

Посилання

e-olymp 4557. Одинокий король

Задача

Вводные данные

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

Тесты

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

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

Ссылки