Областная олимпиада по информатике, 2009-2010 учебный год

Задача A. Ферзи

Ограничение по времени:

2 sec.

Ограничение по памяти:

64MB

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

Формат входного файла

Первая строка входного файла содержит два целых числа N и K (1 ≤ N ≤ 10000, 1 ≤ К ≤ 100000). Каждая из следующих К строк содержит по два числа – номера строк и столбцов, на которых стоит соответствующий ферзь (строки и столбцы нумеруются целыми числами от 1 до N). Позиции всех ферзей различны. Числа в строках разделены пробелами.

Формат выходного файла

Выведите одно целое число – ответ к задаче.

Пример:

Вход:

3 2 
3 2 
2 3

 Ответ:

1

Комментарий/решение

#include<iostream>

using namespace std;

bool a[10001][10001];

void f(int x,int y,int n)

{

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

{

a[x][i]++;

a[i][y]++;

int q=x,w=y;

if((x+i<=n+1 && y+i<=n+1))

{

a[x+i][y+i]++;

if(x!=1 && y!=1)

{

a[x-i][y-i]++;

}

if(y!=1)

a[x+i][y-i]++;

if(x!=1)

a[x-i][y+i]++;

}

}

}

int main()

{

int n,m,cn=0;

cin>>n>>m;

for(int i=1;i<=m;i++)

{

int x,y;

cin>>x>>y;

a[x][y]++;

f(x,y,n);

}

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

{

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

{

if(!a[i][j]) cn++;

}

}

cout<<cn;

}

Решение

показать/скрыть код

//
//  2019/06/18 Ver1.0
//
//  Codeforces: vsekov
// _________________________s$_____ _________s 
// _________________________.s$$_____________s$ 
// ________________________s$$$’____________s$$ 
// ______________________.s$$$??_______,___s$$? 
// _____________________s$$$$?______.s$’___$$? 
// ________________,____$$$$$.______s$?____?$ 
// ________________$___$$$$$$s_____s$?_____?, 
// _______________s$___‘?$$$$$$s___$$$ 
// _______________$$____?$$$$$$s.__?$$s 
// _______________?$.____?$$$$$$$s_.s$$$____s? 
// _______________`$$.____?$$$$$$$_$$$$___s? 
// ________________?$$s____?$$$$$$s$$$?__s$’ 
// _________________?$$s____$$$$$s$$$$’__s$$ 
// _____________`s.__$$$$___s$$$$$$$$?_.s$$?__s 
// ______________$$_s$$$$..s$$$$$$$$$$$$$$?__s$ 
// ______________s$.s$$$$s$$$$$$$$$$$$$$$$_s$$ 
// _____________s$$$$$$$$$$$$$$$$$$$$$$$$$$$? 
// ____________s$$$ssss$$$$$$$$$$$$$ssss$$$$$? 
// ___________$$s§§§§§§§§§s$$$$$$s§§§§§§§§s$, 
// ___________?§§§§§§§§§§§§§s$s§§§§§§§§§? ?§§s 
// ___________§§§§§§§§§§§§§§§§§§§§§§§§? ?§§§§§ 
// ___________?§§§§§§§§§§§§§§§§§§§§§§§§ §§§§§ 
// ____________?§§§§§§§§§§§§§§§§§§§§§§§? ?§§§? 
// _____________?§§§§§§§§§§§§§§§§§§§§§§§ §§? 
// ______________?§§§§§§§§§§§§§§§§§§§§§§? ?? 
// ________________?§§§§§§§§§§§§§§§§§§§? 
// __________________?§§§§§§§§§§§§§§§? 
// ____________________?§§§§§§§§§§§? 
// _______________________?§§§§§? 
// _________________________?§?

#include <bits/stdc++.h>

using namespace std;

//container
//--------------
#define ft first
#define sd second

