10721 - Bar Codes
Moderator: Board moderators
- Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
10721 - TLE
I have TLE for this problem, because I use a Formula to calculate recursively the final number for this problem. How can I quit TLE?
I have TLE
My problem persist. I don't know how to reduce time.
This is my code for this problem
This is my code for this problem
Code: Select all
#include <stdio.h>
#include <stdlib.h>
long contador;
void Formula(int tot,int sep,int max){
int i;
if (tot<sep) return;
else if ((tot<=max)&&(sep==1)) { contador++; return;}
else if (sep==1) return;
for(i=1;i<=max;i++) Formula(tot-i,sep-1,max);
}
int main (int car, char** v) {
char linea[100];
int total,separaciones,maximo;
while(fgets(linea,100,stdin)!=NULL){
sscanf(linea,"%d %d %d",&total,&separaciones,&maximo);
contador=0;
Formula(total,separaciones,maximo);
printf("%ld\n",contador);
}
return 1;
}
You misunderstand what I mean. You should store the value in a 3D-table like:
This is a standard technique called dynamic programming. If you are computer science major, you will learn it in some intermediate/advanced algorithm course.
Code: Select all
int table[50][50][50];
int Formula(int tot,int sep,int max){
if(table[tot][sep][max]==-1)
{
// compute the value of Formula(int tot,int sep,int max)
// recursively here and assign it to table[tot][sep][max]
}
return table[tot][sep][max];
}
int main (int car, char** v) {
char linea[100];
int total,separaciones,maximo;
initialize all entries of the table to be -1;
while(fgets(linea,100,stdin)!=NULL) {
sscanf(linea,"%d %d %d",&total,&separaciones,&maximo);
printf("%ld\n", Formula(total,separaciones,maximo));
}
return 1;
}
Hello.
This problem also can be solved using 2D matrix or just can be found a formula using PIE.
Eduard.
This problem also can be solved using 2D matrix or just can be found a formula using PIE.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
I have used 3D memo .. I am getting WA ..
can u give me some I/O where my code fails ..?? Thanks in advance ...
can u give me some I/O where my code fails ..?? Thanks in advance ...
Code: Select all
removed after AC..
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh
CSE,BUET
Bangladesh
-
- New poster
- Posts: 9
- Joined: Mon Jul 07, 2014 3:37 pm
- Contact:
Re: 10721 - Bar Codes
Hints:
-------
Complete search over all bar widths, in each recursive call you should try to add a bar with all allowed width.
Recursively do that until all your bars width = n and number of bars = k Here you found a solution.
You can use a 2D array to store answers. in order not to re-calculate any of them (DP).
-------
Complete search over all bar widths, in each recursive call you should try to add a bar with all allowed width.
Recursively do that until all your bars width = n and number of bars = k Here you found a solution.
You can use a 2D array to store answers. in order not to re-calculate any of them (DP).
Abdelrahman Ali (MaTrix)
Re: 10721 - Bar Codes
got ac on 1st submission
actually 2D array is enough . as 'm' is not changing so we don't need 'm' as dp state
