## 10350 - Liftless EME

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10350 - Liftless EME

The code always gets WA. Is anything I didn't consider yet? Could
someone give me some data?
[c]
#include<stdio.h>
void main(void)
{
int m,n,x,y,z;
long data[15],temp[15][15],min;
char name[20];
while(scanf("%s",name)!=EOF)
{
scanf("%d %d",&n,&m);
for(x=0;x<m;x++)
data[x]=0;
for(x=0;x<n-1;x++)
{
for(y=0;y<m;y++)
for(z=0;z<m;z++)
scanf("%d",&temp[y][z]);
for(z=0;z<m;z++)
{
for(y=0,min=2147483647;y<m;y++)
if(temp[y][z]+data[z]<min)
min=temp[y][z]+data[z];
data[z]=min;
}
}
for(x=0,min=2147483647;x<m;x++)
if(data[x]<min)
min=data[x];
printf("%s\n%ld\n",name,min+2*(n-1));
}
}
[/c]

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Hi!
I think your algorithm is wrong. Look this case:

Sample002
3 2
3 4
1 2
7 8
5 6

The correct output is 11, but your program's output is 10.
In the first step, the best way to arrive at second floor is go to the first hole in this floor, with cost 3, or go to the second hole in this floor with cost 4.
So if you stay in the first hole in the second floor, you can go to the third floor with 13 as minimum cust, and if you stay in the second hole in the second floor, you can go to the third floor with minimum cost 11, that is the best cost.

Here are some test cases:

INPUT
Sample001
3 2
1 2
3 4
5 6
7 8
Sample001
3 2
3 4
1 2
7 8
5 6
Sample002
2 2
4 3
2 2
Sample003
2 1
222222
Sample123
6 6
5 3 7 3 2 4
3 5 6 6 2 1
3 58 54 2 2 2
2 4 99 3 4 5
3 4 5 68 3 2
1 3 4 56 4 3
3 38 5 3 4 9
2 9 2 4 8 2
3 48 5 8 3 9
3 49 3 2 9 9
5 3 7 3 2 4
3 5 6 6 2 1
3 58 54 2 2 2
2 4 99 3 4 5
3 4 5 68 3 2
1 3 4 56 4 3
3 38 5 3 4 9
2 9 2 4 8 2
3 48 5 8 3 9
3 49 3 2 9 9
5 3 7 3 2 4
3 5 6 6 2 1
3 58 54 2 2 2
2 4 99 3 4 5
3 4 5 68 3 2
1 3 4 56 4 3
3 38 5 3 4 9
2 9 2 4 8 2
3 48 5 8 3 9
3 49 3 2 9 9
Sample444
7 10
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
4 3 2 1 48 5 5 8 2 9
3 4 9 25 9 2 4 5 6 7
4 29 2 1 3 4 9 5 3 2
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5
7 2 3 48 5 39 4 6 8 9
2 4 8 3 1 7 3 4 9 5
3 8 7 22 34 23 2 3 4 5

OUTPUT
Sample001
10
Sample001
11
Sample002
4
Sample003
222224
Sample123
18
Sample444
22

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

### 10350

hello,
can someone explain me the following line, coz i didnt get the following line?

Code: Select all

``````......the i-th hole through the roof of k-th floor (i.e. the i-th hole through the floor of (k+1)-th floor) to the ladder at the j-th hole through the roof of (k+1)-th floor.
``````
In problem description,
3 2
1 2
....
3 means there is 3 roofs and
2 means there is 2 holes, right?
and so on.

Need some details. ANYONE.
Help would be appreciated.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10350 - Liftless EME

DP wrote:hello,

can someone explain me the following line, coz i didnt get the following line?

Code: Select all

``````......the i-th hole through the roof of k-th floor (i.e. the i-th hole through the floor of (k+1)-th floor) to the ladder at the j-th hole through the roof of (k+1)-th floor.
``````
In problem description,

3 2

1 2

....

3 means there is 3 roofs and

2 means there is 2 holes, right?

and so on.

Need some details. ANYONE.

Help would be appreciated.
The line "1 2" represents the 1st hole of the 0-th floor; 1 is the time for this hole to the 1st hole of the 1st floor, and 2 is the time from this hole to the 2nd hole of the 1st floor.
Similarly, the line "3 4" represents the 2nd hole of the 0-th floor, and "5 6" represents the 1st hole of the 1st floor.
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.