10593 - Kites

[Zhou Yiyan@SHU]

Would O(n^3) be enough to solve this problem?
I couldn't make out a more effective way...

[Azim]

Hi all,

I really got nervous about this problem! It's not deficult! I tested for all inputs on board, but still WA. There shouldn't be any special traps, or sth...
Please, HELP

My code:

Code: Select all

const
     max = 500;

type
    cat = record
    k,r:boolean;
    end;

var
a,i,j,n,wyn:longint;
t:array[1..max,1..max]of cat;
h:char;
q:boolean;

begin

while not eof do
      begin
      readln(n); wyn:=0;

      for i:=1 to n do
          begin
          j:=0;
          for j:=1 to n do
              begin
              read(h);
              if h='.' then
                 begin
                 t[i,j].k:=false;
                 t[i,j].r:=false;
                 end else
                 begin
                 t[i,j].k:=true;
                 t[i,j].r:=true;
                 end;
              end;
          readln;          end;

      a:=0; q:=false;
      while q=false do
      begin
      a:=a+1; q:=true;

      for i:=1 to (n-a+1) do
      for j:=1 to (n-a+1) do
      if (i<n) and (j+a<=n) and ((t[i,j].k=true) or (t[i,j].r=true)) then
      begin

      if (i+a<=n) and (t[i,j].k=true) then
         begin
         if (t[i,j+1].k=true) and (t[i+1,j].k=true) and (t[i+1,j+1].k=true) then
         begin q:=false; inc(wyn); end else if t[i,j].k=true then t[i,j].k:=false;
         end else if t[i,j].k=true then t[i,j].k:=false;

      if (1<j) and (i+a< n) and (t[i,j].r=true) then
         begin
         if (t[i+1,j-1].r=true) and (t[i+1,j].r=true) and (t[i+1,j+1].r=true) and (t[i+2,j].r=true) then
         begin q:=false; inc(wyn); end else if t[i,j].r=true then t[i,j].r:=false;
         end else if (i<>1) and (j<>1) and (t[i,j].r=true) then t[i,j].r:=false;

      end;

      end;

      writeln(wyn);
      end;

end.

Thx,
Azim

[nicu_ivan]

Hi all,

I really got nervous about this problem! It's not deficult! I tested for all inputs on board, but still WA. There shouldn't be any special traps, or sth...
Please, HELP

My code:

Code: Select all

const
     max = 500;

type
    cat = record
    k,r:boolean;
    end;

var
a,i,j,n,wyn:longint;
t:array[1..max,1..max]of cat;
h:char;
q:boolean;

begin

while not eof do
      begin
      readln(n); wyn:=0;

      for i:=1 to n do
          begin
          j:=0;
          for j:=1 to n do
              begin
              read(h);
              if h='.' then
                 begin
                 t[i,j].k:=false;
                 t[i,j].r:=false;
                 end else
                 begin
                 t[i,j].k:=true;
                 t[i,j].r:=true;
                 end;
              end;
          readln;          end;

      a:=0; q:=false;
      while q=false do
      begin
      a:=a+1; q:=true;

      for i:=1 to (n-a+1) do
      for j:=1 to (n-a+1) do
      if (i<n) and (j+a<=n) and ((t[i,j].k=true) or (t[i,j].r=true)) then
      begin

      if (i+a<=n) and (t[i,j].k=true) then
         begin
         if (t[i,j+1].k=true) and (t[i+1,j].k=true) and (t[i+1,j+1].k=true) then
         begin q:=false; inc(wyn); end else if t[i,j].k=true then t[i,j].k:=false;
         end else if t[i,j].k=true then t[i,j].k:=false;

      if (1<j) and (i+a< n) and (t[i,j].r=true) then
         begin
         if (t[i+1,j-1].r=true) and (t[i+1,j].r=true) and (t[i+1,j+1].r=true) and (t[i+2,j].r=true) then
         begin q:=false; inc(wyn); end else if t[i,j].r=true then t[i,j].r:=false;
         end else if (i<>1) and (j<>1) and (t[i,j].r=true) then t[i,j].r:=false;

      end;

      end;

      writeln(wyn);
      end;

end.

Thx,
Azim

It seams fine to me. Try to think at some critical test cases. For example 0 or anything else, that can be critical.

[yure]

I keep getting TLE and dont really understand what I do wrong, if anyone can help it would be great.

Code: Select all

#include <iostream>
#include <vector>
using namespace std;
bool square(vector<vector<bool> >& V, int i, int j, int size){
	for(int i1=0; i1<size; ++i1)
		for(int j1=0; j1<size; ++j1)
			if (not V[i+i1][j+j1]) return false;
	return true;
}
bool diamond(vector<vector<bool> >& V, int i, int j, int size){
	int amplada=0;
	for (int i1=0; i1<size; ++i1){
		for (int j1=0; j1<=amplada; ++j1)
			if (not (V[i+i1][j+j1] and V[i+i1][j-j1])){
				return false;
			}
		if (i1<size/2) ++amplada;
		else --amplada;
	}
	return true;
}
void build_squares(vector<vector<bool> >&V, int i, int j, int& ways){
	int size=2;
	while(square(V, i, j, size)){
		++ways;
		++size;
	}
}
void build_diamonds(vector<vector<bool> >&V, int i, int j, int& ways){
	int size=3;
	while(diamond(V, i, j, size)){
		++ways;
		size+=2;
	}
}

int main(){
	int n;
	while (cin >> n){
		vector<vector<bool> > v(n+2, vector<bool> (n+2, false));
		for (int i=1; i<=n; ++i)
			for (int j=1; j<=n; ++ j){
					char s; cin >> s;
					if (s=='x') v[i][j]=true;
					else v[i][j]=false;
				}
		int ways=0;
		for (int i=1; i<v.size()-1; ++i)
			for (int j=1; j<v[i].size()-1; ++j){
				build_squares(v, i, j, ways);
				build_diamonds(v, i, j, ways);
			}
		cout << ways << endl;
	}
	
}