## 10593 - Kites

Moderator: Board moderators

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China
Would O(n^3) be enough to solve this problem?
I couldn't make out a more effective way...

Azim
New poster
Posts: 2
Joined: Fri Mar 18, 2005 12:05 am
Location: PL

### 10593 HELP!!

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...

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

for i:=1 to n do
begin
j:=0;
for j:=1 to n do
begin
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;

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
New poster
Posts: 7
Joined: Wed Mar 16, 2005 7:27 pm

### Re: 10593 HELP!!

Azim wrote: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...

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

for i:=1 to n do
begin
j:=0;
for j:=1 to n do
begin
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;

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
New poster
Posts: 1
Joined: Sun Jul 29, 2007 4:56 pm
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){
for (int i1=0; i1<size; ++i1){
if (not (V[i+i1][j+j1] and V[i+i1][j-j1])){
return false;
}
}
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;
}

}

``````