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

11/06/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

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

#include <iostream>
using namespace std;

int main() {
    long int n;
    cin >> n;
    long int result;
    result = n*(n + 1)*(2*n + 1)/6;
    cout << result;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n;

cin >> n;

long int result;

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

cout << result;

return 0;

}

Рішення

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

Посилання

Related Images:

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

14/12/2019 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

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

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

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

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

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

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

#include <iostream>
#include <string>
using namespace std;

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = x.size() - 1; i >= 0; i--) {
    temporary = int(x[i] - '0') * y + carry;
    carry = temporary / 10;
    answer = char(temporary % 10 + '0') + answer;
}
while (carry) {
    answer = char(carry % 10 + '0') + answer;
    carry /= 10;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = x.size() - 1; i >= 0; i--) {

temporary = int(x[i] - '0') * y + carry;

carry = temporary / 10;

answer = char(temporary % 10 + '0') + answer;

}

while (carry) {

answer = char(carry % 10 + '0') + answer;

carry /= 10;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

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

s = multiplication(s, i);

}

cout << s << endl;

}

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

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

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

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

Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки: #include <vector> и #include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

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

Related Images:

e-olymp 1488. Шахматная головоломка

22/02/2019 by Инна Литвиненко

Задача

Борис очень любит различные шахматные головоломки. У него есть младший брат Вова. Борис очень любит задавать простые головоломки Вове, а в награду, если тот их решит, давать ему конфету. Но Вова, к сожалению, не очень любит шахматы, зато любит программирование.

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером $8 × 8$ клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

Напомним, что конь бьет те клетки, которые отстоят от его текущего положения на две клетки по горизонтали и одну клетку по вертикали, или на две клетки по вертикали и одну по горизонтали.

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.

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

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от $a$ до $h$, обозначающая номер столбца в котором находится конь, потом цифра от $1$ до $8$, обозначающая номер строки.

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

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

Гарантируется, что требуемая расстановка всегда существует.

Тесты

№	Ввод	Вывод
1	a1	d1 b2
2	h8	e8 g7
3	e5	b5 d4
4	c8	f8 d7
5	h6	e6 g5

Код

#include <iostream>
using namespace std;

int main() {
    int k1;
    char k0;
    cin >> k0 >> k1;
    int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски 
    char mid = char (('a' + n) - n / 2); //Находим середину доски
    if ( k1 != 1) {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;
    }
    else {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;
    } 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1;

char k0;

cin >> k0 >> k1;

int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски

char mid = char (('a' + n) - n / 2); //Находим середину доски

if ( k1 != 1) {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;

}

else {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;

}

return 0;

}

Решение

Для решения данной задачи ладью всегда будем размешать на две клетки левее или правее коня, а слона — на одну клетку вниз/вверх по диагонали от него.

Ссылки

Задача 1488 на e-olymp

Код задачи на Ideone

Related Images:

e-olymp 2820. Перемещение коня

30/06/2015 by Янішевська Альона Русланівна

Задача с сайта e-olimp №2820. Перемещение коня

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из n клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

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

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (a—h), задающая столбец и второй – цифра (1—8), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).

Тесты:

Пример входных данных	Пример выходных данных
e2 e4	To get from e2 to e4 takes knight 2 moves.
a1 b2	To get from a1 to b2 takes knight 4 moves.
b2 c3	To get from b2 to c3 takes knight 2 moves.
a1 h8	To get from a1 to h8 takes knight 6 moves.
a1 h7	To get from a1 to h7 takes knight 5 moves.
h8 a1	To get from h8 to a1 takes knight 6 moves.
b1 c3	To get from b1 to c3 takes knight 1 moves.
f6 f6	To get from f6 to f6 takes knight 0 moves.

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

#include<cstdio>
#include<queue>
using namespace std;
 
char a, b;
int nx, ny, tx, ty;
int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
int A[8][8];
 
int main() {
    while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {
        nx = a - 'a';
        ny--;
        tx = b - 'a';
        ty--;
        A[nx][ny] = 0;
        queue< pair<int, int> > q;
        q.push(make_pair(nx, ny));
        while(!q.empty()) {
            pair<int, int> c = q.front();
            int x = c.first, y = c.second;
            if(x == tx && y == ty) break;
            q.pop();
            for(int i = 0; i < 8; i++) {
                if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                    q.push(make_pair(x + mx[i], y + my[i]));
                    A[x + mx[i]][y + my[i]] =  A[x][y] + 1;
                }
            }
        }
        printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
    }
}

#include<cstdio>

#include<queue>

using namespace std;

char a, b;

int nx, ny, tx, ty;

int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };

int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };

int A[8][8];

