10278 - Fire Station

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

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10278 - Fire Station

Post by stcheung » Fri Oct 24, 2008 2:34 am

Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.

1
1 2
1
1 2 0

ymgve
New poster
Posts: 7
Joined: Mon Oct 15, 2007 1:17 am

Re: 10278 - Fire Station

Post by ymgve » Sun May 03, 2009 7:31 pm

stcheung wrote:Here's 1 more tricky test case, where the correct output is 1 even though there's already a fire station there. So don't immediately reject any intersection that already has a fire station. Be careful on TLE though, because after making this change my code went from 1sec to 6sec.

1
1 2
1
1 2 0
Isn't that wrong? The answer should be 2, since that location doesn't have any station already.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 10278 - Fire Station

Post by mak(cse_DU) » Sun Sep 06, 2009 4:33 pm

Actually the tricky part is below.
input:

Code: Select all

1
2 2
1
2
1 2 10
output will be:

Code: Select all

1
No intersection without fire station. so Answer is 1.
Mak
Help me PLZ!!

Stargazer71
New poster
Posts: 1
Joined: Fri Dec 17, 2010 6:16 am

Re: 10278 - Fire Station

Post by Stargazer71 » Fri Dec 17, 2010 6:27 am

I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.

Most of these inputs have already been posted, but this combination was:

- Brutal on my program, and
- Easy to verify at a glance

Input:

Code: Select all

8

2 2
1
2
1 2 10

0 4
1 2 10
2 3 10
2 4 10

2 7
1
4
1 2 5
1 4 30
1 3 20
2 4 45
2 5 25
3 4 15
3 6 35
5 7 10
6 7 40

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10 

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

1 8
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1

1 9
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

1 8
1
1 2 1
2 3 2
3 4 2
3 5 2
3 6 2
3 7 2
3 8 15
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

Chocolate
New poster
Posts: 3
Joined: Sat Jun 11, 2011 3:17 pm

Problem in reading input

Post by Chocolate » Sat Jun 11, 2011 5:24 pm

Hi, im new to UVa and finds that sometimes input-output here quite non-trivial.

I just want to work on this problem http://uva.onlinejudge.org/index.php?op ... oblem=1219

but I can't code to detect the blank lines between each testcase. I also found that this kind of input format is common for UVa problems (reading input until some blank lines).

I have tried using getline but still not working.

Anyone can help me with C++ code for reading input like the problem above ? (http://uva.onlinejudge.org/index.php?op ... oblem=1219)
Thanks before

zslwyuan
New poster
Posts: 4
Joined: Sun Nov 28, 2010 10:04 am

I Ac All the Samples that you gave, But WA,WHY!!HELP!!!

Post by zslwyuan » Tue Aug 09, 2011 5:21 am

#include<cstdio>
#include<cstring>
using namespace std;
int map[501][501],zj[501],yl[102],now[501];
bool used[501];
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
int i,j,k,l,n,m,t,o=0;scanf("%d\n",&t);
while (t--)
{
if (o)printf("\n");o=1;
scanf("%d %d",&m,&n);
memset(used,0,sizeof(used));
memset(map,60,sizeof(map));
for (i=1;i<=m;i++){scanf("%d\n",&yl);used[yl]=1;}
char s[300];
gets(s);
while (gets(s) != NULL && s[0] != '\0')
{
int x,y,z;
sscanf(s, "%d%d%d", &x, &y, &z);
map[x][y] = map[y][x] = z;
}
for (i=1;i<=n;i++)map=0;
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
{
if (k==i)continue;
for (j=1;j<=n;j++)
if (j!=i&&j!=k&&map[k]+map[k][j]<map[j])
map[j]=map[k]+map[k][j];
}
memset(zj,50,sizeof(zj));
int gd=100000000,gdn=1;
for (k=1;k<=n;k++)
if (!used[k])
{
int big=-1,bn;yl[m+1]=k;
memset(zj,60,sizeof(zj));
for (i=1;i<=n;i++)
for (j=1;j<=m+1;j++)
if (zj>map[yl[j]])
zj[i]=map[i][yl[j]];
for (i=1;i<=n;i++)
if (big<zj[i]){big=zj[i];}
if (big<gd){gd=big;gdn=k;}
}
printf("%d\n",gdn);
}
return 0;
}

djsohrab2007
New poster
Posts: 2
Joined: Mon Apr 30, 2012 12:50 am

Re: 10278 - Fire Station

Post by djsohrab2007 » Mon Apr 30, 2012 1:01 am

