10801 - Lift Hopping

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

hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

Post by hts » Sun May 01, 2005 9:27 am

Code: Select all

			gets(buf);

			p = buf;
			while(*p != '\n' && *p != 0)
			{
				while(*p == ' ' || *p == 0)
					p++;

				if(*p == '\n' || *p == 0)
					break;

				j = atoi(p);

				while(*p != ' ' && *p != '\n')
					p++;

				acesso[i][j] = 1;
			}
and also

Code: Select all

gets(buf);
p = buf;
while(*p != '\n' && *p != 0)
{
	sscanf(p, "%d%n", &j, &u);
	p += u;

	acesso[i][j] = 1;
}
Both gave WA.
maybe it's not an IO problem...[/code]

hts
New poster
Posts: 8
Joined: Sat Feb 22, 2003 2:56 am

Post by hts » Sun May 01, 2005 6:51 pm

I got ACC :D

It was a silly bug, this testcase helped me

Code: Select all

2 5
1 1
0 3
4 5
the above input reading routine is right.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Tue May 31, 2005 3:52 pm

I used exhaustive BFS to solve this problem. Though it passes all the test cases found in the forum, I only managed to get half a dozen WA with this. So, I think it's high time to find help from some others. Can someone look upon my code & tell me what I've done wrong? :P Thanks in advance.

Code: Select all

AC, code deleted.
Last edited by Mohammad Mahmudur Rahman on Tue May 31, 2005 11:16 pm, edited 1 time in total.
You should never take more than you give in the circle of life.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 31, 2005 8:08 pm

I compiled your code, and it said "IMPOSSIBLE" to all 4 of the sample test cases.
If only I had as much free time as I did in college...

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Tue May 31, 2005 9:21 pm

Sounds really strange ! :o I've just retested the program. It gives correct answer in all the test cases in my PC. will you please recheck & tell me what possibly could cause this? :roll: Nevertheless, thank you so much for your concern. :)
You should never take more than you give in the circle of life.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 31, 2005 10:45 pm

Your mistake is in the way you use sscanf(). Linux does not allow the zero character inside the format string in sscanf(). So this is illegal:

Code: Select all

sscanf( buf, " %d %[^\0]", &x, buf );
You have to do something else. The simplest thing is to use istringstream.

Code: Select all

#include <sstream>
...
gets( buf );
istringstream in( string( buf ) );
int x;
while( in >> x )
{
    ...
}
If you want it to be more efficient, you can do this:

Code: Select all

gets( buf );
int bs = 0, x, dbs;
while( sscanf( buf + bs, " %d%n", &x, &dbs ) == 2 )
{
    ....
    bs += dbs;
}
If only I had as much free time as I did in college...

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Tue May 31, 2005 11:12 pm

Thanks a lot man ! It was really helpful !! I particularly liked your second code block. 8)
But just a confusion, shouldn't it be -

Code: Select all

while( sscanf( buf + bs, " %d%n", &x, &dbs ) == 1)
instead of

Code: Select all

while( sscanf( buf + bs, " %d%n", &x, &dbs ) == 2 )
I've got it to work with the modified version i.e. ... == 1.
Thanks for the help again.
You should never take more than you give in the circle of life.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 31, 2005 11:24 pm

Sorry, you're right. %n does not increment the assignment counter.

Great! Now you are ready to solve 10841. :-)
If only I had as much free time as I did in college...

losvald
New poster
Posts: 3
Joined: Mon Jul 09, 2007 11:48 pm

Post by losvald » Mon Jul 09, 2007 11:53 pm