//definitions of types
//--------------
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VLL;
typedef vector<bool> VB;
typedef vector<char> VC;
typedef vector<double> VD;
typedef vector <string> VS;

//input and output
//--------------
#define SPEED() std::ios::sync_with_stdio(false);
#define GL(s) getline(cin, (s))
#define OUT(d) std::cout<<(d)
#define IN(d) std::cin>>(d)
#define OUT_L(d) std::cout<<(d)<<endl
#define EL() printf("\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define YES() printf("YES\n")
#define NO() printf("NO\n")

//repeat
//--------------
#define FOREACH(x, arr) for(auto (x) : (arr))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)

//lower or upper
//--------------
#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)
#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)

//math
//--------------------------------------------
template<typename T>
inline bool BETWEEN(const T aim, const T min, const T max) {
    if (min <= aim && aim <= max) {
        return true;
    } else {
        return false;
    }
}

template<class Type>    bool IsPrime(Type value)
{
    for(Type i=2;i<=value/2;i++)
        if((value%i)==0)
            return 0;
 
    return 1;
}

ll n,k,a[220][220],b,d;
int main() {
	SPEED();
	IN(n);
	IN(k);
	for(int i=1;i<=k;i++)
	{
		cin>>b>>d;
		a[b][d]=2;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==2)
			{
				b=i, d=j;
					for(int p=1;p<=n;p++)
					{
						if(a[b][p]!=2) a[b][p]=1;
						
					}
					for(int p=1;p<=n;p++)
					{
						if(a[p][d]!=2) a[p][d]=1;
					}
			}
		}
	}
	
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]==2)
			{
					b=i;
					for(int p=j;p>=1&&b>=1;p--)
					{
						if(a[b][p]!=2) a[b][p]=1;
						b--;
					}
					b=i;
					for(int p=j;p<=n&&b<=n;p++)
					{
						if(a[b][p]!=2) a[b][p]=1;
						b++;
					}
					
					b=j;
					for(int p=i;p>=1&&b>=1;p--)
					{
						if(a[b][p]!=2) a[b][p]=1;
						b++;
					}
					b=j;
					for(int p=i;p<=n&&b<=n;p++)
					{
						if(a[b][p]!=2) a[b][p]=1;
						b--;
					}
			}
		}
	}
	
	int s=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			s+=a[j][i]==0?1:0;
		}
	}
	cout<<s;
}	

AC Solution:

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;
const int M = 1e6 + 7;
const long long MOD = 1e9 + 7;
const long long INF = 1e18 + 9;
const int SM = 1e3 + 8;
const int logN = 20, BL = 400;
const double EPS = 3e-16;

long long getRow(long long x, long long y){
	return x;
}

long long getColumn(long long x, long long y){
	return y;
}

long long getPrimaryDiagonal(long long x, long long y, long long n){
	return (y - x) + n - 1;
}

long long getSecondaryDiagonal(long long x, long long y, long long n){
	return x + y;
}

int main(){
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	long long n, q; cin >> n >> q;
	
	vector<bool> br(n, true), bc(n, true), bp(2 * n - 1, true), bs(2 * n - 1, true);
	
	while(q--){
		long long x, y; cin >> x >> y;	
		x--, y--;
		long long r = getRow(x, y);
		long long c = getColumn(x, y);
		long long d1 = getPrimaryDiagonal(x, y, n);
		long long d2 = getSecondaryDiagonal(x, y, n);
		br[r] = bc[c] = bp[d1] = bs[d2] = false;	
	}
	
	long long ans = 0;
	for(long long i = 0; i < n; i++){
		if(!br[i]) continue;
		for(long long j = 0; j < n; j++){
			if(!bc[j]) continue;
			long long u = getPrimaryDiagonal(i, j, n);
			long long v = getSecondaryDiagonal(i, j, n);
			if(!bp[u]) continue;
			if(!bs[v]) continue;
			ans++;
		}
	}
	
	cout << ans;
	return 0;
}