Stargazer71 wrote:I got snagged by some tricky inputs, so I'll give a sample output from my ACC program.

Most of these inputs have already been posted, but this combination was:

- Brutal on my program, and
- Easy to verify at a glance

Input:

Code: Select all

8

2 2
1
2
1 2 10

0 4
1 2 10
2 3 10
2 4 10

2 7
1
4
1 2 5
1 4 30
1 3 20
2 4 45
2 5 25
3 4 15
3 6 35
5 7 10
6 7 40

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10 

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

1 8
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1

1 9
3
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1

1 8
1
1 2 1
2 3 2
3 4 2
3 5 2
3 6 2
3 7 2
3 8 15
The correct output is:

Code: Select all

1

2

3

4

5

6

7

8
Hope this helps someone, and best of luck!

why output of this input is 4, I think it must be 5 ?

Code: Select all

1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
Because question is minimize the maximum distance from any intersection to its nearest fire station.
distance of Intersection 4 to Fire station 2 is 20, But distance of Intersection 5 to that Fire Station is 30.
Please help me,
I Can't get AC.

I write this Code :

Code: Select all

#include<iostream>
#include<string>
#include <sstream>
#define MAXINT 2147483647
#define size  502
using namespace std;

int floyd( int Graph[][size] , int I ,int f)
{
	int IndexMax = 1 ;
	if( f!= 0 )
	{
		int through_k;
		for( int k = 1 ; k <= I+1 ; k++ )
		{
			for(int i =1 ; i < I + 2 ; i++ )
			{
				for( int j =1 ; j < I + 2 ; j++ )
				{
					if(Graph[i][k] == MAXINT||Graph[k][j] ==MAXINT)
						through_k = MAXINT; 
					else
						through_k = Graph[i][k]+Graph[k][j];
					if(through_k < Graph[i][j])
						Graph[i][j]=through_k;
				}
			}
		}

		int MaxD = Graph[1][I+1];
		for( int i = 2 ; i < I + 1 ; i++ )
		{
			if ( MaxD < Graph[i][I+1] )
			{
				MaxD = Graph[i][I+1];
				IndexMax = i ;
			}
		}
		return IndexMax;
	}
	else
	{
		int MaxD = 0;
		for( int i = 1 ; i < I + 1 ; i++ )
		{
			int val = 0 ;
			for( int j = 1 ; j < I+1 ; j++ )
			{
				if( i == j )
					continue;
				val+=Graph[i][j];
			}
			if ( MaxD < val )
			{
				MaxD = val;
				IndexMax = i ;
			}
		}
		return IndexMax;
	}
}
int main()
{
	int NumberOfTestCase;
	cin>>NumberOfTestCase;
	for(int number = 0 ; number < NumberOfTestCase ; number++)
	{
		int Graph[ size ] [ size ];
		int F , I ;
		cin >> F >> I ;

		for( int i = 0 ; i < I + 2 ; i++ )
			for( int j = 0 ; j < I + 2 ; j++ )
				Graph[i][j]=MAXINT;

	
		for( int i = 0 ; i < F ; i++ )
		{
			int FirStation ;
			cin>>FirStation;
			Graph[I+1][FirStation] = 0;
			Graph[FirStation][I+1] = 0;
		}

		string Input ;
		cin.ignore(10, '\n' );
		getline(cin,Input,'\n');
	
		while( !Input.empty())
		{
			istringstream iss(Input);
			int v1 , v2 , Edge;
			iss>>v1;
			iss>>v2;
			iss>>Edge;
			Graph[v1][v2] = Edge;
			Graph[v2][v1] = Edge;
			getline(cin,Input,'\n');
		}

		cout<<floyd(Graph , I , F ) <<endl ;
	}
	return 0 ;
}
Thank you,

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

Re: 10278 - Fire Station

Post by brianfry713 » Fri May 04, 2012 8:30 pm

For this input, there is already a fire station at 2:

Code: Select all

1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
If you put the new fire station at 4, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 0
5: 10
6: 20
7: 20

If you put the new fire station at 5, the distance from each intersection to the nearest fire station is:
1: 10
2: 0
3: 10
4: 10
5: 0
6: 10
7: 20

I think you misunderstood the question. You are to find the intersection to put the new fire station to minimize the maximum distance from any intersection to the nearest fire station. If you put the new fire station at intersection 4 or 5 the max distance is 20 so in that case you pick the lowest intersection number.
Check input and AC output for thousands of problems on uDebug!

djsohrab2007
New poster
Posts: 2
Joined: Mon Apr 30, 2012 12:50 am

