900 - Brick Wall Patterns

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

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

900 - Brick Wall Patterns

Post by soyoja » 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 

Last edited by soyoja on Wed Dec 06, 2006 2:53 am, edited 2 times in total.
I love Problem Solving!!! :) :) :)

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Dec 06, 2006 2:29 am

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.
Last edited by rio on Fri Dec 15, 2006 7:08 am, edited 1 time in total.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

Post by soyoja » Wed Dec 06, 2006 2:56 am

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. ^^;
I love Problem Solving!!! :) :) :)

rezaee
New poster
Posts: 8
Joined: Sun Dec 10, 2006 8:30 pm

900 help me plz

Post by rezaee » 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;}
Last edited by brianfry713 on Mon Nov 24, 2014 10:52 pm, edited 1 time in total.
Reason: Added code blocks

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » Fri Dec 15, 2006 2:01 am

rio wrote:

Code: Select all

   remove after soyoja's AC. 
could anyone explain me, why this work ?
Last edited by mogers on Fri Dec 15, 2006 12:48 pm, edited 1 time in total.
Miguel Oliveira

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » 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.

mogers
New poster
Posts: 29
Joined: Tue May 30, 2006 5:09 pm
Location: Porto, Portugal

Post by mogers » 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 :oops:
Miguel Oliveira

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

Post by helloneo » 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 :oops:
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 ***

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Sat Jul 21, 2007 1:00 pm

Code: Select all


  ACCEPTED

Last edited by newton on Sat Jul 21, 2007 2:28 pm, edited 1 time in total.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sat Jul 21, 2007 1:38 pm

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.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » 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??



thanx in advanced

gaucho.andre
New poster
Posts: 3
Joined: Fri Aug 31, 2007 8:33 am

Post by gaucho.andre » 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[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
Last edited by brianfry713 on Mon Nov 24, 2014 10:53 pm, edited 2 times in total.
Reason: Added code blocks

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Wed Oct 10, 2007 9:50 pm

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

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 900 - Brick Wall Patterns

Post by stcheung » Sun Sep 14, 2008 9:18 am

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

Post Reply

Return to “Volume 9 (900-999)”