900 - Brick Wall Patterns

[soyoja]

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 

[rio]

Code: Select all

  remove after soyoja's AC.

I think fib[50] = fib[49] + fib[48] 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.

[soyoja]

Thx, Rio.

I agree with your opinion.
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. ^^;

[rezaee]

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

[Jan]

Try the cases...

Input:

Code: Select all

39
40
0

Output:

Code: Select all

102334155
165580141

Hope these help.

[mogers]

Code: Select all

   remove after soyoja's AC. 

could anyone explain me, why this work ?

[rio]

Oops. I forgot removing the code after soyoja's AC.

to Mogers:
Its a kind of DP solution.

[mogers]

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

[helloneo]

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

[newton]

Code: Select all

  ACCEPTED

[stubbscroll]

In the function str_add, you are allocating res[10000] 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.

[newton]

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



thanx in advanced

[gaucho.andre]

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[0] = 1; fib[1] = 2; fib[2] = 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)
           {
               car = System.in.read();
               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)
       {
               String input = ReadLn (255);
               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[0] = 1; fib[1] = 2; fib[2] = 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.
(if your mail system adds extra lines to your letter, please include
a "@end_of_source_code" string after the last source code line).

Here are the compiler error messages:

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

>>>Could you please help me and tell me what's wrong about this code for solving the problem? And how do i read thing from the input since i can't use the Scanner clas. I would thanks if you answer to my e-mail (gaucho.andre@gmail.com).

Thanks,
gaucho.andre

[baodog]

Try the new server.
Now your Java should work!!!
It supports 1.6 now.

[stcheung]

The following webpage explains clearly why the fibonacci series is relevant to this problem. Basically if you consider the left end of a brick pattern for length N, you either have a single standing brick or two sideway bricks. Consider how many patterns you can form with each case and then add them up. The first case is equivalent to #patterns for N-1 while the second case is same as #patterns for N-2. So you end up with the fib sequence.

http://www.mcs.surrey.ac.uk/Personal/R. ... PLAIN.html