855 - Lunch in Grid City

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

Moderator: Board moderators

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 855 - Lunch in Grid City

Post by newkid »

actually for that case (1,1) (2,2) and (3,3) all of them are optimal. in those case print the one that comes first.
hmm..

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 855 - Lunch in Grid City

Post by abid_iut »

Still I am getting WA
what is the problem?
code:

Code: Select all

Removed

Last edited by abid_iut on Sat Dec 20, 2008 12:02 pm, edited 1 time in total.
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 855 - Lunch in Grid City

Post by mf »

You still didn't fix the problem I told you about. This part is wrong, guess why.
abid_iut wrote:

Code: Select all

      n=f+1;
      sort(s,s+n);
      sort(a,a+n);
newkid was trying to get your attention to this part of the problem statement:
http://acm.uva.es/p/v8/855.html wrote:If there is more than one candidate point, the rule imposes that the meeting point is the one corresponding to the smaller number for street and avenue.
When F is even, all points in region [s[mid]..s[mid+1]] x [a[mid]..a[mid+1]] are valid meeting points, you need to print the lexicographically smallest of them, not the central one.
abid_iut wrote:

Code: Select all

 if((S==1 && A==1)   || (S==2 && A==2) || (S==3 && A==3))printf("(Street: 1, Avenue: 1)\n");
Man, not only this is ugly, but you've introduced a whole new bug with this code!

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 855 - Lunch in Grid City

Post by newkid »

Thanks mf.
I was just going to point to the problem statement..
hmm..

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 855 - Lunch in Grid City

Post by abid_iut »

thanks to all
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 855 - Lunch in Grid City

Post by sazzadcsedu »

whats wrong with my code??
WA.

Code: Select all

                      #include<stdio.h>
                      #include<stdlib.h>
                 

                     int comp(const void *i,const void *j)
						 
					 { 
						 return *(int *)i- *(int *)j;


					 }



                           int main()


						 { 

							 int i,ncase,str,av,frnd,med;
							 int street[1000],avenue[1000];


							 scanf("%d",&ncase);


							 while(ncase>0)

							 {
							 scanf("%d %d %d",&str,&av,&frnd);

							 for(i=0;i<frnd;i++)

							 { 

								 scanf("%d %d",&street[i],&avenue[i]);

							 }

							  
							 qsort(street,frnd,sizeof(int),comp);
                             qsort(avenue,frnd,sizeof(int),comp);


							 for(i=0;i<frnd;i++)
							 { 

								 printf("%d %d\n",street[i],avenue[i]);


							 }

                           
							 if(frnd%2)

								 med=(frnd-1)/2;

							 else
								 med=(frnd-1)/2;


							 //printf("%d\n",med);



         printf("(Street: %d, Avenue: %d)\n",street[med],avenue[med]);


                             
                                    ncase--;


							 }

                                  return 0;
						 }
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

Re: 855 - Lunch in Grid City

Post by newkid »

what does this if/else do?

Code: Select all

                     if(frnd%2)

                         med=(frnd-1)/2;

                      else
                         med=(frnd-1)/2;
its the same as writing only

Code: Select all

                med=(frnd-1)/2;
hmm..

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

Re: 855 - Lunch in Grid City

Post by uvasarker »

I am getting Runtime Error. Why? Help please................

Code: Select all

Thanks Guru (brianfry713)
I got AC.
Last edited by uvasarker on Fri Sep 07, 2012 2:51 pm, edited 1 time in total.

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

Re: 855 - Lunch in Grid City

Post by brianfry713 »

F can be as large as 50000.
Check input and AC output for thousands of problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 855 - Lunch in Grid City

Post by mgavin2 »

Sort the list they said. Find the median they said.

Nope, get WA. I understand the first couple of posts that differentiate the input from the lexicographically smaller number to output... but then a post afterward messes it up with different data.

Anyway... code.

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

//#define DEBUG  //comment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#define dbg(end) end
#else
#define debug(a, end)
#define dbg(end)
#endif

typedef pair<int, int> point;
typedef long long int64; //for clarity
typedef vector<int> vi; //?
typedef vector<point> vp; //?
template<class T> void chmin(T &t, T f) { if (t > f) t = f; } //change min
template<class T> void chmax(T &t, T f) { if (t < f) t = f; } //change max

#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())   
#define SORT(c) sort((c).begin(),(c).end())   
#define FOR(i,a,b) for (int  i=(a); i < (b); i++)    
#define REP(i,n) FOR(i,0,n)    
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)

/*global variables*/
vp friends;

struct cmp
{
	bool operator()(const point& a, const point& b)
	{
		if (a.first == b.first)
			return a.second < b.second;
		else
			return a.first < b.first;
	}

};

int a, b;
/*global variables*/

void dump()
{
    //dump data
}

bool getInput()
{
	int c;
	scanf("%d %d %d", &a, &b, &c);
	point p;
	REP(i, c)
	{
		scanf("%d %d", &p.first, &p.second);
		friends.push_back(p);
	}

    //get input
    return true;
}

void process()
{
    //process input

	sort(friends.begin(), friends.end(), cmp());

	for(vp::iterator it = friends.begin(); it != friends.end(); ++it)
	{
		dbg ( cout << it->first << " " << it->second << endl );
	}

    point minp;
    if (!(friends.size()%2))
        minp = friends[friends.size()/2-1];
    else
        minp = friends[friends.size()/2];
    
	printf("(Street: %d, Avenue: %d)\n", minp.first, minp.second);
	
}

int main()
{
	int nc;
	scanf("%d", &nc);
    while (nc-- > 0)
    {
		getInput();
        process();

        /*CLEAR GLOBAL VARIABLES!*/
		friends.clear();
        /*CLEAR GLOBAL VARIABLES!*/
    }

    return 0;
}

all that matters is AC

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

Re: 855 - Lunch in Grid City

Post by brianfry713 »

Input:

Code: Select all

1
10 10 3
1 8
4 1
8 4
AC output:

Code: Select all

(Street: 4, Avenue: 4)
Check input and AC output for thousands of problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

Re: 855 - Lunch in Grid City

Post by mgavin2 »

wow I'm dumb :-? .. /facepalm

ps. brianfry is the best
all that matters is AC

Post Reply

Return to “Volume 8 (800-899)”