10819 - Trouble of 13-Dots

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

Moderator: Board moderators

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Wed Mar 02, 2005 8:04 am

There is no need for any sorting.
Use dynamic programming, optimizing with respect to favor index.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Tue Mar 15, 2005 9:59 am

Hi!

I've just got 10819 AC.. :wink:


Try with this small test
0 0
your program should produce
0
Remember Never Give Up
Regrads
Miras

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Jul 28, 2005 3:33 am

A quote from Adrian Kuegel:
1900 3
2000 5
1950 1
101 1

output:
2
Strange, my program's output is 1 and it was accepted. :o

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Tue May 09, 2006 2:35 pm

why I got wrong answer all the time
could somebody tell me what's wrong with my code??

Code: Select all

removed, accept ^^

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Jul 22, 2006 12:11 pm

Hey whats the problem with my code ?
i used 0-1 knapsack with a bubble sort. I passed all the tricky tests here but I am getting TLE in judge's robot.

Code: Select all

edited..
can anyone help me with suggestions or pointing out where i am wrong ?
Last edited by Kallol on Fri Dec 14, 2007 8:20 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
rube
New poster
Posts: 18
Joined: Thu Oct 28, 2004 10:13 am

10819 - Trouble of 13-Dots!!!

Post by rube » Thu Aug 03, 2006 5:43 pm

I cann't figure out how to solve it. I m getting WA all the time! Plz help me.
here is my code:

Code: Select all

#include <stdio.h>
#include <algorithm>
using namespace std;
struct MoneyPoint{
       int m,p;
};
int const max_v = 10001;
MoneyPoint mp[max_v];
int grid[101][max_v];
int max_f(int a,int b){
       return a>b?a:b;
}
int knapsack01(int N,int L){
       int i,j,tL;
       for(i=0;i<=N;i++){
               grid[i][0]=0;
       }
       tL=L;
       if(L+200>2000)L+=200;
       for(i=1;i<=N;i++){
               for(j=1;j<=L;j++){
                       if(j==1 && j<mp[i].m)
                               grid[i][j]=0;
              //problem may be in this part [][][][][][][]
                       else if(j==1 && j<=tL || j>2000)
                               grid[i][j]=mp[i].p;
                       else if(j<mp[i].m)
                               grid[i][j]=grid[i-1][j];
                       else{
                               grid[i][j]=max_f(grid[i-1][j],(j<=tL||j>2000)?mp[i].p+grid[i-1][j-mp[i].m]:grid[i-1][j]);
//[][][][][][][]
                       }
               }
       }
       return grid[N][L];
}
bool comp(MoneyPoint a,MoneyPoint b){
       if(a.m<b.m)return true;
       if(a.m==b.m && a.p>b.p)return true;
       return false;
}
int main(){
       int n,m,i;
       while(scanf("%d%d",&m,&n)==2){
               for(i=1;i<=n;i++){
                       scanf("%d%d",&mp[i].m,&mp[i].p);
               }
               sort(mp+1,mp+n+1,comp);
               printf("%d\n",knapsack01(n,m));
       }
       return 0;
}
Never argue with an idiot, they'll drag you down to their level and beat you with experience! (unknown)

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10819 - Trouble of 13-Dots!!!

Post by Martin Macko » Sat Aug 05, 2006 3:11 am

rube wrote:I cann't figure out how to solve it. I m getting WA all the time! Plz help me.
Your solution's not working for:

Code: Select all

8762 2
2458 4
308 1
My AC's output:

Code: Select all

5

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10819 - Trouble of 13-Dots!!!

Post by Martin Macko » Sat Aug 05, 2006 3:12 am

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=7536 and http://online-judge.uva.es/board/viewtopic.php?t=7646)

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Mon Aug 14, 2006 9:40 pm

please check my I/O:

Code: Select all

1800 3
1950 1
2000 5
101 1

1801 3
2000 5
1955 1
101 1

1890 3
1955 1
2000 5
101 1
 
5000 4
1000 2
1000 2
1000 3
3200 5

0 0

1 1
1 1

5 5
1 9
2 9
3 9
1 9
2 9
Output:

Code: Select all

1
1
2
10
0
1
27
Is it correct?

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Tue Aug 15, 2006 2:19 am

Hi,

My AC code outputs:

Code: Select all

1
1
1
10
0
1
27
Although I'm not sure if they are totally right.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 15, 2006 10:41 am

daveon wrote:Hi,

My AC code outputs:

Code: Select all

1
1
1
...
Although I'm not sure if they are totally right.
The correct answer is:

Code: Select all

1
1
2
10
0
1
27
As
problem description wrote:It is important to know that 13-Dots always uses her credit card to pay the bill, which offers her a 200-dollar refund if her total expense in the month exceeds $2000.
Buying the first item for $1955 and the third one for $101 makes her bill $2056. Therefore she can apply the $200 refund and pay only $1856.

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Tue Aug 15, 2006 11:29 am

Code: Select all

removed
Last edited by DP on Tue Aug 15, 2006 11:57 am, edited 1 time in total.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 15, 2006 11:53 am

DP wrote:What is the problem here?? Please tell me.
Here is my code:
Your code isn't working for:

Code: Select all

3123 2
3212 5
150 2
6733 6
969 3
2195 3
1565 2
233 5
1707 5
1702 3
3948 7
2151 4
3117 2
748 5
1463 5
1405 4
1204 5
3778 3
2957 4
362 5
1852 3
2979 2
323 3
7268 10
2846 4
2423 5
3585 5
678 1
3190 2
2078 1
3611 4
1340 2
801 1
2870 3
5890 9
1707 4
2140 2
2820 3
601 4
1195 5
1242 3
217 2
894 1
3879 2
1382 1
1791 1
565 0
3184 9
599 5
3359 1
2604 2
499 1
2103 5
261 5
3201 5
3204 5
1423 2
4678 10
1019 2
3103 1
3102 2
2675 3
23 5
3831 1
2199 1
2420 5
607 4
2249 5
My AC's output:

Code: Select all

5
19
15
11
12
19
0
0
15
16

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Tue Aug 15, 2006 11:56 am

Martin,
Thnx you are a great helper. :)

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Thu Aug 17, 2006 2:12 am

Martin Macko wrote: The correct answer is:

Code: Select all

1
1
2
10
0
1
27
I agree, so therefore, this problem needs a rejudge as my solution should not get accepted.

Post Reply

Return to “Volume 108 (10800-10899)”