301

Jucovschi Constantin · Sun Nov 03, 2002 6:36 pm

How to solve 301 in time 0.00

I've tried some kind of opptimized backtracking and it run for 4.661 sec.

How to make this time 0.00 ?

Is there any other method ?

Cloud Song · Post by **Cloud Song** » Fri Jun 20, 2003 2:16 pm

hi, if you use a simple pruning in the B&B, you can get 0.00

hank · Post by **hank** » Fri Jul 04, 2003 4:02 pm

hi,excuse me
What is B&B?

srdjan · Post by **srdjan** » Wed Oct 08, 2003 4:43 pm

What's a good algorithm for problem 301? I can't think of any dynamic programming solution. I'm using recursion but basically it's considering every possible set of orders (with distinct total number of passengers) between two stations and that's why I'm getting TLE.

UFP2161 · Post by **UFP2161** » Fri Nov 14, 2003 12:04 am

Branch & Bound

[It could also mean Bed & Breakfast, but that's probably not what he meant =P]

Sanya · Post by **Sanya** » Sun Dec 14, 2003 11:41 pm

Hi, can somebody give me test data for this problem, please.
I don't know why my code produces WA. Thank you.
[pascal]
var
n,m,k,i,j,sum,bestsum:integer;
c:array[1..22] of integer;
r:array[0..6] of integer;
a,b,x:array[1..22] of byte;
begin
while True do
begin
read(n,m,k);
if (n=0)and(m=0)and(k=0) then break;
for i:=1 to k do read(a,b,c);
for i:=0 to m-1 do r:=n;
i:=0; sum:=0; bestsum:=0;
while True do
begin
inc(i);
j:=a;
while(j<b)and(r[j]>=c) do inc(j);
if j=b then
begin
for j:=a to b-1 do dec(r[j],c[i]);
x[i]:=1; inc(sum,(b[i]-a[i])*c[i]);
end else
begin
x[i]:=0;
end;
if i=k then
begin
if sum>bestsum then bestsum:=sum;
while (i>0)and(x[i]=1) do
begin
dec(sum,(b[i]-a[i])*c[i]);
for j:=a[i] to b[i]-1 do inc(r[j],c[i]);
dec(i);
end;
while (i>0)and(x[i]=0) do dec(i);
if i=0 then break;
dec(sum,(b[i]-a[i])*c[i]);
for j:=a[i] to b[i]-1 do inc(r[j],c[i]);
x[i]:=0;
end;
end;
writeln(bestsum:1);
end;
end.
[/pascal]

Opexoc · Post by **Opexoc** » Thu Jul 29, 2004 11:05 pm

Who can help me with this problem ? J have sumbited my solution but my
program still use too much memory. I think about better solution but nothing come to my head!
Any answer will be appreciated!

Kire Sopov · Post by **Kire Sopov** » Wed Sep 15, 2004 2:05 am

Here's my code, if it can help...
[cpp]
/* @JUDGE_ID: xxxxxx 301 C++ "Backtracking" */
#include <stdio.h>

#define MAX_ORDERS 25
#define MAX_STATION 10

// Global templates
template <class _T>
inline void Swap(_T &x, _T &y)
{
_T z = x;
x = y;
y = z;
}

// Global class definitions and typedefs
struct TICKET_ORDER
{
inline TICKET_ORDER():m_nFrom(0), m_nTo(0), m_nTickets(0), m_nEarnings(0) {}

inline TICKET_ORDER(int nFrom, int nTo, int nTickets)
{
m_nFrom = nFrom;
m_nTo = nTo;
if (m_nFrom > m_nTo) Swap<int>(m_nFrom, m_nTo);
m_nTickets = nTickets;
m_nEarnings = nTickets * (m_nTo - m_nFrom);
}

inline void Set(int nFrom, int nTo, int nTickets)
{
m_nFrom = nFrom;
m_nTo = nTo;
if (m_nFrom > m_nTo) Swap<int>(m_nFrom, m_nTo);
m_nTickets = nTickets;
m_nEarnings = nTickets * (m_nTo - m_nFrom);
}

inline bool operator > (const TICKET_ORDER &rhs)
{
if (m_nFrom != rhs.m_nFrom)
return (m_nFrom > rhs.m_nFrom);
return (m_nTo > rhs.m_nTo);
}

int m_nFrom, m_nTo, m_nTickets;
int m_nEarnings;
};

typedef TICKET_ORDER *PTICKET_ORDER;

class ORDERS_STACK
{
public:
inline ORDERS_STACK():m_nTop(-1) {}

inline void Push(int i)
{
m_arr[++m_nTop] = i;
}

inline int Pop()
{
return m_arr[m_nTop--];
}

inline int GetTopVal()
{
return m_arr[m_nTop];
}

inline bool IsEmpty()
{
return (m_nTop < 0);
}

private:
int m_arr[MAX_ORDERS];
int m_nTop;
};

// Global function declarations
void GetOrders(PTICKET_ORDER pOrders, int &nMaxOrders, int nCapacity, int nB);
int ProcessOrders(PTICKET_ORDER pOrders, int nMaxOrders, int nCapacity);

// The main entry
int main()
{
int nCapacity, nCityB, nNumOrders;
TICKET_ORDER arrOrders[MAX_ORDERS];

while (1)
{
scanf("%d%d%d", &nCapacity, &nCityB, &nNumOrders);
if ((nCapacity == 0) && (nCityB == 0) && (nCityB == 0))
break;
if (nCityB > 7) nCityB = 7;
if (nNumOrders > 22) nNumOrders = 22;
GetOrders(arrOrders, nNumOrders, nCapacity, nCityB);
printf("%d\n", ProcessOrders(arrOrders, nNumOrders, nCapacity));
}

return 0;
}

void GetOrders(PTICKET_ORDER pOrders, int &nMaxOrders, int nCapacity, int nB)
{
int nFrom, nTo, nQuantity, i(0);
int nTmp = nMaxOrders;

while (nTmp--)
{
scanf("%d%d%d", &nFrom, &nTo, &nQuantity);
if (nFrom > nB) nFrom = nB;
if (nTo > nB) nTo = nB;
if ((nQuantity <= nCapacity) && (nFrom != nTo))
{
pOrders[i].Set(nFrom, nTo, nQuantity);
if (i)
for (int j = i - 1; j >= 0; --j)
if (pOrders[j] > pOrders[j + 1])
Swap<TICKET_ORDER>(pOrders[j], pOrders[j + 1]);
i++;
}
}

nMaxOrders = i;
}

int ProcessOrders(PTICKET_ORDER pOrders, int nMaxOrders, int nCapacity)
{
int nTotalEarnings(0), nCurOrder(0), nMaxEarnings(0);
int arrPeopleInside[MAX_STATION];
ORDERS_STACK stack;

if (nMaxOrders == 0)
return 0;
if (nMaxOrders == 1)
return pOrders[0].m_nEarnings;

for (int i = 0; i < MAX_STATION; ++i)
arrPeopleInside[i] = 0;

while (1)
{
while (nCurOrder == nMaxOrders)
{
if (stack.IsEmpty())
return nMaxEarnings;
nCurOrder = stack.Pop();
nTotalEarnings -= pOrders[nCurOrder].m_nEarnings;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
arrPeopleInside[i] -= pOrders[nCurOrder].m_nTickets;
nCurOrder++;
}

bool bCanDo = true;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
if (arrPeopleInside[i] + pOrders[nCurOrder].m_nTickets > nCapacity)
{
bCanDo = false;
break;
}

if (bCanDo)
{
nTotalEarnings += pOrders[nCurOrder].m_nEarnings;
for (int i = pOrders[nCurOrder].m_nFrom; i < pOrders[nCurOrder].m_nTo; ++i)
arrPeopleInside[i] += pOrders[nCurOrder].m_nTickets;
stack.Push(nCurOrder++);
if (nMaxEarnings < nTotalEarnings)
nMaxEarnings = nTotalEarnings;
}
else
nCurOrder++;
}

return nMaxEarnings;
}
/*"@END_OF_SOURCE_CODE*/[/cpp]

oulongbin · Post by **oulongbin** » Mon Feb 21, 2005 10:06 am

i don't know how to solve this problem.could somebody give me some idea?thank you very much!!

Observer · Post by **Observer** » Mon Feb 21, 2005 2:00 pm

Hi,

You can solve this problem by backtracking. Good luck~

oulongbin · Post by **oulongbin** » Fri Feb 25, 2005 7:36 am

thanx,i have solved this problem ,backtracking ,thank you!

tan_Yui · Post by **tan_Yui** » Sat Oct 07, 2006 11:23 am

Hi, I'm trying to solve this problem, but got WA.
I want to know the information about the problem description.
Can anyone help me?

Code: Select all

Can the train pass the station visited once?
For example, in above test case,
if the train can pass the station visited once, the biggest possible total earning is 40.
But, if the train can't pass the station visited once, the biggest possible total earning is 32.

And if you have any test case, show me for debugging.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define MAX 7
#define NORAIL -1
#define ON  1
#define OFF 0
int adj[MAX+1][MAX+1];
int capacity, dest, max;

void function(int now, int earn, char passed[MAX+1][MAX+1]) {
  int i, j;
  if(now==dest) {
    if(earn > max) max = earn;
    return;
  }
  for(i=0; i<=dest; i++) {
    if(adj[now][i]==NORAIL) continue;
    if(passed[now][i]==ON) continue;
    passed[now][i] = passed[i][now] = ON;
    function(i, earn+abs((now-i)*adj[now][i]), passed);
    passed[now][i] = passed[i][now] = OFF;
  }
}

main() {
  int ticket, a, b, np, i, j;
  char passed[MAX+1][MAX+1];
  while(scanf("%d %d %d\n", &capacity, &dest, &ticket)!=EOF && !(capacity==0 && dest==0 && ticket==0)) {
    for(i=0; i<=dest; i++) {
      for(j=0; j<=dest; j++) {
        adj[i][j] = NORAIL;
        passed[i][j] = OFF;
      }
    }
    for(i=0; i<ticket; i++) {
      scanf("%d %d %d\n", &a, &b, &np);
      if(np > capacity) np = capacity;
      if(adj[a][b] < np) {
        adj[a][b] = adj[b][a] = np;
      }
    }
    max = 0;
    function(0, 0, passed);
    printf("%d\n", max);
  }
  return 0;
}

Thank you.

Yousef_Hanafi · Post by **Yousef_Hanafi** » Sat Apr 18, 2015 7:00 am

Hi, I'm trying to solve this problem, but got WA..
I tried hundreds of cases and all were correct ..
and this is my code
can anyone help or give me some tricky cases ?
thanks in advance

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n , b ,o, Max = 0;
struct order
{
	int s ,d,c;
};

vector<order> v;
bool valid (order s , int n)
{
	int x = 0;
	if ( s.d > b || s.s > b)
		return false;
	if ( v.empty())
		if ( s.c <= n )
			return true;
	for(int i = 0; i<v.size(); i++)
	{
		if (v[i].d >s.s)
			x+= v[i].c;
	}
	if ( x + s.c <= n)
		return true;

	return false;
}
int FindMaxVal(order * mat , int ord  , int sum ,int count)
{
	for(int i = ord; i< o; i++)
	{
		if(valid(mat[i],n))
		{
			sum += mat[i].c * (mat[i].d - mat[i].s);
			count += mat[i].c;
			v.push_back(mat[i]);
			FindMaxVal(mat,i+1,sum,count);
			if ( sum > Max)
				Max = sum;
			sum -= mat[i].c * (mat[i].d - mat[i].s);
			count -=mat[i].c;
			if( !v.empty())
				v.erase(v.begin()+v.size()-1);
		}
	}
	return Max;
}

int main()
{	
	while ( cin >> n >> b >> o && n && b && o )
	{
		order * mat = new order[o];
		for(int i = 0; i<o; i++)
		{
			cin >> mat[i].s >> mat[i].d >> mat[i].c;
		}
		int sum = 0 , count = 0 ; 
		Max = 0;
		cout <<FindMaxVal(mat,0,sum,count)<<endl;
		v.clear();
	}
}

anacharsis · Post by **anacharsis** » Fri Jul 10, 2015 8:31 pm

Some I/O

In:

Code: Select all

AC out:

Code: Select all

If that's not enough, here's an I/O generator to play with:

Code: Select all

import java.util.Random;

public class InGen {

	public static void main( String[] args ) {
		Random randy = new Random( System.currentTimeMillis() );

		for ( int i = 0; i < 20; ++i ) {
			int n = randomInRange( 50, 300, randy );
			int maxS = randomInRange( 4, 7, randy );
			int orders = randomInRange( 5, 22, randy );
			System.out.println( String.format( "%d %d %d", n, maxS, orders ) );
			int midS = maxS / 2;

			for ( int j = 0; j < orders; ++j ) {
				int start = randomInRange( 0, midS, randy );
				int end = randomInRange( midS, maxS, randy );

				if ( start == end ) {
					--j;
					continue;
				}

				int pass = randomInRange( 5, 200, randy );
				System.out.println( String.format( "%d %d %d", start, end, pass ) );
			}
		}
		
		System.out.println( "0 0 0" );
	}

	private static int randomInRange( int start, int end, Random randy ) {
		return randy.nextInt( end - start ) + start;
	}

}

OJ Board

301 - Transportation

How to solve 301 in time 0.00

problem 301

301 - Transportation

Re: 301 - Transportation

Re: 301 - Transportation