10465 - Homer Simpson

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

try
4 8 17
8 4 17

both output 4 1

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

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

Thank you very very much!

temper_3243 · 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 · 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 · Post by **temper_3243** » Thu Sep 14, 2006 12:43 pm

thanks darko that accepts it , memset was the culprit.

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

Is this output correct?

Input

Code: Select all

Output

Code: Select all

Thanks.

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

Input :

Code: Select all

My AC prog gives...

Output :

Code: Select all

!!..*S K Meena*..!!

viniciusweb · 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 · 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

dallen · 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 · Post by **brianfry713** » Thu May 30, 2013 12:27 am

http://acm.uva.es/board/viewtopic.php?t=11081

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

what is submission error
it's making me mad

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

Try a different problem.

afruizc · 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

OJ Board

10465 - Homer Simpson

Re: 10465 - Homer Simpson

Re: 10465 - Homer Simpson

Re: 10465 - Homer Simpson

10465 - Homer Simpson

Re: 10465 - Homer Simpson

Re: 10465 - Homer Simpson

Re: 10465 - Homer Simpson

Re: 10465 - Homer Simpson