int main() {

while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

queue< pair<int, int> > q;

q.push(make_pair(nx, ny));

while(!q.empty()) {

pair<int, int> c = q.front();

int x = c.first, y = c.second;

if(x == tx && y == ty) break;

q.pop();

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

if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.push(make_pair(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

Данную задачу можно решить с помощью алгоритма поиска в ширину. Из начальной клетки мы ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения (если новое значение меньше того, что записано в клетке — записываем его, а если больше — оставляем предыдущее). Длина в начальной клетке — 0, а длина в каждой последующей — 1.

Ссылка на засчитанное решение и код решения на ideone.

Related Images:

А 1041

29/06/2015 by Зелінський Вячеслав Олександрович

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

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

#include <iostream>
#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;
const bool SET_DIA = true, DEL_DIA = false;
int a[HEIGHT][WIDTH];				// доска
bool is_set[HEIGHT][WIDTH];			// Расположение слонов на доске
int count_null = WIDTH * HEIGHT;		// Количество пустых клеток
bool isEnd = false;				// Флаг выхода из рекурсии
const bool FIRST = true, SECOND = false;	// флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями
	while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){					// заполняем/очищаем первую\вторую диагональ
		if(is_firstD? true : x != j || y != i){
			if(set){							  
				a[y][x]++;
				if(a[y][x] == 1){				
					count_null--;
				}
			}else{								  
				a[y][x]--;
				if(a[y][x] == 0){					
					count_null++;
				}
			}
		}
		x += (is_firstD? 1 : -1);
		y++;
	}
}

int space(bool set, int level, int i, int j){	// функция осуществляет операции с диагоналями (установку \ удаление)
	is_set[i][j] = set;			// Сохраняем последнее расположение слонов
	int x, y;
	if(j>i){	// ищем начало прохода первой диагонали (параллельной или идентичной главной)
		y = 0;
		x = j-i;
	}else{
		x = 0;
		y = i-j;
	}
	diagonal(FIRST, set, x, y, i, j);
	// ищем начало второй диагонали (перпендикулярной главной (побочной))
	int sum = i+j;
	if(sum < WIDTH){
		x = sum;
		y = 0;
	}else{
		x = WIDTH-1;
		y = sum-x;
	}
	diagonal(SECOND, set, x, y, i, j);
}

bool find_permutation(int level=0){		
	level++;

	for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){			
	/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет
	  именно по этой причине, если мы задаем первого слона, то начинаем со второй ячейки строки 
	*/
		if(a[i][j] == 0){			
			space(SET_DIA, level, i, j);							// устанавливаем слона и поле под его боем 
			if(level != COUNT_EL){											
				find_permutation(level);											
				if(isEnd){						
					return false;
				}
			}else if(count_null == 0){					  
				cout << "Ответ найден:"<< endl << endl;			
				for( int i1=0 ; i1<HEIGHT ; i1++ ){			
					for( int j1=0 ; j1<WIDTH ; j1++ ){
						cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );
					}
				}
				isEnd = true;						
				return false;						
			}
			space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем 							
		}
	}
	level--;
}

int main(){
	find_permutation();
}

#include <iostream>

#include <cstdlib>

using namespace std;

const int COUNT_EL = 8, WIDTH = 8, HEIGHT = 8;

const bool SET_DIA = true, DEL_DIA = false;

int a[HEIGHT][WIDTH]; // доска

bool is_set[HEIGHT][WIDTH]; // Расположение слонов на доске

int count_null = WIDTH * HEIGHT; // Количество пустых клеток

bool isEnd = false; // Флаг выхода из рекурсии

const bool FIRST = true, SECOND = false; // флаги для индификации диагоналей