Re: 10278 - Fire Station

Post by djsohrab2007 » Thu May 10, 2012 11:30 am

Thank you,
I write this code for minimize maximum dis. but I got Run-time error,
I don't know why,
I compiled this code , every thing was Okay.

Code: Select all

#include<iostream>
#include<sstream>
#include<vector>
#define INF 2147483647
#define SIZE  502

using namespace std;
template <class T> 
class PriorityQueue
{
private:
	vector<int> Key;
	vector<T> element;
	vector<int>::iterator it;

	
	void insert(const T &value,const int &key ,const int l ,const int h)
	{
		if( h<=l )
		{
			if(Key.at(l)>= key )
			{
				it = element.begin();
				//it++;
				element.insert(it+l,value);

				it = Key.begin();
				//it++;
				Key.insert(it+l,key);
			}
			else
			{
				it = element.begin();
				it++;
				element.insert(it+l,value);

				it = Key.begin();
				it++;
				Key.insert(it+l,key);
			}
		}
		else
		{
			int mid = ( l + h ) / 2 ;

			if ( Key.at( mid ) == key )	// maybe queue have two element with same Priority 
			{
				it = element.begin();
				//it++;
				element.insert(it+mid,value);

				it = Key.begin();
				//it++;
				Key.insert(it+mid,key);
			} 
		    else if( Key.at( mid ) > key )
			{
				insert(value,key,l,mid-1 );
			}
			else if	( Key.at( mid ) < key )
			{
				insert(value,key,mid+1,h );
				
			}
			
		}
		
	}
public:
	PriorityQueue(const PriorityQueue& Copy)
	{
		Key = Copy.Key;
		element = Copy.element;
		
	}
	PriorityQueue operator=(const PriorityQueue& Copy)
	{
		Key = Copy.Key;
		element = Copy.element;
		return *this;
	}
	PriorityQueue()
	{
	}
	bool empty()
	{
		return element.empty();
	}
	int size()
	{
		return element.size();
	}
	void push(const T& value ,const int& key)
	{
		if(element.empty())
		{
			element.push_back(value);
			Key.push_back(key);
		}
		else
		{
			int s= element.size()-1;
			insert(value,key,0,s);
		}
	}
	T popLowestPriority()
	{
		
		T temp = element.at(0);

		it = element.begin();
		element.erase(it);

		it = Key.begin();
		Key.erase(it);

		return temp ;
	}
	T popHighestPriority()
	{
		
		T temp = element.back();
		element.pop_back();

		Key.pop_back();

		return temp ;
	}
	void changePriority(T value  , int newKey)
	{
		it = element.begin();
		int elementSize = element.size();
		for( int i = 0 ; i < elementSize ; i++ )
		{
			if( element.at( i ) == value )
			{
				element.erase( it+i);

				it = Key.begin();
				Key.erase(it+i);

				this->push(value,newKey);
			}
		}
	}
};	
class graph
{
	
private:
	vector<int> GraphAdj[ 3 ];
	vector<int> Locate;
	int Order;

	
public:
	graph( const graph& Copy )
	{
		for( int i = 0 ; i < 3 ; i++ )
		{
			GraphAdj[ i ] = Copy.GraphAdj[ i ];
		}
		Locate = Copy.Locate;
		Order = Copy.Order;
	}
	graph operator=(const graph& Copy )
	{
		for( int i = 0 ; i < 3 ; i++ )
		{
			GraphAdj[ i ] = Copy.GraphAdj[ i ];
		}
		Locate = Copy.Locate;
		Order = Copy.Order;
		return *this;

	}
	int getOrder()
	{
		return Order;
	}
	int getSize()
	{
		return GraphAdj[ 2 ].at( 0 );
	}
	void UpdateLocate()
	{
		int LocateSize = Locate.size();
		int GraphAdjSize = GraphAdj[0].size();
		
		for( int i = 1 ; i < LocateSize ; i++ )
			Locate.at( i ) = -1 ;
		//
		int temp = GraphAdj[0].at( 1 );
		Locate.at(temp) = 1;

		for( int i = temp + 1 ; i < GraphAdjSize ; i++ )
		{
			if ( temp != GraphAdj[ 0 ].at( i ) )
			{
				temp = GraphAdj[0].at( i );
				Locate.at(temp) = i;
			}
		}
	}
	int Dijkstra_Find_farestCity(const int& s)
	{
		//cout<<endl << endl <<"Start"<<endl<<endl ;

		PriorityQueue<int> Q ;
		vector<int> d (Order);
		int dSize = d.size();
		for( int i = 1 ; i < dSize ; i++ )
		{
			if( i != s )
			{
				Q.push(i, INF );
				d.at( i ) = INF ;
			}
			else if ( i == s )
			{
				Q.push(i, 0 );
				d.at( i ) = 0;
			}
		}

		//
		//cout<<"Size Q is: " << Q.size() <<endl;
		while( !Q.empty() )
		{
			int u = Q.popLowestPriority();
			int LocateU = Locate.at( u ) ;
			int temp = GraphAdj[ 0 ].at( LocateU );
			int i = LocateU;


			int GraphAdjSize = GraphAdj[1].size();

			while( i < GraphAdjSize && (temp == GraphAdj[ 0 ].at( i )))
			{
				int v = GraphAdj[ 1 ].at( i ) ;
				int wuv = GraphAdj[2].at( i );
				int dist;
				if( d.at( u ) == INF )
					dist = INF;
				else
				{
					dist = d.at( u ) + wuv ;
				}
				if( d.at( v ) > dist )
				{
					d.at( v ) = dist ;
					Q.changePriority(v,dist);
				}
				i++;
			}

		}
		int maxD = 0;

		for( int i = 1 ; i <dSize -1 ; i++ )
			if ( d.at( i ) != INF && maxD < d.at( i ) )
				maxD = d.at( i ) ;
		return maxD;

	}
	int getEdge( const int& v1 , const int& v2 )
	{
		int i1 = Locate.at( v1 ) ;
		if( i1 == -1 )
			return INF ;


		int temp = GraphAdj[ 0 ].at( i1 );
	
		int i2 = i1 ;
		int GraphAdjSize = GraphAdj[ 1 ].size();
		while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
		{
			if( GraphAdj[ 1 ].at( i2 ) == v2 )
				return GraphAdj[2].at(i2);
			else
				i2++;
		}


		return INF;
	
	}
	void addEdge(const int& v1,const int& v2 ,const int& w , bool update=false )
	{
		if( GraphAdj[ 0 ].size() == 1 )
		{

		}
		int i = 1 ;
		int GraphAdjSize = GraphAdj[ 0 ].size();
		while( i < GraphAdjSize && GraphAdj[ 0 ].at( i ) < v1 )
		{
			i++;
		}

		if( i == GraphAdj[ 0 ].size() )
		{
			GraphAdj[ 0 ].push_back( v1 );
			GraphAdj[ 1 ].push_back( v2 );
			GraphAdj[ 2 ].push_back( w );
		}
		else
		{
			vector<int>::iterator it;

			it = GraphAdj[0].begin();
			GraphAdj[ 0 ].insert(it+i,v1);

			it = GraphAdj[1].begin();
			GraphAdj[ 1 ].insert(it+i,v2);

			it = GraphAdj[2].begin();
			GraphAdj[ 2 ].insert(it+i,w);
		}
		GraphAdj[2].at(0)++;
		//update Locate
		if( update == true )
		{
			UpdateLocate();
		}
		
	}
	void removeEdge(const int& v1 , const int& v2 )
	{
		int i1 = Locate.at( v1 ) ;
		if( i1 == -1 )
			return ;
		int temp = GraphAdj[ 0 ].at( i1 );
	
		int i2 = i1 ;
		int GraphAdjSize = GraphAdj[ 1 ].size();
		while( ( i2 <GraphAdjSize ) && ( temp == (GraphAdj[ 0 ].at( i2 ))) )
		{
				if( GraphAdj[ 1 ].at( i2 ) == v2 )
				{
					vector<int>::iterator it;

					it = GraphAdj[ 0 ].begin();
					GraphAdj[0].erase(it+i2);

					it = GraphAdj[ 1 ].begin();
					GraphAdj[1].erase(it+i2);

					it = GraphAdj[ 2 ].begin();
					GraphAdj[2].erase(it+i2);
					GraphAdj[2].at(0)--;
					//update Locate
					UpdateLocate();
					return;
				}
				else
					i2++;
		}

	}

