10465 - Homer Simpson

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

Moderator: Board moderators

plankton97330
New poster
Posts: 3
Joined: Mon May 22, 2006 10:29 am

Post by plankton97330 » Wed Aug 16, 2006 9:15 am

try
4 8 17
8 4 17

both output 4 1

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Fri Sep 08, 2006 2:02 pm

sklitzz!
I wasnt here for a long time, so sorry for make you waiting for months!
Okay.. I am not sure whether you have thought about these line...
It is preferable that Homer drinks as little beer as possible.
so after your dp part, all you have to do, is to check whether best[t] is possible. if its not possible, then you have to t-- and for the first one that is possible you just have to print and get out!

Like I just changed your last two parts of your codes and wrote this lines and your program successfully got ac!

Code: Select all

      if(best[t]) cout<<best[t]<<endl;
      else for(int i =t-1; i>=0; i--) {
            if(best[i]) {
                cout<<best[i]<<" "<<t-i<<endl;
                break;
            }else if(i==0) cout<<0<<" "<<t<<endl;
      }
fahim
#include <smile.h>

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

Post by sklitzz » Fri Sep 08, 2006 4:41 pm

Thank you very very much!

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Wed Sep 13, 2006 3:45 pm

Hi,
I am using DP for this problem. I fill all the slots with multiples of m first, then with n and if it is already filled i check which is max.

I have checked all input on the forum but mine still gives WA. Can someone help me with test inputs where it fails.

Code: Select all

#include<stdio.h>
#define MAX 10001
int arr[MAX];
int set[MAX];
#define mymax(a,b) ((a>b)?(a):(b))
int
main ()
{
  int m, n, t, tmax, i, diff;
  while (scanf (" %d %d %d", &m, &n, &t) != EOF)
    {
      memset (arr, 0, MAX);
      memset (set, 0, MAX);
      arr[0] = 0;
      set[0] = 1;
      for (i = 0; i <= t; i++)
	{
	  if (set[i] == 1)
	    {
	      if (i + m <= t)
		{
		  arr[i + m] = mymax (arr[i] + 1, arr[i + m]);
		  set[i + m] = 1;
		}
	    }
	}

      for (i = 0; i <= t; i++)
	{
	  if (set[i] == 1)
	    {
	      if (i + n <= t)
		{
		  arr[i + n] = mymax (arr[i + n], arr[i] + 1);
		  set[i + n] = 1;
		}
	    }
	}

      if (arr[t] != 0)
	{
	  printf ("%d\n", arr[t]);
	  continue;
	}

      tmax = 0;
      for (i = t - 1; i > 0; i--)
	{
	  if (arr[i] !=0)
		break;
	}

      printf ("%d %d\n", arr[i], t - i);



    }
  return 0;
}


Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Sep 14, 2006 7:12 am

What does that memset thingy do? Sets MAX bytes to 0? Is int one byte long?

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Thu Sep 14, 2006 12:43 pm

thanks darko that accepts it , memset was the culprit.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Mon Mar 24, 2008 9:30 am

Is this output correct?

Input

Code: Select all

88 2 5038
34 31 3509
79 10 8419
37 33 2175
64 6 8227
54 35 7026
94 8 4689
Output

Code: Select all

113
835
63
1371 1
185
Thanks.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 10465 - Homer Simpson

Post by Ron » Mon May 19, 2008 4:05 pm

Input :

Code: Select all

88 2 5038
34 31 3509
79 10 8419
37 33 2175
64 6 8227
54 35 7026
94 8 4689
My AC prog gives...

Output :

Code: Select all

2519
113
835
63
1371 1
185
586 1
!!..*S K Meena*..!!

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Re: 10465 - Homer Simpson

Post by viniciusweb » Mon Aug 18, 2008 12:05 am

What's the correct output for the following cases? Thanks.

Code: Select all

17 18 99
435 159 4568
1 1 1
10 87 555
34 657 189
999 99 6544
10 100 1000
1000 10 1
54 65 98
6 4 21
3 7 1000
103 103 465
485 173 6548
6465 555 1551
34 7878 8484
321 456 9877

christephan
New poster
Posts: 5
Joined: Fri Jan 25, 2008 9:27 pm

Re: 10465 - Homer Simpson

Post by christephan » Mon Aug 25, 2008 11:47 am

For this input

Code: Select all

17 18 99
435 159 4568
1 1 1
10 87 555
34 657 189
999 99 6544
10 100 1000
1000 10 1
54 65 98
6 4 21
3 7 1000
103 103 465
485 173 6548
6465 555 1551
34 7878 8484
321 456 9877
My AC output:

Code: Select all

5 9
20 8
1
17
5 19
57 1
100
0 1
1 33
5 1
332
4 53
18 2
2 441
249 18
24 13

dallen
New poster
Posts: 7
Joined: Mon Apr 22, 2013 1:06 am
Location: Asunción, Paraguay

10465 - Homer Simpson

Post by dallen » Mon May 27, 2013 12:39 am

I'm getting WA and still couldn't find a test case in which my code fails, can someone point out some tricky cases to test. Here's my code is anyone is interested.

Code: Select all

//import java.io.File;
//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.Scanner;

class Main {

	private static int m, n, t;
	private static int[][] memo = new int[10000][2];