int diagonal(bool is_firstD, bool set, int x, int y, int i, int j){ // осуществляет все операции с диагоналями

while(y<HEIGHT && (is_firstD? (x<WIDTH) : (x >= 0))){ // заполняем/очищаем первую\вторую диагональ

if(is_firstD? true : x != j || y != i){

if(set){

a[y][x]++;

if(a[y][x] == 1){

count_null--;

}

}else{

a[y][x]--;

if(a[y][x] == 0){

count_null++;

}

x += (is_firstD? 1 : -1);

y++;

}

int space(bool set, int level, int i, int j){ // функция осуществляет операции с диагоналями (установку \ удаление)

is_set[i][j] = set; // Сохраняем последнее расположение слонов

int x, y;

if(j>i){ // ищем начало прохода первой диагонали (параллельной или идентичной главной)

y = 0;

x = j-i;

}else{

x = 0;

y = i-j;

}

diagonal(FIRST, set, x, y, i, j);

// ищем начало второй диагонали (перпендикулярной главной (побочной))

int sum = i+j;

if(sum < WIDTH){

x = sum;

y = 0;

}else{

x = WIDTH-1;

y = sum-x;

}

diagonal(SECOND, set, x, y, i, j);

}

bool find_permutation(int level=0){

level++;

for(int i = level-1, j = (level==1?1:0); j < WIDTH ; j++){

/*экспериментально было замечено, что при установки первого слона в самом начале строки нужных нам последовательностей найдено не будет

именно по этой причине, если мы задаем первого слона, то начинаем со второй ячейки строки

if(a[i][j] == 0){

space(SET_DIA, level, i, j); // устанавливаем слона и поле под его боем

if(level != COUNT_EL){

find_permutation(level);

if(isEnd){

return false;

}

}else if(count_null == 0){

cout << "Ответ найден:"<< endl << endl;

for( int i1=0 ; i1<HEIGHT ; i1++ ){

for( int j1=0 ; j1<WIDTH ; j1++ ){

cout << (is_set[i1][j1]? 1 : 0) << (j1+1 == WIDTH ? '\n' : ' ' );

}

isEnd = true;

return false;

}

space(DEL_DIA, level, i, j);// удаляем слона и поле под его боем

}

level--;

}

int main(){

find_permutation();

}

Определяем переменные: количество слонов, длинна и ширина шахматного поля, массив клеток поля. Далее определяем булевы переменные для добавления и удаления диагоналей, расположения слонов, выхода из рекурсии. Функция «giagonal» осуществляет все операции с диагоналями. Добавляет/удаляет диагонали(параллельные главной или побочной). Она принимает булевы переменные для определения того, добавляем мы главную диагональ или побочную, собираемся мы добавлять диагональ или удалять. А также координаты начала диагоналей, координаты расположения слона. Если клетку бьет какой-либо слон, прибавляем к ее значению 1. При этом число свободных клеток уменьшается. Если же мы удаляем диагональ, то просто уменьшаем количество бьющих данную клетку слонов (это указывается в самой клетке). Если удаленный слон был единственным, кто ее бил, увеличиваем число свободных клеток. Функция «space». Она используется как для удаления, так и для добавления диагоналей. В ней мы запоминаем последнее расположение слонов на доске и далее ищем начало прохода диагоналей. Для этого сначала мы определяем в какой части доски находится поставленный слон и исходя из этого, если оказалось, что координата по горизонтали больше координаты по вертикали, то следовательно начало первой диагонали будет в первой строке, в противном случае ее начало будет в первом столбце. Вторые координаты зависят от разности j-i. При поиске начала второй диагонали используем сумму i+j, если эта сумма меньше 8 (то есть слон находится ближе к верхнему левому углу доски, чем к правому нижнему) тогда диагональ начинается в первом столбце. Функция «find_permutation» (рекурсивно расставляет слонов). С каждой новым поставленным слоном увеличиваем переменную level, для определения в последствии момента установки последнего слона. Просматриваем клетки, если какая-то из них не под боем-ставим туда слона и запускаем функцию «space» для него. Так расставляем их, пока число слонов не достигнет 8. Если после какой-либо расстановки мы нашли правильный ответ, то используя булеву переменную isEnd выходим из рекурсии. Если после установки восьмого слона оказалось, что все поля были заполнены, то мы выводим: «Ответ найден» и печатаем доску (если булева переменная is_set — true, то есть этот элемент слон, тогда выводим 1, остальные клетки — 0). Далее выходим из всех циклов, определив переменную isEnd = true. Удаляем слонов и битые ими поля. Конец программы.

ideone.com

Related Images:

А1035

28/06/2015 by Ковальський Олександр Дмитрович

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

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

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

a1
b3
d2
b1

a1
h8

a1
c2
e3
g2
h4
g6
h8

Решение

#include <iostream>
#include <math.h>
using namespace std;

struct coord
	{
		int x,y;
	};
const int n=8;
int main()
	{
		int chessboard[n][n];
		bool k;
		string s0,s1;
		int step=0;
		coord start, finish;
		cin>>s0>>s1;
		start.x=(int)s0[0]-97;
		start.y=s0[1]-49;
		finish.x=(int)s1[0]-97;
		finish.y=s1[1]-49;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				chessboard[i][j]=-1;
		chessboard[start.x][start.y]=0;
		k=true;
		while(chessboard[finish.x][finish.y]==-1)
			{
				k=false;
				for(int i=0;i<n;i++)
					for(int j=0;j<n;j++)
						if(chessboard[i][j]==step)
							{
								for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)
									for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)
										if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))
											{
              									chessboard[a][b]=step+1;
              									k=true;
											}
							}
					if(!k) chessboard[finish.x][finish.y]=0;
					else step++;
			}
		if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;
		else
			{
				coord path[8];
				path[0].x=finish.x;
				path[0].y=finish.y;
				for(int i=0;i<step;i++)
					{
						int x=path[i].x;
						int y=path[i].y;
						for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)
							for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)
								if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))
									{
										path[i+1].x=a;
										path[i+1].y=b;
									}
					}
				for(int i=step;i>=0;i--)
				cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;
			}
		return 0;
	}

#include <iostream>

#include <math.h>

using namespace std;

struct coord

{

int x,y;

};

const int n=8;

int main()

{

int chessboard[n][n];

bool k;

string s0,s1;

int step=0;

coord start, finish;

cin>>s0>>s1;

start.x=(int)s0[0]-97;

start.y=s0[1]-49;

finish.x=(int)s1[0]-97;

finish.y=s1[1]-49;

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

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

chessboard[i][j]=-1;

chessboard[start.x][start.y]=0;

k=true;

while(chessboard[finish.x][finish.y]==-1)

{

k=false;

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

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

if(chessboard[i][j]==step)

{

for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)

for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)

if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))

{

chessboard[a][b]=step+1;

k=true;

}

if(!k) chessboard[finish.x][finish.y]=0;

else step++;

}

if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;

else

{

coord path[8];

path[0].x=finish.x;

path[0].y=finish.y;

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

{

int x=path[i].x;

int y=path[i].y;

for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)

for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)

if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))

{

path[i+1].x=a;

path[i+1].y=b;

}

for(int i=step;i>=0;i--)

cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;

}

return 0;

}

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

Related Images:

e-olimp 1098. Ходи ферзем!

01/05/2015 by Денисова Ольга

Задача о восьми ферзях

Задача. На шахматной доске 8х8 произвольным образом расставлено 8 ферзей, по одному на каждой вертикали, других фигур на доске нет. Ферзь может ходить на любое количество клеток как по диагонали, так и по вертикали или горизонтали, но при этом не может перепрыгивать через другие фигуры. Необходимо добиться такой позиции, в которой ни один ферзь не находится под боем любого другого, и сделать это за минимальное количество ходов.

Входные данные. В одной строке задано сначала натуральное число T (T < 6) — количество тестов. Далее через пробел задано T блоков по 8 целых чисел от 1 до 8 – номера горизонталей, на которых находится ферзь с i-той вертикали. Вертикали пронумерованы подряд.

Выходные данные. Одна строка, содержащая последовательность соответствующих минимальных количеств ходов без пробелов.

Тесты

Входные данные	Выходные данные	Комментарий
2 1 1 1 1 1 1 1 1 2 4 6 8 3 2 7 5	71	пройден

Решение

«Поиск с возвратом» в задаче о восьми ферзях.
Алгоритм.
При решении задачи используется два массива : массив расстановок из теста и массив правильной расстановки. Первоначально массив правильных расстановок — пустой (все значения элементов массива = -1).

Для вычисления правильных расстановок вызывается рекурсивная функция line_up (параметром которого является номер столбца). Внутри функции line_up вызывается функция check (параметр — номер столбца), она проверяет горизонтальную линию и две диагонали на поля, которые бьет ферзь. Элементам массива правильных расстановок присваиваются номера горизонтальных линий (алгоритм «Поиск с возвратом»).

Как только достигается одна из возможных правильных расстановок вызывается функция calc_min_strok(). Если элемент одного массива не равен элементу другого — это ход. Функция calc_min_strok() вычисляет количество ходов для данной расстановки и решает минимальное оно или нет для данного теста.

#include <iostream>
#include <stdio.h>
#include<fstream>
using namespace std;

const int n = 8;// Размер поля
int count_test = 0;// Количество тестов
int mincountstep = n + 1; //Количество ходов
int frtest[n]; //расстановка теста
int fr[n]; //правильная расстановка

bool check(int nf) 
// проверка битых полей
{ 
	if ( fr[nf] < 0 )  return false; //На всякий случай, чтобы не проверять поля где нет ферзей
    for (int i = 0; i < n && fr[i] >= 0; i++) {           
        if ( i == nf ) continue;
        if (fr[nf] == fr[i]  ) return false;  // (Горизонталь) 
        if ( (nf + fr[nf]) ==  (i + fr[i]) ) return false; // Нисходящая диагональ
        if ( (nf - fr[nf]) ==  (i - fr[i]) ) return false; // Восходящая диагональ
    }  
    return true; //если поле свободно
}

void calc_min_strok()
// Вычисление количества ходов и нахождение минимального
{
   int countstep = 0; // количество ходов
   for (int i = 0; i < n; i++){ 
      if ( frtest[i] != fr[i] ) countstep++;
   }
   if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)
//рекурсивня функция установки ферзей (стек расстановок)
 {
    if ( i > n-1) return false ;
    for (int j = 0; j < n; j++) { 
        fr[i] = j;
        if ( check(i) == true ) {              
            if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
            calc_min_strok();
            } else { 
                line_up(i+1);
            } 
        }
        fr[i] = -1 ;  
    } 
  return false ;
}

int main()
{
	cin >> count_test;
	//Обнуление начального массива
	for (int test = 0; test < count_test; test++ ){
	   mincountstep = n + 1;
       for (int i = 0; i < n; i++) fr[i] = -1; 
       //ввод данных теста
	   for (int i = 0; i < n; i++) {     
        	cin >> frtest[i];  
		    frtest[i]--;    
	   }
       line_up(0);    
       cout << mincountstep;
	}   
    
    return 0;
}

#include <iostream>

#include <stdio.h>

#include<fstream>

using namespace std;

const int n = 8;// Размер поля

int count_test = 0;// Количество тестов

int mincountstep = n + 1; //Количество ходов

int frtest[n]; //расстановка теста

int fr[n]; //правильная расстановка

bool check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей

for (int i = 0; i < n && fr[i] >= 0; i++) {

if ( i == nf ) continue;

if (fr[nf] == fr[i] ) return false; // (Горизонталь)

if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ

if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ

}

return true; //если поле свободно

}

void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

int countstep = 0; // количество ходов

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

if ( frtest[i] != fr[i] ) countstep++;

}

if ( mincountstep > countstep ) mincountstep = countstep;

}

bool line_up(int i)

//рекурсивня функция установки ферзей (стек расстановок)

{

if ( i > n-1) return false ;

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

fr[i] = j;

if ( check(i) == true ) {

if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

calc_min_strok();

} else {

line_up(i+1);

}

fr[i] = -1 ;

}

return false ;

}

int main()

{

cin >> count_test;

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

mincountstep = n + 1;

for (int i = 0; i < n; i++) fr[i] = -1;

//ввод данных теста

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

cin >> frtest[i];

frtest[i]--;

}

line_up(0);

cout << mincountstep;

}

return 0;

}

Решение на Java:

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

public class Main {
	static int n ;// Размер поля
	static int count_test ;// Количество тестов
	static int mincountstep ; //Количество ходов
	static int frtest[]; //расстановка теста
	static int fr[]; //правильная расстановка
	
	static boolean check(int nf) 
	// проверка битых полей
	{ 
		if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей
		for (int i = 0; i < n && fr[i] >= 0; i++) { 
			if ( i == nf ) continue;
			if (fr[nf] == fr[i] ) return false; // (Горизонталь) 
			if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ
			if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ
		} 
		return true; //если поле свободно
	}
	
	static void calc_min_strok()
	// Вычисление количества ходов и нахождение минимального
	{
		int countstep = 0; // количество ходов
		for (int i = 0; i < n; i++){ 
			if ( frtest[i] != fr[i] ) countstep++;
		}
		if ( mincountstep > countstep ) mincountstep = countstep;
	}
	
	static boolean line_up(int i)
	//рекурсивная функция установки ферзей (стек расстановок)
	{
		if ( i > n-1) return false ;
		for (int j = 0; j < n; j++) { 
			fr[i] = j;
			if ( check(i) == true ) { 
			if ( i == n-1) { //Если дошли до последней колонки и всё хорошо
				calc_min_strok();
			} else { 
				line_up(i+1);
			} 
			}
			fr[i] = -1 ; 
		} 
		return false ;
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		count_test = in.nextInt();
		n = 8;// Размер поля
		mincountstep = n + 1; //Количество ходов
		frtest = new int [n]; //расстановка теста
		fr = new int [n]; //правильная расстановка
		
		//Обнуление начального массива
		for (int test = 0; test < count_test; test++ ){
			mincountstep = n + 1;
			for (int i = 0; i < n; i++) fr[i] = -1; 
			//ввод данных теста
			for (int i = 0; i < n; i++) { 
				frtest[i] = in.nextInt();
				frtest[i]--; 
			}
			line_up(0); 
			System.out.print(mincountstep);
		} 
		System.out.println();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main {

static int n ;// Размер поля

static int count_test ;// Количество тестов

static int mincountstep ; //Количество ходов

static int frtest[]; //расстановка теста

static int fr[]; //правильная расстановка

static boolean check(int nf)

// проверка битых полей

{

if ( fr[nf] < 0 ) return false; //На всякий случай, чтобы не проверять поля где нет ферзей

for (int i = 0; i < n && fr[i] >= 0; i++) {

if ( i == nf ) continue;

if (fr[nf] == fr[i] ) return false; // (Горизонталь)

if ( (nf + fr[nf]) == (i + fr[i]) ) return false; // Нисходящая диагональ

if ( (nf - fr[nf]) == (i - fr[i]) ) return false; // Восходящая диагональ

}

return true; //если поле свободно

}

static void calc_min_strok()

// Вычисление количества ходов и нахождение минимального

{

int countstep = 0; // количество ходов

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

if ( frtest[i] != fr[i] ) countstep++;

}

if ( mincountstep > countstep ) mincountstep = countstep;

}

static boolean line_up(int i)

//рекурсивная функция установки ферзей (стек расстановок)

{

if ( i > n-1) return false ;

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

fr[i] = j;

if ( check(i) == true ) {

if ( i == n-1) { //Если дошли до последней колонки и всё хорошо

calc_min_strok();

} else {

line_up(i+1);

}

fr[i] = -1 ;

}

return false ;

}

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

count_test = in.nextInt();

n = 8;// Размер поля

mincountstep = n + 1; //Количество ходов

frtest = new int [n]; //расстановка теста

fr = new int [n]; //правильная расстановка

//Обнуление начального массива

for (int test = 0; test < count_test; test++ ){

mincountstep = n + 1;

for (int i = 0; i < n; i++) fr[i] = -1;

//ввод данных теста

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

frtest[i] = in.nextInt();

frtest[i]--;

}

line_up(0);

System.out.print(mincountstep);

}

System.out.println();

}

(Что бы прошло на e-olimp нужно удалить все комментарии)

Related Images:

Ю2.25

31/10/2014 by Карташов Денис Геннадійович

Задача. На шахматной доске стоят черный король и белые ладья и слон (ладья бьет по горизонтали и вертикали, слон — по диагоналям). Проверить, есть ли угроза королю и если есть, то от кого именно. Учесть возможность защиты (например, ладья не бьет через слона).

[latex]x _{1}, y_{1}[/latex]- координаты слона.

[latex]x _{2}, y_{2}[/latex]- координаты ладьи.

[latex]x _{3}, y_{3}[/latex]- координаты короля.

Таблица:

[latex]x _{1} [/latex]	[latex]y _{1} [/latex]	[latex]x _{2} [/latex]	[latex]y _{2} [/latex]	[latex]x _{3} [/latex]	[latex]y _{3} [/latex]	Предполагаемый результат	Комментарий
1	1	2	2	4	4	Ладья перекрывает шаг от слона.	Тест пройден
4	5	2	5	5	5	Слон перекрывает шаг от ладьи.	Тест пройден
1	1	4	5	5	5	Короля атакует и слон и ладья.	Тест пройден
5	1	4	5	5	5	Ладья атакует короля.	Тест пройден
5	1	5	3	5	5	Ладья атакует короля.	Тест пройден
3	1	4	2	5	3	Ладья перекрывает шаг от слона.	Тест пройден
4	2	3	1	5	3	Слон объявляет шаг королю.	Тест пройден
1	4	5	3	2	2	Короля не атакует никакая фигура.	Тест пройден

Исходный код программы:

#include <stdio.h>
#include <math.h>
int main (){
  int x1, x2, x3, y1, y2, y3;             //Объявляем переменные, обозначающие координаты фигур
  printf("Введите координаты слона\n");      //
  scanf("%d %d", &x1, &y1);                  //
  printf("Введите координаты ладьи\n");      //Вводим координаты фигур, printf'ы помогают не запутаться.
  scanf("%d %d", &x2, &y2);                  //
  printf("Введите координаты короля\n");     //
  scanf("%d %d", &x3, &y3);                  // 
  	if((x1==x2&&y1==y2)||(x2==x3&&y2==y3)||(x1==x3&&y1==y3)){    //Проверка правильности ввода
		printf("Ошибка");
		return 0;
	}    
	if(((x2!=x3)&&(y2!=y3))&&(fabs(x1-x3)!=fabs(y1-y3))){        //Проверка условия №1
		printf("Короля не атакует никакая фигура\n");
	}
	if(x2==x3||y2==y3){                                          //Проверка условия №2 
       	if( ((x1==x2&&x2==x3)||(y1==y2&&y2==y3)) &&                                           //Уточняющее условие №1
			(((y1>y2&&y3>y1)||(y1<y2&&y3<y1))||((x1>x2&&x3>x1)||(x1<x2&&x3<x1))) ) 
			printf("Слон перекрывает шаx от ладьи\n");
		else{
			printf("Ладья объявляет шаx королю\n");
		}
	}       
	if(fabs(x1-x3)==fabs(y1-y3)){                                //Проверка условия №3  
		if((fabs(x2-x1)==fabs(y2-y1)&&fabs(x3-x2)==fabs(y3-y2))&&                   //Уточняющее условие №2
			(((y2>y1)&&(y3>y2))||((y2<y1)&&(y3<y2)))) 
			printf("Ладья перекрывает шах от слона\n");
		else{
			printf("Слон объявляет шах королю\n");
		}
	}		
   return 0;   //Конец.
}

#include <stdio.h>

#include <math.h>

int main (){

int x1, x2, x3, y1, y2, y3; //Объявляем переменные, обозначающие координаты фигур

printf("Введите координаты слона\n"); //

scanf("%d %d", &x1, &y1); //

printf("Введите координаты ладьи\n"); //Вводим координаты фигур, printf'ы помогают не запутаться.

scanf("%d %d", &x2, &y2); //

printf("Введите координаты короля\n"); //

scanf("%d %d", &x3, &y3); //

if((x1==x2&&y1==y2)||(x2==x3&&y2==y3)||(x1==x3&&y1==y3)){ //Проверка правильности ввода

printf("Ошибка");

return 0;

}

if(((x2!=x3)&&(y2!=y3))&&(fabs(x1-x3)!=fabs(y1-y3))){ //Проверка условия №1

printf("Короля не атакует никакая фигура\n");

}

if(x2==x3||y2==y3){ //Проверка условия №2

if( ((x1==x2&&x2==x3)||(y1==y2&&y2==y3)) && //Уточняющее условие №1

(((y1>y2&&y3>y1)||(y1<y2&&y3<y1))||((x1>x2&&x3>x1)||(x1<x2&&x3<x1))) )

printf("Слон перекрывает шаx от ладьи\n");

else{

printf("Ладья объявляет шаx королю\n");

}

if(fabs(x1-x3)==fabs(y1-y3)){ //Проверка условия №3

if((fabs(x2-x1)==fabs(y2-y1)&&fabs(x3-x2)==fabs(y3-y2))&& //Уточняющее условие №2

(((y2>y1)&&(y3>y2))||((y2<y1)&&(y3<y2))))

printf("Ладья перекрывает шах от слона\n");

else{

printf("Слон объявляет шах королю\n");

}

return 0; //Конец.

}

Описание:

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

Алгоритм:

Объявляем переменные и вводим их значения.
Проверка условий.
1. Проверка правильности ввода (не совпадают координаты фигур).
2. Проверка условия №1. Проверяем, может ли короля хоть кто-то атаковать. Т. е. стоят ли ладья и король на одной горизонтальной или вертикальной линии или стоит ли король на одной диагонали со слоном.
3. Проверка условия №2. Проверяем отдельно ладью. Если какая-то координата у ладьи и короля совпадает, то проверяем, находится ли слон между ними. Вывод результата.
4. Проверка условия №1. Проверка слона, если король и слон расположены на одной диагонали, то проверяем, находится ли ладья между ними. Вывод результата.
Окончание работы.

Ссылка на Ideone.

Related Images:

Ю4.26

29/10/2014 by Калачьов Андрій Сергійович

Задача: На шахматной доске находятся король и несколько ферзей другого цвета. Проверить, находится ли король под угрозой и если да, кто ему угрожает. Положение фигур задано массивом A(8,8): 0 — клетка пуста, 1 — король, 2 — ферзь. Ферзь бьет по горизонтали, вертикали и диагоналям.

0	0	0	0
1	0	0	2
0	0	0	0
0	0	0	0
0	0	0	2
0	0	0	0
0	0	0	0
2	2	2	2

Король под угрозой от ферзя на клетке (2,8) (по вертикали)

Король под угрозой от ферзя на клетке (8,2) (по горизонтали)

Король под угрозой от ферзя на клетке (8,8) (по диагонали)

Решение:

Ссылка на ideone C++: http://ideone.com/h4ECiW

#include <iostream>
using namespace std;
const int n = 8;
int main() {
    double a[n][n]; int q,p;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            cin>>a[i][j];
            if (a[i][j] == 1) {q=i; p=j;}
        }
    }
    for (int i=q; i>=0; i--) {
        if (a[i][p]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<p+1<<")\n"; break;}}
    for (int i=q; i<n; i++) {
        if (a[i][p]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<p+1<<")\n"; break;}}
    for (int j=p; j>=0; j--) {
        if (a[q][j]==2) {cout << "Король под угрозой от ферзя ("<<q+1<<","<<j+1<<")\n"; break;}}
    for (int j=p; j<n; j++) {
        if (a[q][j]==2) {cout << "Король под угрозой от ферзя ("<<q+1<<","<<j+1<<")\n"; break;}}
        
    for (int i=q,j=p; (i>=0 && j>=0); (i-- && j--)){
        if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}
    for (int i=q,j=p; (i<n && j<n); (i++ && j++)){
        if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}
    for (int i=q,j=p; (i>=0 && j<n); (i-- && j++)){
        if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}
    for (int i=q,j=p; (i<n && j>=0);  (i++ && j--)){
        if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}
}

#include <iostream>

using namespace std;

const int n = 8;

int main() {

double a[n][n]; int q,p;

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

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

cin>>a[i][j];

if (a[i][j] == 1) {q=i; p=j;}

}

for (int i=q; i>=0; i--) {

if (a[i][p]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<p+1<<")\n"; break;}}

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

if (a[i][p]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<p+1<<")\n"; break;}}

for (int j=p; j>=0; j--) {

if (a[q][j]==2) {cout << "Король под угрозой от ферзя ("<<q+1<<","<<j+1<<")\n"; break;}}

for (int j=p; j<n; j++) {

if (a[q][j]==2) {cout << "Король под угрозой от ферзя ("<<q+1<<","<<j+1<<")\n"; break;}}

for (int i=q,j=p; (i>=0 && j>=0); (i-- && j--)){

if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}

for (int i=q,j=p; (i<n && j<n); (i++ && j++)){

if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}

for (int i=q,j=p; (i>=0 && j<n); (i-- && j++)){

if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}

for (int i=q,j=p; (i<n && j>=0); (i++ && j--)){

if (a[i][j]==2) {cout << "Король под угрозой от ферзя ("<<i+1<<","<<j+1<<")\n"; break;}}

}

Ссылка на ideone Java: http://ideone.com/sIJwPA

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n = 8;
        Scanner in = new Scanner(System.in);
        int[][] a = new int[n][n];
        int q=-1,p=-1;
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                a[i][j]=in.nextInt();
                if (a[i][j] == 1) {q=i; p=j;}
            }
        }
        if (q!=-1 && p!=-1){
            for (int i=q; i>=0; i--) {
                if (a[i][p]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,p+1);break;}}
            for (int i=q; i<n; i++) {
                if (a[i][p]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,p+1);break;}}
            for (int j=p; j>=0; j--) {
                if (a[q][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",q+1,j+1);break;}}
            for (int j=p; j<n; j++) {
                if (a[q][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",q+1,j+1);break;}}
                
            for (int i=q,j=p; (i>=0 && j>=0); i--, j--){
                if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}
            for (int i=q,j=p; (i<n && j<n); i++, j++){
                if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}
            for (int i=q,j=p; (i>=0 && j<n); i--, j++){
                if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}
            for (int i=q,j=p; (i<n && j>=0); i++, j--){
                if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}
        }
    }    
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n = 8;

Scanner in = new Scanner(System.in);

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

int q=-1,p=-1;

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

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

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

if (a[i][j] == 1) {q=i; p=j;}

}

if (q!=-1 && p!=-1){

for (int i=q; i>=0; i--) {

if (a[i][p]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,p+1);break;}}

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

if (a[i][p]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,p+1);break;}}

for (int j=p; j>=0; j--) {

if (a[q][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",q+1,j+1);break;}}

for (int j=p; j<n; j++) {

if (a[q][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",q+1,j+1);break;}}

for (int i=q,j=p; (i>=0 && j>=0); i--, j--){

if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}

for (int i=q,j=p; (i<n && j<n); i++, j++){

if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}

for (int i=q,j=p; (i>=0 && j<n); i--, j++){

if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}

for (int i=q,j=p; (i<n && j>=0); i++, j--){

if (a[i][j]==2) {System.out.printf("Король под угрозой от ферзя (%d,%d)\n",i+1,j+1);break;}}

}

Сначала в цикле вводим массив и ищем где находится король (единичка). Найдя короля, начинаем искать ферзей в восьми направлениях от него (вниз, вверх, вправо, влево и также по диагоналям). Найдя ферзя по одному из направлений выводим его координаты и переходим на следующее направление т.к. все остальные не причинят угрозы королю, потому что между ними и королем стоит фигура (первый найденный ферзь).

Related Images:

Ю2.26

21/09/2014 by Кваша Дар`я Михайлівна

Задача. На шахматной доске стоят три ферзя (ферзь бьет по вертикали, горизонтали и диагоналям). Найти те пары из них, которые угрожают друг другу.

[latex]x_{1}[/latex]	[latex]y_{1}[/latex]	[latex]x_{2}[/latex]	[latex]y_{2}[/latex]	[latex]x_{3}[/latex]	[latex]y_{3}[/latex]	Результаты	Комментарий
6	8	3	5	6	3	Пара ферзей 1 и 2 угрожают друг другу Пара ферзей 1 и 3 угрожают друг другу	Пройден
1	5	6	8	7	3	Никто никому не угрожает	Пройден
3	3	8	8	7	1	Пара ферзей 1 и 2 угрожают друг другу	Пройден
2	8	4	7	7	4	Пара ферзей 2 и 3 угрожают друг другу	Пройден

Тесты:

Код на С

#include <stdio.h>
 
int main() 
{
	int x1,x2,x3,y1,y2,y3,k;
	//определим координаты фигур на доске
	scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3 );
	k=0;
 
	//начнем последовательную проверку на угрозу в каждой паре ферзей
 
	if ((x1==x2)||(y1==y2)||(abs(x1-x2)==abs(y1-y2)))
	{
	    printf("Пара ферзей 1 и 2 угрожают друг другу\n");
	    k++;
	}
	if ((x1==x3)||(y1==y3)||(abs(x1-x3)==abs(y1-y3)))
	{
	   printf("Пара ферзей 1 и 3 угрожают друг другу\n");
	   k++;
	}
	if ((x2==x3)||(y2==y3)||(abs(x2-x3)==abs(y2-y3))) 
	{
	   printf("Пара ферзей 2 и 3 угрожают друг другу\n");
	   k++;
	}
	if (k==0) printf("Никто никому не угрожает\n");
 
	return 0;
}

#include <stdio.h>

int main()

{

int x1,x2,x3,y1,y2,y3,k;

//определим координаты фигур на доске

scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3 );

k=0;

//начнем последовательную проверку на угрозу в каждой паре ферзей

if ((x1==x2)||(y1==y2)||(abs(x1-x2)==abs(y1-y2)))

{

printf("Пара ферзей 1 и 2 угрожают друг другу\n");

k++;

}

if ((x1==x3)||(y1==y3)||(abs(x1-x3)==abs(y1-y3)))

{

printf("Пара ферзей 1 и 3 угрожают друг другу\n");

k++;

}

if ((x2==x3)||(y2==y3)||(abs(x2-x3)==abs(y2-y3)))

{

printf("Пара ферзей 2 и 3 угрожают друг другу\n");

k++;

}

if (k==0) printf("Никто никому не угрожает\n");

return 0;

}

Код на Java

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	   Scanner in=new Scanner(System.in);
	   int x1, x2, x3, y1, y2, y3, k;
	   k=0;
	   x1=in.nextInt();
       y1=in.nextInt();
       x2=in.nextInt();
       y2=in.nextInt();
       x3=in.nextInt();
       y3=in.nextInt();
       if ((x1==x2)||(y1==y2)||(Math.abs(x1-x2)==Math.abs(y1-y2))){
	    System.out.println("Пара ферзей 1 и 2 угрожают друг другу");
	    k++;
	   }
	   if ((x1==x3)||(y1==y3)||(Math.abs(x1-x3)==Math.abs(y1-y3))){
	    System.out.println("Пара ферзей 1 и 3 угрожают друг другу");
	    k++;
	   }
	   if ((x2==x3)||(y2==y3)||(Math.abs(x2-x3)==Math.abs(y2-y3))){
	    System.out.println("Пара ферзей 2 и 3 угрожают друг другу");
	    k++;
	   }
	   if (k==0) System.out.println("Никто никому не угрожает");
		
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in=new Scanner(System.in);

int x1, x2, x3, y1, y2, y3, k;

k=0;

x1=in.nextInt();

y1=in.nextInt();

x2=in.nextInt();

y2=in.nextInt();

x3=in.nextInt();

y3=in.nextInt();

if ((x1==x2)||(y1==y2)||(Math.abs(x1-x2)==Math.abs(y1-y2))){

System.out.println("Пара ферзей 1 и 2 угрожают друг другу");

k++;

}

if ((x1==x3)||(y1==y3)||(Math.abs(x1-x3)==Math.abs(y1-y3))){

System.out.println("Пара ферзей 1 и 3 угрожают друг другу");

k++;

}

if ((x2==x3)||(y2==y3)||(Math.abs(x2-x3)==Math.abs(y2-y3))){

System.out.println("Пара ферзей 2 и 3 угрожают друг другу");

k++;

}

if (k==0) System.out.println("Никто никому не угрожает");

}

Решение:

В случае если фигуры стоят на одной вертикали или горизонтали соответствующие координаты будут равны. Таким образом, проверяя на равенство координаты, узнаем о существовании угрозы. В случае если фигуры стоят на одной диагонали можно заметить, что [latex] \left|x_{1}-x_{2 }\right|=\left|y_{1}-y_{2} \right|[/latex]. Таким образом, проверив и это условие, точно определим есть угроза или нет.

Также надо отметить тот случай, когда не существует никакой угрозы . Для этого введем счетчик [latex]k[/latex]. Если между какой-либо парой фигур есть угроза, то [latex]k[/latex] увеличивается на единицу. Если после проверки вышеупомянутых условий [latex]k[/latex] остается равным нулю, то делаем вывод, что никто никому не угрожает.

Related Images:

Ю2.24

18/09/2014 by Карагяур Мілан Сергійович

Задача: На шахматной доске стоят черный король и три белые ладьи (ладья бьет по горизонтали и вертикали). Проверить, не находится ли король под боем, а если есть угроза, то от кого именно.

x	y	x1	y1	x2	y2	x3	y3
3	6	1	1	3	7	2	5	Угроза от второй ладьи
1	2	7	8	4	6	3	6	Угрозы нет
1	2	5	4	3	7	1	2	Ошибка

#include <iostream>
using namespace std;
 
int main() 
{
    int x,y,x1,y1,x2,y2,x3,y3;
        //Вводим координаты фигур на шахматной доске(от 1 до 8)
    scanf("%d", &x);
    scanf("%d", &y);//Координаты короля
    scanf("%d", &x1);
    scanf("%d", &y1);//Координаты первой ладьи
    scanf("%d", &x2);
    scanf("%d", &y2);//Координаты второй ладьи
    scanf("%d", &x3);
    scanf("%d", &y3);//Координаты третьей ладьи
    if (((x!=x1) || (y!=y1)) && ((x!=x2) || (y!=y2)) && ((x!=x3) || (y!=y3)) && ((x1!=x2) || (y1!=y2)) && ((x1!=x3) || (y1!=y3)) && ((x2!=x3) || (y2!=y3)))
    {
    if ((x==x1) || (y==y1)) 
    {
         printf(" x = %d; y = %d \n x1 = %d;  y1 = %d \n Угроза от первой ладьи\n", x, y, x1, y1);
    }
    else
    {
            if ((x==x2) || (y==y2)) 
        {
         printf(" x = %d; y = %d \n x2 = %d;  y2 = %d \n Угроза от второй ладьи\n", x, y, x2, y2);
        }
        else
        {
            if ((x==x3) || (y==y3)) 
            {
             printf(" x = %d ; y = %d \n x3 = %d ;  y3 = %d \n Угроза от третьей ладьи\n", x, y, x3, y3);
            }
            else
            {
            printf(" x = %d ; y = %d \n x1 = %d ;  y1 = %d \n x2 = %d ;  y2 = %d \n x3 = %d ;  y3 = %d \n Угрозы нет", x, y, x1, y1, x2, y2, x3, y3);
            }
        }
    
    }
    }
    else
    {
    printf("Ошибка");
    }
return 0;
}

#include <iostream>

using namespace std;

int main()

{

int x,y,x1,y1,x2,y2,x3,y3;

//Вводим координаты фигур на шахматной доске(от 1 до 8)

scanf("%d", &x);

scanf("%d", &y);//Координаты короля

scanf("%d", &x1);

scanf("%d", &y1);//Координаты первой ладьи

scanf("%d", &x2);

scanf("%d", &y2);//Координаты второй ладьи

scanf("%d", &x3);

scanf("%d", &y3);//Координаты третьей ладьи

if (((x!=x1) || (y!=y1)) && ((x!=x2) || (y!=y2)) && ((x!=x3) || (y!=y3)) && ((x1!=x2) || (y1!=y2)) && ((x1!=x3) || (y1!=y3)) && ((x2!=x3) || (y2!=y3)))

{

if ((x==x1) || (y==y1))

{

printf(" x = %d; y = %d \n x1 = %d; y1 = %d \n Угроза от первой ладьи\n", x, y, x1, y1);

}

else

{

if ((x==x2) || (y==y2))

{

printf(" x = %d; y = %d \n x2 = %d; y2 = %d \n Угроза от второй ладьи\n", x, y, x2, y2);

}

else

{

if ((x==x3) || (y==y3))

{

printf(" x = %d ; y = %d \n x3 = %d ; y3 = %d \n Угроза от третьей ладьи\n", x, y, x3, y3);

}

else

{

printf(" x = %d ; y = %d \n x1 = %d ; y1 = %d \n x2 = %d ; y2 = %d \n x3 = %d ; y3 = %d \n Угрозы нет", x, y, x1, y1, x2, y2, x3, y3);

}

else

{

printf("Ошибка");

}

return 0;

}

Введем координаты каждой фигуры на шахматной доске от 1 до 8 (использовать отрицательные или дробные числа не имеет смысла). Проверим совпадает ли хотя бы один из координат короля с координатой хотя бы одной ладьи. Если, да то выводим соответствующее сообщение, если нет то выведем, что угрозы нет.

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

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


class Chess
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
        //Вводим координаты фигур на шахматной доске(от 1 до 8)
    int x = in.nextInt();   
    int y = in.nextInt();//Координаты короля
    int x1 = in.nextInt();   
    int y1 = in.nextInt();//Координаты первой ладьи
    int x2 = in.nextInt();   
    int y2 = in.nextInt();//Координаты второй ладьи
    int x3 = in.nextInt();   
    int y3 = in.nextInt();//Координаты третьей ладьи
    if (((x!=x1) || (y!=y1)) && ((x!=x2) || (y!=y2)) && ((x!=x3) || (y!=y3)) && ((x1!=x2) || (y1!=y2)) && ((x1!=x3) || (y1!=y3)) && ((x2!=x3) || (y2!=y3)))
    {
    if ((x==x1) || (y==y1)) 
    {
         System.out.format(" x = %d; y = %d \n x1 = %d;  y1 = %d \n Угроза от первой ладьи\n", x, y, x1, y1);
    }
    else
    {
            if ((x==x2) || (y==y2)) 
        {
         System.out.format(" x = %d; y = %d \n x2 = %d;  y2 = %d \n Угроза от второй ладьи\n", x, y, x2, y2);
        }
        else
        {
            if ((x==x3) || (y==y3)) 
            {
             System.out.format(" x = %d ; y = %d \n x3 = %d ;  y3 = %d \n Угроза от третьей ладьи\n", x, y, x3, y3);
            }
            else
            {
             System.out.format(" x = %d ; y = %d \n x1 = %d ;  y1 = %d \n x2 = %d ;  y2 = %d \n x3 = %d ;  y3 = %d \n Угрозы нет", x, y, x1, y1, x2, y2, x3, y3);
            }
        }
    
    }
    }
    else
    {
    System.out.println("Ошибка");
    }
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Chess

{

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

{

Scanner in = new Scanner(System.in);

//Вводим координаты фигур на шахматной доске(от 1 до 8)

int x = in.nextInt();

int y = in.nextInt();//Координаты короля

int x1 = in.nextInt();

int y1 = in.nextInt();//Координаты первой ладьи

int x2 = in.nextInt();

int y2 = in.nextInt();//Координаты второй ладьи

int x3 = in.nextInt();

int y3 = in.nextInt();//Координаты третьей ладьи

if (((x!=x1) || (y!=y1)) && ((x!=x2) || (y!=y2)) && ((x!=x3) || (y!=y3)) && ((x1!=x2) || (y1!=y2)) && ((x1!=x3) || (y1!=y3)) && ((x2!=x3) || (y2!=y3)))

{