I keep getting WA. I tried everything, and tested with all this IO posted here and even with some tricky IO and everything seems OK. I also tried with different inputs (gets, fgets, getline...). I really cannot see the problem. Here is the source code:

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
#define MAX 105
using namespace std;
int n, k, t[MAX], bio[MAX];
int adj[MAX][MAX];
const int inf = 1000000000;
vector<vector<int> > a;
vector<int> dist; 
int input() {
  a.clear();
  if( scanf("%d%d", &n, &k) == EOF) return 0;
  a.resize(n);
  for(int i = 0; i < MAX; ++i)
    for(int j = 0; j < MAX; ++j)
      if(i == j) adj[i][j] = 0;
      else adj[i][j] = inf;
  for(int i = 0; i < n; ++i) scanf("%d", &t[i]);
  fflush(stdin);
  for(int i = 0; i < n; ++i) {
    char s[500], *token;
    gets(s);
    token = strtok(s, " ");
    if(token) {
      do {
        a[i].push_back(atoi(token));
        token = strtok(NULL, " ");
      } while(token);  
    }
    sort(a[i].begin(), a[i].end());
  }
  for(int i = 0; i < n; ++i)
    for(vector<int>::iterator p1 = a[i].begin(); p1 != a[i].end(); ++p1)
      for(vector<int>::iterator p2 = p1+1; p2 != a[i].end(); ++p2)
        if(*p1 != *p2)
        adj[*p1][*p2] = (adj[*p2][*p1] <?= (*p2-*p1)*t[i]);
  for(int i = 0; i < MAX; ++i)
    for(int j = 0; j < MAX; ++j)
     adj[i][j] += 60;
  return 1;
}
int solve() {
  for(int i = 0; i < MAX; ++i) bio[i] = 0;
  dist = vector<int>(MAX, inf); 
  dist[0] = 0;
  for(;;) {
    int u = -1;
    int mini = inf;
    for(int i = 0; i < MAX; ++i)
      if(!bio[i] && dist[i] < mini) {
        mini = dist[i];
        u = i;
      }
    if(u == -1) break;
    bio[u] = 1;
    for(int i = 0; i < MAX; ++i)   
      dist[i] <?= dist[u] + adj[u][i];    
  }
  return dist[k];  
}    
int main() {
  while( input() ) {
    int sol = solve();
    if(sol >= inf) printf("IMPOSSIBLE\n");
    else {
      if(sol >= 60) sol -= 60;
      printf("%d\n", sol);
    }  
  }  
  return 0;
}

Please help.

User avatar
Rupak
New poster
Posts: 8
Joined: Mon Jan 15, 2007 6:53 am
Location: Bangladesh

Post by Rupak » Tue Oct 16, 2007 3:53 pm

Need some input( :roll: ) and output( :D ).
_______________________________________
http://acm.uva.es/problemset/usersnew.php?user=6114

Mohamed Abd El-Monem
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

Re: 10801 - Lift Hopping

Post by Mohamed Abd El-Monem » Thu Sep 03, 2009 12:08 am

hi all

how could i know number of changing elevators?

thanx in advance

Musaffa
New poster
Posts: 1
Joined: Tue Nov 10, 2009 5:23 pm

Re: 10801 - Lift Hopping

Post by Musaffa » Tue Nov 10, 2009 5:45 pm

U can think of using unsigned int to track the time.
A lift can be as slow as 100. Max lift no 5 & Max floor no 100.
So 100*100*5=50000<65535 but >32767.
Use Dijkstra's shortest path.
Here is a sample input.

Code: Select all

4 89
7 2 4 8
3 34 45 56 77
4 23 34 89
0 99
3 99
Output

Code: Select all

1671

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10801 - Lift Hopping

Post by Shafaet_du » Thu Mar 17, 2011 3:22 pm

My algo is something between bfs and dijikstra :-| :-|

Try this case:

Code: Select all

5 99
12 90 34 56 22
0 4 7 3 6 8 98
4 10 20 23 46 50 69 88 99
0 3 12 45 50 77 88 99
0 20 46 77 98
0 50
ans=2826

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

Re: 10801 - Lift Hopping

Post by back_tracker » Sun Jul 24, 2011 12:57 am

what's the output of this input ??

2 99
10 40
1 2 3 4 99 0 12
3 4 2 0 12 99


my code gives 990

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Re: 10801 - Lift Hopping

Post by mmfrb » Sat Sep 22, 2012 4:56 pm

I know it seems to be a very silly question, but the answer would help me a lot.

Code: Select all

2 2
10 5
0 1 2
1 2
Is it 75? It wouldn't make any sense..

Post Reply

Return to “Volume 108 (10800-10899)”