	public static void main(String[] args) /*throws FileNotFoundException*/ {
		//System.setIn(new FileInputStream(new File("test.txt")));

		Scanner sc = new Scanner(System.in);
		StringBuilder output = new StringBuilder();

		while (sc.hasNextInt()) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			t = sc.nextInt();
			
			m = Math.min(a, b);
			n = Math.max(a, b);
			
//			if (m == 0 || n == 0) {
//				output.append(t + "\n");
//				continue;
//			}
			
			maxBurgers(t);
			
			output.append(memo[t][0] + memo[t][1]);
			
			if (t - (m * memo[t][0] + n * memo[t][1]) > 0) {
				output.append(" " + (t - (m * memo[t][0] + n * memo[t][1])));
			}
			
			output.append("\n");
		}

		output.deleteCharAt(output.length() - 1);
		System.out.println(output.toString());
	}

	private static void maxBurgers(int number) {
		for (int i = m; i <= number; i++) {
			if (i % m == i % n) {
				int a = memo[i - m][0] + memo[i - m][1];
				int b = memo[i - n][0] + memo[i - n][1];

				if (a > b) {
					memo[i][0] = memo[i - m][0] + 1;
					memo[i][1] = memo[i - m][1];
				} else {
					memo[i][0] = memo[i - n][0];
					memo[i][1] = memo[i - n][1] + 1;
				}
			} else if (i % m < i % n) {
				memo[i][0] = memo[i - m][0] + 1;
				memo[i][1] = memo[i - m][1];
			} else {
				memo[i][0] = memo[i - n][0];
				memo[i][1] = memo[i - n][1] + 1;
			}
		}
	}

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10465 - Homer Simpson

Post by brianfry713 » Thu May 30, 2013 12:27 am

Check input and AC output for thousands of problems on uDebug!

Snakib
New poster
Posts: 7
Joined: Mon May 31, 2010 6:25 am

Re: 10465 - Homer Simpson

Post by Snakib » Tue Jun 11, 2013 11:04 pm

what is submission error
it's making me mad :evil:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10465 - Homer Simpson

Post by brianfry713 » Tue Jun 11, 2013 11:49 pm

Try a different problem.
Check input and AC output for thousands of problems on uDebug!

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

Re: 10465 - Homer Simpson

Post by afruizc » Fri Jul 05, 2013 10:33 pm

Sample input

All the ones that are getting WA; here is some sample I/O.

Code: Select all

6102 7869 9130
8146 3101 8746
9491 5930 9701
3450 7301 9451
4444 7247 8779
6001 8117 9411
6809 7336 7365
8614 8505 9119
351 7226 8020
2903 7008 9534
6223 101 8849
2603 7592 9602
62 9083 9553
263 427 7383
59 9468 9522
8727 989 9144
2296 3900 8174
2886 1293 9732
4655 9249 9963
8140 4594 9873
9688 9658 9984
5515 9350 9996
7647 4801 7869
337 4129 6758
9449 6451 9628
8340 2019 9339
9222 6442 9281
193 886 9218
4561 3541 5772
8867 8309 8947
6752 1196 9147
9907 8701 9948
5816 7971 9281
7012 8923 9859
4479 9777 9829
1859 947 2748
1707 8388 8677
507 219 7034
6987 382 9998
5444 2529 8681
7978 6080 8869
5950 3822 6226
6547 2254 8348
5923 489 6653
4909 4249 7224
7866 2669 8897
2002 3704 6648
524 395 9788
4600 2855 9911
7886 5909 9688
3623 5912 9709
8861 3162 9144
8626 350 9217
8152 657 8295
5249 3859 8682
8048 9754 9803
1055 5671 9016
565 3659 9711
8492 3454 9348
2484 7430 9894
9231 1471 9235
3481 8414 8569
5837 5295 6947
2857 2447 6042
7818 9746 9796
5243 4811 8405
7318 9955 9989
8645 8591 8750
1405 6131 6794
7299 647 7393
8582 4627 9019
1317 4662 7221
6570 1555 6677
3234 327 6856
6571 3684 7704
1283 5680 5806
7890 7006 8989
6632 212 7906
9577 9009 9967
5870 6710 8345
4798 8068 8802
1062 1371 4859
278 6416 8852
2696 5617 5912
5840 4522 8731
3940 1900 5597
5265 5851 9899
3008 4323 7067
613 324 7087
3245 1701 3680
4957 2920 8098
6778 4543 9019
6829 3594 9276
5944 3040 8054
9428 4802 9501
1786 8194 8769
7434 3502 8313
3549 5225 6932
8490 9844 9875
4229 7299 7465
Output

Code: Select all

1 1261
1 600
1 210
1 2150
1 1532
1 1294
1 29
1 505
3 92
3 825
27
3 1793
154 5
28 19
161 23
9 243
2 374
5 81
2 653
2 685
1 296
1 646
1 222
20 18
1 179
1 999
1 59
19 7
1 1211
1 80
3 3
1 41
1 1310
1 936
1 52
2 854
5 142
15 5
26 66
2 708
1 891
1 276
3 1586
2 241
1 2315
3 890
3 642
24 50
2 711
1 1802
2 174
1 283
26 117
1 143
2 964
1 49
4 180
17 106
1 856
3 2442
1 4
1 155
1 1110
2 328
1 50
1 3162
1 34
1 105
1 663
1 94
1 437
5 636
1 107
12 25
2 336
1 126
1 1099
7 2
1 390
1 1635
1 734
4 302
9 212
1 295
1 2891
1 1657
1 4048
2 1051
12 20
2 278
2 221
1 2241
2 2088
2 1974
1 73
1 575
1 879
1 1707
1 31
1 166

Post Reply

Return to “Volume 104 (10400-10499)”