	graph(int order)
	{
		Order = order+1;
		//Locate.resize(Order);
		for( int i = 0 ; i < Order ; i++ )
			Locate.push_back(-1);
		GraphAdj[ 0 ].push_back(Order);
		GraphAdj[ 1 ].push_back(Order);
		GraphAdj[ 2 ].push_back(0);
	}
};

int findIntersection( graph& g , int I ,int NumberOfFireStation)
{
	vector<int>	MaxDistance ( I+2 ) ;
		//
	
	for( int i = 1 ; i < I + 1 ; i++ )
	{
		//Build FireStation on Intersetion i
		graph g1 = g ;
		int sg = g.getSize();
		g1.addEdge(i,I+1,0);
		g1.addEdge(I+1,i,0,true);
		int sg1 = g1.getSize();
		
		MaxDistance[ i ] = g1.Dijkstra_Find_farestCity(I+1);
	}
	int MinD = MaxDistance[1],IndexMin = 1 ;
	for( int i = 2 ; i < I + 1 ; i++ )
	{
		if( MinD > MaxDistance[ i ] )
		{
			MinD = MaxDistance[ i ];
			IndexMin = i ;
		}

	}
	return IndexMin;
}

int main()
{
	int NumberOfTestCase;
	cin>>NumberOfTestCase;
	for(int number = 0 ; number < NumberOfTestCase ; number++)
	{
		//structure of Graph 
		vector<int> GraphAdj[ 3 ];
		
		int F , I ;
		cin >> F >> I ;
		if( I == 1 )
		{
			cout<<"1"<<endl;
		}
		else
		{
			graph g(I+1);
			//
			for( int i = 0 ; i < F ; i++ )
			{
				int FirStation ;
				cin>>FirStation;

				g.addEdge(FirStation,I+1,0);
				g.addEdge(I+1,FirStation,0);
			}

			string Input ;
			cin.ignore(10, '\n' );
			getline(cin,Input,'\n');

			while( !Input.empty())
			{
				istringstream iss(Input);
				int v1 , v2 , Edge;
				iss>>v1;
				iss>>v2;
				iss>>Edge;

				g.addEdge(v1,v2,Edge);
				g.addEdge(v2,v1,Edge);
				
				getline(cin,Input,'\n');
			}
			g.UpdateLocate();
			cout<<findIntersection(g,I , F ) <<endl ;
			
			if( number != NumberOfTestCase - 1 )
				cout<<endl;
		}
	
	}
	return 0;
}






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

