Областная олимпиада по информатике, 2010 год

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

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

#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;
}