10801 - Lift Hopping

[hts]

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]

I got ACC

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]

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? Thanks in advance.

Code: Select all

AC, code deleted.

[Abednego]

I compiled your code, and it said "IMPOSSIBLE" to all 4 of the sample test cases.

[Mohammad Mahmudur Rahman]

Sounds really strange ! 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? Nevertheless, thank you so much for your concern.

[Abednego]

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

[Mohammad Mahmudur Rahman]

Thanks a lot man ! It was really helpful !! I particularly liked your second code block.
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.

[Abednego]

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

Great! Now you are ready to solve 10841. :-)

[losvald]

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.

[Rupak]

Need some input( ) and output( ).

[Mohamed Abd El-Monem]

hi all

how could i know number of changing elevators?

thanx in advance

[Musaffa]

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]

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]

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]

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..