Re: 10278 - Fire Station

Post by brianfry713 » Fri May 11, 2012 4:02 am

Input:

Code: Select all

2

1 1
1

1 7
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 1 10
AC output:

Code: Select all

1

4
Check input and AC output for thousands of problems on uDebug!

Ryan
New poster
Posts: 1
Joined: Thu May 24, 2012 8:49 pm

Re: 10278 - Fire Station

Post by Ryan » Thu May 24, 2012 8:56 pm

Nice article of yours about "10278 - Fire Station". I like your well post. How can I help you ? I think your topic about road distance between cities with fire station. Thanks for your fine sharing.

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10278 - Fire Station

Post by cyberdragon » Wed Aug 06, 2014 10:41 am


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

Re: 10278 - Fire Station

Post by brianfry713 » Wed Aug 06, 2014 9:22 pm

Input:

Code: Select all

1

1 15
13
1 2 92
1 3 24
1 7 56
1 8 38
1 11 23
1 12 66
1 13 68
1 14 17
2 3 47
2 4 58
2 5 11
2 6 73
2 7 66
2 10 24
2 11 37
2 12 84
2 13 49
3 5 58
3 6 29
3 9 42
3 10 65
3 11 80
3 12 60
3 13 37
3 15 57
4 6 74
4 7 45
4 8 30
4 11 62
5 9 57
5 13 95
5 15 55
6 7 5
6 9 61
6 10 9
6 11 56
6 12 15
6 13 56
6 14 84
6 15 78
7 9 25
7 11 81
7 12 49
8 9 19
8 10 4
8 11 60
8 12 8
8 13 51
8 14 17
9 10 25
9 11 72
9 12 36
9 13 85
9 15 80
10 12 24
10 14 24
10 15 62
11 12 85
11 13 15
11 14 33
11 15 23
12 14 42
12 15 46
13 15 26
AC output 10
Check input and AC output for thousands of problems on uDebug!

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 10278 - Fire Station

Post by Farsan » Sun Sep 21, 2014 12:21 pm

Is there anyway to solve the problem by running dijkstra's algo only once instead of placing firestation at every possible intersection?

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

Re: 10278 - Fire Station

Post by brianfry713 » Mon Sep 22, 2014 8:57 pm

I got AC in 0.022 seconds by running Dijkstra's Algorithm from every intersection that doesn't already have a fire station.

I got AC in 1.356 seconds using the Floyd-Warshall Algorithm.

This line from the problem statement is not met in the judge's input: "there will exist a route between any pair of intersections."
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”