Page 1 of 2

### 900 - Brick Wall Patterns

Posted: Wed Dec 06, 2006 2:11 am
It's a very easy problem. However, I received TLE from judge.
I don't know why my solution received TLE. It works well my VC++ and
g++ compiler.

Anyone tell me why my solution received TLE. Thx.

Code: Select all

``````
Remove my accepted code

``````

Posted: Wed Dec 06, 2006 2:29 am

Code: Select all

``````  remove after soyoja's AC.
``````
I think fib = fib + fib couse an overflow and overwriting the value of a.

And I think it would be better if you edit the title like "900 - Brick Wall Patterns".
----
Sory for my poor English.

Posted: Wed Dec 06, 2006 2:56 am
Thx, Rio.

I changed the type of "int a" to "long long a", then I accepted.
Maybe my loop statement caused an overflow, and it makes infinite loop.
Thx!

ps ) I changed this thread title. ^^;

### 900 help me plz

Posted: Wed Dec 13, 2006 5:46 pm

Code: Select all

``````#include <iostream.h>

int fact(int n)
{int p;
p=1;
if(n==0)return 1;
else{
while(n!=0)
{p*=n;n--;}

return p;}}

int max(int i,int j)
{if(i>j)return i;
else return j;
}

int combination(int j,int n)
{int p,k;
p=1;
if(n==j) return 1;
else{
k=n;
while(k!=j)
{p*=k;k--;}
return p/fact(n-j);}
}

int main(void)
{int n;
int unsigned long s;
while(cin>>n){
if(n==0)return 0;
else{
s=0;
for(int i=0;i<=n/2;i++)
for(int j=0;j<=n;j++)
if(2*i+j==n){s+=combination(max(i,j),i+j);}

cout<<s<<endl;}}

return 0;}``````

Posted: Wed Dec 13, 2006 7:42 pm
Try the cases...

Input:

Code: Select all

``````39
40
0``````
Output:

Code: Select all

``````102334155
165580141``````
Hope these help.

Posted: Fri Dec 15, 2006 2:01 am
rio wrote:

Code: Select all

``````   remove after soyoja's AC.
``````
could anyone explain me, why this work ?

Posted: Fri Dec 15, 2006 7:14 am
Oops. I forgot removing the code after soyoja's AC.

to Mogers:
Its a kind of DP solution.

Posted: Fri Dec 15, 2006 12:51 pm
rio wrote: to Mogers:
Its a kind of DP solution.
I just don't understand why we can count the number of patterns this way.
maybe i'm missing something Posted: Fri Dec 15, 2006 1:27 pm
mogers wrote: I just don't understand why we can count the number of patterns this way.
maybe i'm missing something Just try to draw several steps on your paper .. then you can find the patterns..

If you have n bricks, all the patterns you can make are from *** or ***

Posted: Sat Jul 21, 2007 1:00 pm

Code: Select all

``````
ACCEPTED

``````

Posted: Sat Jul 21, 2007 1:38 pm
In the function str_add, you are allocating res on the stack, which is then returned by the function. This array will be overwritten with garbage when other functions are called. This is likely the cause for run-time error. If your program did work, you would get Memory limit exceeded because the fibo array is 36 MB, while the general memory limit is 32 MB.

In addition, your solution for 900 is more complex than needed. There's no need to use bigint on this problem.

Posted: Sat Jul 21, 2007 2:24 pm
i got ACCEPTED both of the problem. now my question??

1. if fibo[m][n];
what should be the value of m and n for minimum memory
in the both problem??

Posted: Fri Aug 31, 2007 8:45 am
Hi,

I'm new at UVA Online Judge system and i'm having a few troubles. I'm programing in JAVA and my program consists in an algorythim similar to this:

"

Code: Select all

``````public static void main(String[] args)
{
while (true)
{
// something to read the number and stock it in the variable "N"

if(N == 0)break;
System.out.println(solve(N));
}
}
static long solve(int N)
{
if(N == 1)return 1;
if(N == 2)return 2;
if(N == 3)return 3;

long[] fib = new long[N];
fib = 1; fib = 2; fib = 3;
for(short i = 3; i < N; i++) fib[i] = fib[i-1] + fib[i-2];

return fib[N-1];
}
}``````
"

>>>My first problem was that i didn't really understand how do you do to read information from the input in this kind o problems. So I've copied the method ReadLn() from the sample solution of problem 100. Then my program was like this:

Code: Select all

``````import java.io.*;
import java.util.*;

class teste2
{
static String ReadLn (int maxLg)  // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
// String line = "";

try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);  // eof
return (new String (lin, 0, lg));
}

public static void main(String args[])
{

while (true)
{
StringTokenizer st = new StringTokenizer(input);
int N = Integer.parseInt(st.nextToken());

if(N == 0)break;
System.out.println(solve(N));

}
}

static long solve(int N)
{
if(N == 1)return 1;
if(N == 2)return 2;
if(N == 3)return 3;

int[] fib = new int[N];
fib = 1; fib = 2; fib = 3;
for(short i = 3; i < N; i++) fib[i] = fib[i-1] + fib[i-2];

return fib[N-1];
}
}``````
>>>Then I've received the following message:

Dear gaucho.andre:

The compiler couldn't compile your ANSI C/C++ or GNU Pascal/Java program.

[Notes: - Select C, C++, JAVA or PASCAL in the @JUDGE_ID field, to ensure that
I'll use the proper compiler. Place a 'program...' sentence in Pascal.
Note that entry point in Java is a 'main' function in a 'Main' class.
- Do not use more than 1024 characters per line, or 40,000 bytes per
program, if you are submitting your programs by E-Mail.
- Do not use '//' comments except in C++ programs [And Note that this
is not Borland C or Turbo Pascal!].
- Some mail tools reformat your text or the standard mail headers.
I compiled the lines I resent you in the "Program Received" message.
a "@end_of_source_code" string after the last source code line).

Here are the compiler error messages:

/tmp/ccY7Ehzvmain.i(.text+0x12): undefined reference to `_CL_4Main'
collect2: ld returned 1 exit status

Thanks,
gaucho.andre

Posted: Wed Oct 10, 2007 9:50 pm
Try the new server.