585 - Triangles

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:

Post by LTH »

er..i don't know why i get wrong answer..
Does triangles can be counted in other direction ?
i have tested lots of situation but still cant find the fault....
The following is my code(i use Dynamic Programming):

#include <stdio.h>
#include <string.h>
void main()
{
long i,j,k,t,tmp,tmpx,num,cnt=0,sum,n[110][220],s[110][220],max,lb,rb;
char read[300];
while(scanf("%ld",&num)!=EOF)
{
if(num==0)
{
break;
}
for(i=0;i<num;i++)
{
scanf("%s",&read);
for(j=0;j<strlen(read);j++)
{
if(read[j]=='#')
{
n[j]=1;
}
else
{
n[j]=0;
}
}
}
for(i=0;i<num;i++)
{
sum=0;
for(j=0;j<(num-i)*2-1;j++)
{
sum+=n[j];
s[j]=sum;
}
}
max=0;
for(i=0;i<num;i++)
{
for(j=0;j<2*(num-i)-1;j++)
{
rb=-2;
sum=0;
for(k=0;k<num-i;k++)
{
rb+=2;
if(j>=2*(num-i-k)-1||j-rb<0)
{
break;
}
if(j-rb-1>=0)
{
sum=sum+s[i+k][j]-s[i+k][j-rb-1];
}
else
{
sum=sum+s[i+k][j];
}
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
}
}
for(i=0;i<num;i++)
{
sum=0;
for(k=0;k<=i;k++)
{
sum=sum+s[i-k][2*k];
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
for(j=1;j<2*(num-i)-1;j++)
{
sum=0;
for(k=0;k<=i;k++)
{
sum=sum+s[i-k][j+2*k]-s[i-k][j-1];
if(sum!=0)
{
break;
}
if((k+1)*(k+1)>max)
{
max=(k+1)*(k+1);
}
}
}
}
cnt++;
if(cnt>1)
{
printf("n");
}
printf("Triangle #%ldn",cnt);
printf("The largest triangle area is %ld.n",max);
}
}

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Try this input:
5
####-####
b##---##
bb#####
bbb###
bbbb#
0
(b = blank, in the second line three '-')
Output:
Triangle #1
The largest triangle area is 1.
On the first glance this seems to be false.
But look at the picture and you will understand.

<font size=-1>[ This Message was edited by: Adrian Kuegel on 2002-02-08 10:22 ]</font>

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:

Post by LTH »

OH...I finally figure out your meaning...^^
I got Accepted... ^^
thank you very much^^

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

585 ( triangles )

Post by tat tvam asi »

helo !

i tried to solve this ( 585 )
problem , but got wa .
could you tell me the right
( ie. produced by ac - ed prog )
answer for this input :

5
#########
#--#--#
#---#
#-#
#
6
###########
#---#---#
#-----#
#---#
#-#
#
7
#############
#----#----#
#---#---#
#-----#
#---#
#-#
#
0

( sorry for the missing leading spaces )
my "solution" produces :

Triangle #1
The largest triangle area is 4.

Triangle #2
The largest triangle area is 9.

Triangle #3
The largest triangle area is 9.

i found on the web an official
solution written by Matthias Ruhl ,
send it to uva and got ac. but Ruhl's
solution produces :

Triangle #1
The largest triangle area is 1.

Triangle #2
The largest triangle area is 4.

Triangle #3
The largest triangle area is 4.

for the input above .
who has right ?

thanks for advance
tat tvam asi

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

Code: Select all

5
#########
 #---###
  #-###
   ###
    #
The output is NOT 4, but 1. Does your program work for this?

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi »

thanks junjieliang !

i misunderstood the
problem . i took care
of triangles which are
not triangles ...

bye
tat tvam asi

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

585 why sometimes u got Wrong Answer.......

Post by Nick »

Hi everyone
sometimes when you've done exactly what the problem wants.......guess what ....WA.....
This is a funny experience of mine with prob 585
where i've got all test input case correctly outputed

9
#################
###############
#############
###########
#########
#######
#####
###
#
5
#--------
-------
-#---
-#-
-
4
#-#-#--
-----
---
-

5
#########
#---###
#-###
###
#

5
####-####
##---##
#####
###
#


0

Output is
Triangle #1
The largest triangle area is 0

Triangle #2
The largest triangle area is 16

Triangle #3
The largest triangle area is 9

Triangle #4
The largest triangle area is 1

Triangle #5
The largest triangle area is 1
The numbers are all correct.....but WA!!!!
Just because i forgot to put '.' (dot) after each numbers in the output

what i'm saying is that, sometimes people get wreckless or a bit careless.
So...if you got WA all the time doesn't mean that you're wrong..but maybe you're just forgetting something really small.

Hope this can help you guys

rodriwan
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

triangle 4

Post by rodriwan »

isnt the area of triangle for == 4?

5
#########
#---###
#-###
###
#

or is your output right?

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Post by Nick »

yes the output is correct.

if you draw the upside down pyramid, you'll know that the 4 triangle holes will not combine into one large triangle..so the largest would be only 1

any two triangle connected stands in opposite positions

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

585 carelessness makes WA

Post by jackie »

[cpp]const int MAX = 1024;
char triangle[MAX][MAX];[/cpp]

if MAX = 105

you will won't get RE but WA

it's difficult to find such stupid bug

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

My programs solves the inputs from all posts on this problem.
Could anybody post more inputs/outputs or look at my code?
[cpp]#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

vector < string > data;
string s;
long n, ans;

inline bool good(const long &i, const long &j){
return i > -1 && j > -1 && i < (long)data.size() &&
j < (long)data.size() && data[j] == '-';
}

int main(){

// ifstream cin("in.txt");
long t = 1;

while(cin >> n && n && getline(cin, s)){
ans = 0;

data.resize(n);

for(long i = 0; i < n; i++){
getline(cin, data);
data.resize(2*n + 10, ' ');
}

for(long i = 0; i < n; i++)
for(long j = 0; j < 2*n + 10; j++)
if(data[j] == '-'){
ans >?= 1;

if((i + j)%2){
for(long ii = 1; good(ii + i, j - ii); ii++)
for(long jj = j - ii; jj <= j + ii && good(ii + i, jj); jj++)
if(jj == j + ii) ans >?= ii + 1;
}else{
for(long ii = -1; good(ii + i, j + ii); ii--)
for(long jj = j + ii; jj <= j - ii && good(ii + i, jj); jj++)
if(jj == j - ii) ans >?= -ii + 1;
}

}

cout << "Triangle #" << t++ << endl;
cout << "The largest triangle area is " << ans*ans << ".\n\n";

}

return 0;
}[/cpp]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

585 - Triangles

Post by helloneo »

probably i didn't get the problem correctly

#########
#---###
#-###
###
#

i checked some articles here..
but i still don't know why the answer for that case is not 4 but 1..
Last edited by helloneo on Fri Jun 08, 2007 6:04 am, edited 1 time in total.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: 585 Triangles.. WA..

Post by CDiMa »

helloneo wrote:probably i didn't get the problem correctly

#########
#---###
#-###
###
#

i checked some articles here..
but i still don't know why the answer for that case is not 4 but 1..
I'm not experienced in ASCII art but this should show why the answer is 1...

Code: Select all

-------------------
\#/#\#/#\#/#\#/#\#/
 -----------------
  \#/ \ / \#/#\#/
   ------------- 
    \#/ \#/#\#/
     ---------
      \#/#\#/
       -----
        \#/
         -
Ciao!!!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo »

Now I got AC!!
Thank you very much..~

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 585 - Triangles

Post by Ron »

Why im getting WA...Please help me....!!

Code: Select all

got AC


Input :

Code: Select all

1
-
1
#
2
#--
 #
3
-----
 --#
  -
3
-#-#-
 ---
  #
4
###-###
 #---#
  ###
   #
4
---#--#
 #-##-
  #--
   -
4
#-#-#--
 #---#
  ##-
   -
0
My program gives..

Output :

Code: Select all

Triangle #1
The largest triangle area is 1.

Triangle #2
The largest triangle area is 0.

Triangle #3
The largest triangle area is 1.

Triangle #4
The largest triangle area is 4.

Triangle #5
The largest triangle area is 1.

Triangle #6
The largest triangle area is 4.

Triangle #7
The largest triangle area is 1.

Triangle #8
The largest triangle area is 4.





Thnx in advance..!!

Post Reply

Return to “Volume 5 (500-599)”