11635 - Hotel booking

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

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

11635 - Hotel booking

Post by serur » Fri Nov 06, 2009 6:50 am

I'm getting RE for this...

Code: Select all

/*
 * ``Hotel Booking''
 */
#include <algorithm>
#include <cctype>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 10001
#define TEN_HOURS (10*60)
#define Q (1UL << 21)
#define MASK(k) ((1UL << (k))-1UL)
#define enc(x,y) ((x)|((y)<<14))
#define xchg(x,y) (((x)==(y))||((x) ^= (y), (y) ^= (x), (x) ^= (y)))
#define bubble {\
		xchg(heap[i],heap[j]);\
		xchg(pos[heap[i]],pos[heap[j]]); }
#define oo 0xfffffffful

int n,h,m,is_hotel[N],yes;
vector<pair<int,int> > adj[N];
unsigned int heap[Q],d[Q];
int cnt,pos[Q];

void heap_push( unsigned int u ) {
	int i,j;

	if ( pos[u] < 0 ) {
		pos[heap[cnt] = u] = cnt;
		++cnt;
	}
	for ( j = pos[u]; j; j = i ) {
		if ( d[heap[i = (j-1)/2]] <= d[heap[j]] )
			break;
		bubble;
	}
}

void heap_pop( unsigned int *u ) {
	int i,j;

	pos[*u = *heap] = -1;
	if ( --cnt )
		pos[heap[0] = heap[cnt]] = 0;
	for ( j = 0;;) {
		i = j, j <<= 1, ++j;
		if ( j > cnt-1 ) break;
		if ( j < cnt-1 && d[heap[j+1]] < d[heap[j]] )
			++j;
		if ( d[heap[i]] <= d[heap[j]] ) break;
		bubble;
	}
}

int main() {
	int i,j,k,t,x,y,dt;
	unsigned int u,v;
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	while ( 1 == scanf("%d",&n) && n && ++yes ) {
		for ( i = 0; i < n; ++i )
			adj[i].clear();
		for ( scanf("%d",&h), i = 0; i < h; ++i )
			scanf("%d",&j), is_hotel[--j] = yes;
		for ( scanf("%d",&m); m--; ) {
			scanf("%d %d %d",&i,&j,&k);
			--i, --j;
			adj[i].push_back(make_pair(j,k));
			adj[j].push_back(make_pair(i,k));
		}
		memset(d,0xff,sizeof(d));
		d[0] = 0;
		memset(pos,-1,sizeof(pos));
		cnt = 0;
		heap_push(0);

		while ( cnt ) {
			heap_pop(&u), t = d[u];
			x = (u & MASK(14)), k = (u>>14);
			for ( i = 0; i < (int)adj[x].size(); ++i ) {
				pair<int,int> pp = adj[x][i];
				y = pp.first, dt = pp.second;
				if ( t+dt <= TEN_HOURS )
					if ( t+dt < d[v = enc(y,k)] ) {
						d[v] = t+dt;
						heap_push(v);	
					}
				if ( is_hotel[x] == yes ) {
					//assert( dt <= TEN_HOURS );
					if ( dt <= TEN_HOURS )
					if ( dt < d[v = enc(y,k+1)] ) {
						d[v] = dt;
						heap_push(v);
					}
				}
			}
		}
		for ( k = 0, j = -1; k <= h; ++k )
			if ( d[enc(n-1,k)] < +oo ) {
				j = k;
				break;
			}
		printf("%d\n",j);
	}
	return 0;
}

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11635--Hotel Booking

Post by Jehad Uddin » Sun Feb 14, 2010 11:11 am

Getting WA in this prob,pls help :oops: :oops: getting frustrated :x :x

Code: Select all

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<stdlib.h>
#define INF 900000000

using namespace std;

struct ss
{
    int tim,ht,pos;
};
int dis[10005][1005];

class comp{
    public : bool operator()(const ss &a,const ss &b)
    {
        return a.tim>b.tim;
    }
};
priority_queue<ss,vector<ss>,comp>Q;
vector<ss>edge[10005];
int n,m;
int h[10005];
int hh;
void ini()
{
    int i,j,k;
    for(i=0;i<=n;i++)
    {

        edge[i].clear();
        h[i]=0;
        for(j=0;j<=hh;j++) dis[i][j]=INF;

    }
    while(!Q.empty()) Q.pop();
}

void dijk()
{
    int i,j,k,l,u,v,t;
    ss s1,s2,s3,s4;
    s1.ht=0,s1.tim=0,s1.pos=1;
    dis[1][0]=0;
    Q.push(s1);
    while(!Q.empty())
    {
        s1=Q.top();
        Q.pop();
        u=s1.pos;
        //cout<<u<<" "<<s1.ht<<" "<<s1.tim<<endl;
        for(i=0;i<edge[u].size();i++)
        {
            s2=edge[u][i];
            v=s2.pos;
            if(s2.tim+s1.tim<dis[v][s1.ht]&&s2.tim+s1.tim<=(s1.ht+1)*600)
            {
                dis[v][s1.ht]=s2.tim+s1.tim;
                s3.ht=s1.ht,s3.pos=v,s3.tim=s2.tim+s1.tim;
                Q.push(s3);
            }
        }

        if(s1.tim%600!=0)
        {
            k=s1.tim/600;
            k=k+1;
            if(h[u]==1)
            {
                s3.ht=k,s3.tim=k*600,s3.pos=u;
                Q.push(s3);
            }
        }
    }
    k=INF;
    for(i=0;i<=hh;i++) if(dis[n][i]<k) k=dis[n][i],j=i;
    if(k!=INF) printf("%d\n",j);
    else
    printf("-1\n");
}

int main()
{
    int i,j,k,u,v,t;
    ss s1,s2;
    while(scanf("%d",&n)==1&&n)
    {

        scanf("%d",&hh);
        ini();
        for(i=0;i<hh;i++)
        {
            scanf("%d",&j);
            h[j]=1;
        }
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&t);
            s1.pos=v,s1.ht=0,s1.tim=t,s2.pos=u,s2.ht=0,s2.tim=t;
            edge[u].push_back(s1),edge[v].push_back(s2);
        }
        dijk();

    }
    return 0;
}

LifeMaker
New poster
Posts: 6
Joined: Sun Sep 19, 2010 11:28 pm

Re: 11635--Hotel Booking

Post by LifeMaker » Fri Sep 24, 2010 9:39 am

i'm really interested in knowing the correct approach to this problem, so can anyone please reply to this thread

i tried different approaches, but they all failed. now i got AC but in 2.7 seconds :-? (so clearly my algo. isn't good and there are much better ones)

the idea of my soln is that i apply dijkstra k times with each hotel as a source (i regard nodes 1 and n hotels as well), so now i have a smaller graph: g[k+2][k+2], which represents the all pair all dest. shortest paths between hotels (including node #1, #n).
then i apply bfs on this new graph from node #1 to get the shortest path to the destination. (in the graph g[][], 2 nodes i,j share an edge if g[j]<=600).

so, what is the best approach to this problem??

thanks in advance

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11635--Hotel Booking

Post by zobayer » Thu Dec 23, 2010 11:08 pm

I have also got WA. Here is my approach, tell me what is wrong here...

Lets say, weight here is a pair, first element, number of days (i.e. number of hotels) and second one is total minute continuing on that day.

Now, I run a dijkstra from 1 and try to reach N maintaining this:
if the current city is reachable (i.e. doesn't need more than 600 minutes from previous continuation) then
----> if it is a hotel then
--------> he may stay here, so day + 1 and continuation minutes becomes 0, push this state if possible
----> else he may not stay here, and continue his travel, so, days stay same, and minutes = minutes + current edge cost
else he just tries to continue, i.e. days stay same, and minutes = minutes + current edge cost.

finally the optimal days in N is my answer, here, I considered that, 1 and N don't have any hotel (as they will be useless and I removed if given any)

So, here is my code, if anyone wants to have a look

Code: Select all

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 long long
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x3f3f3f3f;
const int MAX = 10001;
const int LMT = 600;

typedef pair< pii, pii > edge;

vector< pii > G[MAX];
pii d[MAX][2];
bool flag[MAX][2], hotel[MAX];

int dijkstra(int s, int n) {
	int u, v, w, h;
	priority_queue< edge, vector< edge >, greater< edge > > Q;
	d[s][0] = pii(0, 0);
	hotel[s] = hotel[n] = 0;
	Q.push(edge(d[s][0], pii(s, 0)));
	while(!Q.empty()) {
		edge e = Q.top(); Q.pop();
		u = e.ss.ff, h = e.ss.ss;
		if(u == n) return e.ff.ff;
		if(flag[u][h]) continue;
		if(d[u][h] < e.ff) continue;
		for(int i = 0; i < SIZE(G[u]); i++) {
			v = G[u][i].ss;
			w = G[u][i].ff;
			if(hotel[v]) {
				if(!flag[v][0]) {
					if(d[u][h].ss + w <= LMT && d[v][0] > pii(d[u][h].ff, d[u][h].ss + w)) {
						d[v][0] = pii(d[u][h].ff, d[u][h].ss + w);
						Q.push(edge(d[v][0], pii(v, 0)));
					}
				}
				if(!flag[v][1]) {
					if(d[u][h].ss + w <= LMT && d[v][1] > pii(d[u][h].ff + 1, 0)) {
						d[v][1] = pii(d[u][h].ff + 1, 0);
						Q.push(edge(d[v][1], pii(v, 1)));
					}
				}
			}
			else {
				if(!flag[v][0]) {
					if(d[u][h].ss + w <= LMT && d[v][0] > pii(d[u][h].ff, d[u][h].ss + w)) {
						d[v][0] = pii(d[u][h].ff, d[u][h].ss + w);
						Q.push(edge(d[v][0], pii(v, 0)));
					}
				}
			}
		}
		flag[u][h] = 1;
	}
	return -1;
}

int main() {
	//READ("in.txt");
	//WRITE("out.txt");
	int n, e, k, i, u, v, w, ret;
	while(scanf("%d", &n)==1 && n) {
		for(i = 1; i <= n; i++) {
			G[i].clear();
			hotel[i] = flag[i][0] = flag[i][1] = 0;
			d[i][0] = d[i][1] = pii(INF, INF);
		}
		scanf("%d", &k);
		for(i = 0; i < k; i++) {
			scanf("%d", &e);
			hotel[e] = 1;
		}
		scanf("%d", &e);
		for(i = 0; i < e; i++) {
			scanf("%d%d%d", &u, &v, &w);
			G[u].PB(pii(w, v));
			G[v].PB(pii(w, u));
		}
		ret = dijkstra(1, n);
		printf("%d\n", ret);
	}
	return 0;
}
Thanks in advance.
You should not always say what you know, but you should always know what you say.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 11635--Hotel Booking

Post by smilitude » Sat Dec 25, 2010 5:19 pm

Your use of

Code: Select all

if(flag[u][h]) continue;
looks suspicious to me. You can enter a node with different minutes in hand - but i think your program will not consider all of them.
fahim
#include <smile.h>

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11635--Hotel Booking

Post by zobayer » Sat Dec 25, 2010 8:13 pm

smilitude wrote:Your use of

Code: Select all

if(flag[u][h]) continue;
looks suspicious to me. You can enter a node with different minutes in hand - but i think your program will not consider all of them.
You are right.. indeed it was the bug.
You should not always say what you know, but you should always know what you say.

chengouxuan
New poster
Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

Re: 11635--Hotel Booking

Post by chengouxuan » Sun Apr 24, 2011 9:11 am

LifeMaker wrote:i'm really interested in knowing the correct approach to this problem, so can anyone please reply to this thread

i tried different approaches, but they all failed. now i got AC but in 2.7 seconds :-? (so clearly my algo. isn't good and there are much better ones)

the idea of my soln is that i apply dijkstra k times with each hotel as a source (i regard nodes 1 and n hotels as well), so now i have a smaller graph: g[k+2][k+2], which represents the all pair all dest. shortest paths between hotels (including node #1, #n).
then i apply bfs on this new graph from node #1 to get the shortest path to the destination. (in the graph g[][], 2 nodes i,j share an edge if g[j]<=600).

so, what is the best approach to this problem??

thanks in advance


consider d[] to be the distance from the source vertex to any vertex in Dijkstra algorithm, v is the vertex with minimal d[] and is poped from the heap. d[v] never decrease. and we just need the vertexs which d[] <= 600. so quit Dijkstra as soon as you have popped a vertexs v and d[v] > 600. using this method, i have optimized my solution from 2.2 seconds to 0.9 seconds.

annedoxia122
New poster
Posts: 1
Joined: Tue Dec 20, 2011 9:53 am

Re: 11635--Hotel Booking

Post by annedoxia122 » Tue Dec 20, 2011 10:00 am

Code: Select all

#include "stdafx.h"
002
#include "roomType.h"
003
#include "hotelClient.h"
004
#include "HotelReservation.h"
005
#include <iostream>
006
#include <typeinfo>
007
#include <ctime>
008
#include <vector>
009
#include <fstream>
010
#include <string>
011
#include <exception>
012
 
013
using namespace std;
014
 
015
void loadFiles();
016
void displayMain();
017
void addRoomMenu();
018
void addClientMenu();
019
void requestReservation();
020
void displayRooms();
021
void displayClients();
022
void displayReservations();
023
void quit();
024
bool checkNumerical();
025
void getString(string message, string &s);
026
bool answerBoolConv(string answer);
027
bool getDate(int room, int &posDay1, int &posMonth1, int &posYear1, int &posDay2, int &posMonth2, int &posYear2);
028
 
029
template <class Type>
030
void getInput(string message, Type &x);
031
 
032
vector<roomType> rooms;
033
vector<hotelClient> clients;
034
vector<HotelReservation> reservations;
035
const string reservationMonth = "January";
036
const int maxReserved = 10;
037
 
038
int main()
039
{
040
    loadFiles();
041
    displayMain();
042
    return 0;
043
}
044
 
045
void loadFiles()
046
{
047
    ifstream file;
048
    file.exceptions ( ifstream::eofbit | ifstream::failbit | ifstream::badbit );
049
     
050
    roomType tempRoom;
051
         
052
    try
053
    {
054
        int count = 0;
055
        file.open("c:\\clientFile.txt");
056
 
057
        if (!file.eof())
058
            file >> count;
059
         
060
        for (int i = 0; i < count; i++)
061
        {
062
            int tempID;
063
            string tempFirst;
064
            string tempLast;
065
            char temp[250];
066
            string mailing;
067
            long long phone;
068
            string CCNum;
069
            double tempBalanceDue;
070
            string CCType;
071
 
072
            file >> tempID;
073
            file >> tempFirst;
074
            file >> tempLast;
075
            file.ignore();
076
            file.getline(temp, 250);
077
            mailing = static_cast<string>(temp);
078
            file >> phone;
079
            file >> CCNum;
080
            file >> CCType;
081
            file >> tempBalanceDue;
082
             
083
            hotelClient tempClient;
084
            tempClient.setClient(tempFirst, tempLast, mailing, phone, CCNum, CCType, tempID, tempBalanceDue);
085
            clients.push_back(tempClient);
086
        }
087
        file.close();
088
    }
089
    catch(exception &e)
090
    {
091
        cout << e.what() << " +Error trying to open clientFile.txt" << endl;
092
        file.clear();
093
        system("pause");
094
    }
095
         
096
    try
097
    {
098
        int count = 0;
099
        file.open("c:\\roomFile.txt");
100
 
101
        if (!file.eof())
102
            file >> count;
103
         
104
        for (int i = 0; i < count; i++)
105
        {
106
            int roomNo;
107
            double cost;
108
            bool smoking, twobeds, suite;
109
 
110
            file >> roomNo;
111
            file >> cost;
112
            file >> smoking;
113
            file >> twobeds;
114
            file >> suite;
115
             
116
            roomType temp(roomNo, cost, twobeds, smoking, suite);
117
            rooms.push_back(temp);
118
             
119
        }
120
        file.close();
121
    }
122
    catch(exception &e)
123
    {
124
        cout << e.what() << " +Error trying to open roomFile.txt" << endl;
125
        file.clear();
126
        system("pause");
127
    }
128
 
129
    try
130
    {
131
        int count = 0;
132
        file.open("c:\\reservationFile.txt");
133
 
134
        if (!file.eof())
135
            file >> count;
136
         
137
        for (int i = 0; i < count; i++)
138
        {
139
            int clientID;
140
            int reservNo;
141
            int roomNo;
142
            double cost;
143
            int day1, month1, year1, day2, month2, year2;
144
 
145
            file >> clientID;
146
            file >> reservNo;
147
            file >> roomNo;
148
            file >> cost;
149
            file >> day1 >> month1 >> year1;
150
            file >> day2 >> month2 >> year2;
151
 
152
            HotelReservation temp(clientID, roomNo, reservNo, cost, day1, month1, year1, day2, month2, year2);
153
            reservations.push_back(temp);
154
             
155
        }
156
        file.close();
157
    }
158
    catch(exception &e)
159
    {
160
        cout << e.what() << " +Error trying to open reservationFile.txt" << endl;
161
        file.clear();
162
        system("pause");
163
    }
164
}
165
 
166
void displayMain()
167
{
168
    system("cls");
169
 
170
     
171
     
172
 
173
    int selection;
174
 
175
    do
176
    {
177
        cout << "***********MAIN************" << endl;
178
        cout << "1.) add client" << endl;
179
        cout << "2.) display rooms" << endl;
180
        cout << "3.) display clients" << endl;
181
        cout << "4.) request reservation" << endl;
182
        cout << "5.) display reservations" << endl;
183
        cout << "6.) exit" << endl << endl;
184
        cout << "Selection: ";
185
        cin >> selection;
186
    }
187
    while (selection <= 0 && selection >= 8);
188
 
189
    switch (selection)
190
    {
191
    case 1:
192
        addClientMenu();
193
        break;
194
    case 2:
195
        displayRooms();
196
        break;
197
    case 3:
198
        displayClients();
199
        break;
200
    case 4:
201
        requestReservation();
202
        break;
203
    case 5:
204
        displayReservations();
205
        break;
206
    case 6: //leave blank
207
    default:
208
        quit();
209
    }
210
}
211
 
212
void addRoomMenu()
213
{
214
    int newRoomNumber = 1;
215
    bool smoking;
216
    bool suite;
217
    bool twoBeds;
218
    double costPerDay;
219
    string tempChar;
220
     
221
    if (rooms.size() != 0)
222
        newRoomNumber = rooms[rooms.size() - 1].getRoomNumber() + 1;
223
 
224
    system("cls");
225
 
226
     
227
    getInput("What is the cost per day? ", costPerDay);
228
    getString("Is this room smoking? (Y/N): ", tempChar);
229
    smoking = answerBoolConv(tempChar);
230
    getString("Is this new room a suite? (Y/N): ", tempChar);
231
    suite = answerBoolConv(tempChar);
232
    getString("Does this new room have two beds? (Y/N): ", tempChar);
233
    twoBeds = answerBoolConv(tempChar);
234
 
235
    roomType tempRoom(newRoomNumber, costPerDay, twoBeds, smoking, suite);
236
    rooms.push_back(tempRoom);
237
    cout << "The room has been created!" << endl;
238
    system("pause");
239
 
240
    displayMain();
241
}
242
 
243
void addClientMenu()
244
{
245
    int tempID;
246
    string tempFirst;
247
    string tempLast;
248
    string mailing;
249
    long long phoneNo;
250
    string creditNum;
251
    string CCType;
252
    double tempBalanceDue;
253
 
254
    system("cls");
255
 
256
    if(clients.size() == 0)
257
        tempID = 1111;
258
    else
259
        tempID = clients[clients.size() - 1].getCustomerID() + 1;
260
 
261
    cin.clear();
262
    cin.ignore(250, '\n');
263
 
264
    getString("What is the first name? ", tempFirst);
265
    getString("What is the last name? ", tempLast);
266
    getString("What is the mailing address? ", mailing);
267
    getInput("What is the phone number? (no dashes or spaces) ", phoneNo);
268
    getString("What is the credit card number? (no dashes or spaces) ", creditNum);
269
    getString("What is the credit card type? ", CCType);
270
    tempBalanceDue = 0;
271
 
272
    hotelClient tempClient(tempFirst, tempLast, mailing, phoneNo, creditNum, CCType, tempID, tempBalanceDue);
273
 
274
    clients.push_back(tempClient);
275
    cout << endl;
276
    cout << "A new client has been added!" << endl;
277
    system("pause");
278
    displayMain();
279
}
280
 
281
 
282
void requestReservation()
283
{
284
    system("cls");
285
     
286
    int clientID;
287
    int clientVecNum;
288
    getInput("Enter the client Identification number: ", clientID);
289
    bool exists = false;
290
    for (unsigned int i = 0; i < clients.size(); i++)
291
    {
292
        if (clientID == clients[i].getCustomerID())
293
        {
294
            exists = true;
295
            clientVecNum = i;
296
        }
297
 
298
    }
299
    if (exists)
300
    {
301
        bool available = false;
302
         
303
        do
304
        {
305
            bool roomNoRequested = false;
306
            string answer;
307
            cout << "Would you like to request a room by number? (Y/N): ";
308
            cin >> answer;
309
            cout << endl;
310
            roomNoRequested = answerBoolConv(answer);
311
            if (roomNoRequested)
312
            {
313
                int roomNumber;
314
                getInput("What room number would you like to request? : ", roomNumber);
315
                 
316
                bool reserved = false;
317
                int day, month, year, toDay, toMonth, toYear;
318
                reserved = getDate(roomNumber, day, month, year, toDay, toMonth, toYear);
319
 
320
                if(reserved == true)
321
                {
322
                    cout << "Room is unavailable for renting at that time or doesn't exist" << endl;
323
                    system("pause");
324
                    available = false;
325
                    break;
326
                }
327
                else
328
                {
329
                    bool roomReady = false;
330
                    int vecNum;
331
                    int reservationNumber = 11111111;
332
                    if (reservations.size() != 0)
333
                        reservationNumber = reservations[reservations.size() - 1].getReservationNum() + 1;
334
 
335
                    for (unsigned int i = 0; i < rooms.size(); i++)
336
                    {
337
                        if (roomNumber == rooms[i].getRoomNumber())
338
                        {
339
                            vecNum = i;
340
                        }
341
                    }
342
                     
343
                    HotelReservation temp(clientID, rooms[vecNum].getRoomNumber(), reservationNumber, day, month, year, toDay, toMonth, toYear);
344
                    temp.setCost(rooms[vecNum].getCost() * temp.getReservationLength());
345
                    clients[clientVecNum].SetBalanceDue(clients[clientVecNum].getBalanceDue() + temp.getCost());
346
                    reservations.push_back(temp);
347
                    cout << "The room is available and is now reserved for clientID " << clientID << "." << endl << endl;
348
                    system("pause");
349
                    available = true;
350
                    break;
351
                }
352
            }
353
             
354
            else
355
            {
356
                bool suite;
357
                bool smoking;
358
                bool twoBeds;
359
                string answer;
360
                cin.get();
361
                getString("Would you like a suite? (Y/N) : ", answer);
362
                suite = answerBoolConv(answer);
363
                cout << endl;
364
                getString("Would you like a smoking room? (Y/N) : ", answer);
365
                smoking = answerBoolConv(answer);
366
                cout << endl;
367
                getString("Would you like two beds? (Y/N) : ", answer);
368
                twoBeds = answerBoolConv(answer);
369
                cout << endl;
370
                vector<roomType> possibleRoomMatch;
371
                vector<bool> roomAvail;
372
 
373
                for (unsigned int i = 0; i < rooms.size(); i++)
374
                {
375
                    roomAvail.push_back(true);
376
                    if(rooms[i].getSuite() == suite)
377
                        possibleRoomMatch.push_back(rooms[i]);
378
                    else
379
                        roomAvail[i] = false;
380
                }
381
                for (unsigned int i = 0; i < rooms.size(); i++)
382
                {
383
                    if(rooms[i].getSmoking() == smoking)
384
                    {
385
                        bool alreadyThere = false;
386
                        for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
387
                        {
388
                            if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
389
                                alreadyThere = true;
390
                        }
391
                        if(alreadyThere == false)
392
                        {
393
                            if(roomAvail[i])
394
                                possibleRoomMatch.push_back(rooms[i]);
395
                        }
396
                    }
397
                    else
398
                        roomAvail[i] = false;
399
                }
400
                for (unsigned int i = 0; i < rooms.size(); i++)
401
                {
402
                    if(rooms[i].getTwoBeds() == twoBeds)
403
                    {
404
                        bool alreadyThere = false;
405
                        for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
406
                        {
407
                            if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
408
                                alreadyThere = true;
409
                        }
410
                        if(alreadyThere == false)
411
                        {
412
                            if(roomAvail[i])
413
                                possibleRoomMatch.push_back(rooms[i]);
414
                        }
415
                    }
416
                    else
417
                        roomAvail[i] = false;
418
                }
419
                bool matchFound = false;
420
                int d1, d2, m1, m2, y1, y2, room, roomVec;
421
                for (unsigned int i = 0; i < possibleRoomMatch.size(); i++)
422
                {
423
                    if(roomAvail[i])
424
                    {
425
                        if(!getDate(possibleRoomMatch[i].getRoomNumber(), d1, m1, y1, d2, m2, y2))
426
                        {
427
                            room = possibleRoomMatch[i].getRoomNumber();
428
                            roomVec = i;
429
                            matchFound = true;
430
                            break;
431
                        }
432
                    }
433
                }
434
                if(matchFound == true)
435
                {
436
                    int reservationNumber = 11111111;
437
                    if (reservations.size() != 0)
438
                        reservationNumber = reservations[reservations.size() - 1].getReservationNum() + 1;
439
                    HotelReservation temp(clientID, room, reservationNumber, d1, m1, y1, d2, m2, y2);
440
                    temp.setCost(temp.getReservationLength() * rooms[roomVec].getCost());
441
                    clients[clientVecNum].SetBalanceDue(clients[clientVecNum].getBalanceDue() + temp.getCost());
442
                    reservations.push_back(temp);
443
                    cout << "The room is available and is now reserved for clientID " << clientID << "." << endl << endl;
444
                    system("pause");
445
                    available = true;
446
                }
447
                else
448
                {
449
                    cout << "Sorry, there is no match available at this time" << endl << endl;
450
                    system("pause");
451
                    available = false;
452
                }
453
            }
454
        }
455
        while (available = false);
456
         
457
    }
458
    else
459
    {
460
        cout << "Client does not exist!!" << endl << endl;
461
        system("pause");
462
    }
463
    displayMain();
464
}
465
bool answerBoolConv(string answer)
466
{
467
    if (answer == "Y" || answer == "y")
468
        return true;
469
    else
470
        return false;
471
}
472
 
473
void displayRooms()
474
{
475
    system("cls");
476
    for (unsigned int i = 0; i < rooms.size(); i++)
477
        cout << rooms[i] << endl;
478
 
479
    cout << endl;
480
    system("pause");
481
    displayMain();
482
}
483
 
484
void displayClients()
485
{
486
    system("cls");
487
    for (unsigned int i = 0; i < clients.size(); i++)
488
        cout << clients[i] << endl << endl;
489
 
490
    system("pause");
491
    displayMain();
492
}
493
 
494
void displayReservations()
495
{
496
    system("cls");
497
    for (unsigned int i = 0; i < reservations.size(); i++)
498
        cout << reservations[i] << endl;
499
 
500
    system("pause");
501
    displayMain();
502
}
503
void quit()
504
{
505
    ofstream clientFile("c:\\clientFile.txt", ios::out);
506
 
507
    clientFile << clients.size() << endl;
508
    for(unsigned int i = 0; i < clients.size(); i++)
509
    {
510
        clientFile << clients[i].getCustomerID() << " ";
511
        clientFile << clients[i].getFirstName() << " ";
512
        clientFile << clients[i].getLastName() << endl;
513
        clientFile << clients[i].getMailingAddress() << endl;
514
        clientFile << clients[i].getPhoneNumber() << " ";
515
        clientFile << clients[i].getCreditCard() << " ";
516
        clientFile << clients[i].getCreditCardType() << " ";
517
        clientFile << clients[i].getBalanceDue() << " ";
518
        clientFile << endl;
519
    }
520
 
521
    ofstream reservationFile("c:\\reservationFile.txt", ios::out);
522
 
523
    reservationFile << reservations.size() << endl;
524
    for(unsigned int i = 0; i < reservations.size(); i++)
525
    {
526
        reservationFile << reservations[i].getClientId() << " ";
527
        reservationFile << reservations[i].getReservationNum() << " ";
528
        reservationFile << reservations[i].getRoomNumber() << " ";
529
        reservationFile << reservations[i].getCost() << " ";
530
        reservationFile << reservations[i];
531
        reservationFile << endl;
532
    }
533
}
534
 
535
template <class Type>
536
void getInput(string message, Type &x)
537
{
538
    do
539
    {  
540
        Type temp = 0;
541
        cout << message;
542
        cin >> temp;
543
        cout << endl;
544
        x = temp;
545
        cin.ignore();
546
    }
547
    while(!checkNumerical());
548
}
549
 
550
bool checkNumerical()
551
{
552
    if (!cin)
553
    {
554
        cout << "You entered an incorrect value, try again" << endl;
555
        cin.clear();
556
        cin.ignore(1000, '\n');
557
        return false;
558
    }
559
    else
560
        return true;
561
}
562
 
563
void getString(string message, string &s)
564
{
565
    cin.clear();
566
    char temp[250];
567
    cout << message;
568
    cin.getline(temp, 250);
569
    s = static_cast<string>(temp);
570
}
571
bool getDate(int room, int &posDay1, int &posMonth1, int &posYear1, int &posDay2, int &posMonth2, int &posYear2)
572
{
573
    system("cls");
574
    // Check to see if the room even exists first
575
    int roomVecNum = -1;
576
    int test = rooms.size();
577
    for (unsigned int i = 0; i < rooms.size(); i++)
578
    {
579
        if(rooms[i].getRoomNumber() == room)
580
        {
581
            roomVecNum = i;
582
            break;
583
        }
584
    }
585
    if(roomVecNum == -1)
586
        return true;
587
 
588
    cout << "You will now enter the starting date for the reservation..." << endl;
589
 
590
    int selection;
591
    do
592
    {
593
        cout << "Select a month" << endl;
594
        cout << "1.) Jan" << endl;
595
        cout << "2.) Feb" << endl;
596
        cout << "3.) Mar" << endl;
597
        cout << "4.) Apr" << endl;
598
        cout << "5.) May" << endl;
599
        cout << "6.) Jun" << endl;
600
        cout << "7.) Jul" << endl;
601
        cout << "8.) Aug" << endl;
602
        cout << "9.) Sep" << endl;
603
        cout << "10.) Oct" << endl;
604
        cout << "11.) Nov" << endl;
605
        cout << "12.) Dec" << endl;
606
        getInput("Selection: ", selection);
607
    }
608
    while (selection < 1 || selection > 12);
609
    posMonth1 = selection;
610
     
611
    do
612
    {
613
        getInput("Select a day (1-28) :", selection);
614
    }
615
    while (selection < 1 || selection > 28);
616
 
617
    posDay1 = selection;
618
     
619
    do
620
    {
621
        getInput("Select a year (2008 to 2011) :", selection);
622
    }
623
    while (selection < 2008 || selection > 2011);
624
 
625
    posYear1 = selection;
626
 
627
    system("cls");
628
    cout << "You will now enter an ending date for the reservation" << endl;
629
     
630
    do
631
    {
632
        cout << "Select a month" << endl;
633
        cout << "1.) Jan" << endl;
634
        cout << "2.) Feb" << endl;
635
        cout << "3.) Mar" << endl;
636
        cout << "4.) Apr" << endl;
637
        cout << "5.) May" << endl;
638
        cout << "6.) Jun" << endl;
639
        cout << "7.) Jul" << endl;
640
        cout << "8.) Aug" << endl;
641
        cout << "9.) Sep" << endl;
642
        cout << "10.) Oct" << endl;
643
        cout << "11.) Nov" << endl;
644
        cout << "12.) Dec" << endl;
645
        getInput("Selection: ", selection);
646
    }
647
    while (selection < 1 || selection > 12);
648
    posMonth2 = selection;
649
     
650
    do
651
    {
652
        getInput("Select a day (1-28) :", selection);
653
    }
654
    while (selection < 1 || selection > 28);
655
 
656
    posDay2 = selection;
657
     
658
    do
659
    {
660
        getInput("Select a year (2008 to 2011) :", selection);
661
    }
662
    while (selection < 2008 || selection > 2011);
663
 
664
    posYear2 = selection;
665
 
666
    time_t todayDate;
667
    time_t date2;
668
    time_t date3;
669
 
670
    time(&todayDate);
671
    struct tm date2str = {0,0,0,posDay1,posMonth1 - 1,posYear1 - 1900};
672
    struct tm date3str = {0,0,0,posDay2,posMonth2 - 1,posYear2 - 1900};
673
    //start = mktime(&today);
674
    date2 = mktime(&date2str);
675
    date3 = mktime(&date2str);
676
         
677
    double difference = difftime(date2, todayDate) / (60 * 60 * 24);
678
    if (difference < 0)
679
    {
680
        cout << "You entered a date from the past" << endl;
681
        system("pause");
682
        return true;
683
    }
684
     
685
    difference = -1;
686
 
687
    difference = difftime(date3, date2) / (60 * 60 * 24);
688
    if (difference < 0)
689
    {
690
        cout << "Your start date was after your end date!" << endl;
691
        system("pause");
692
        return true;
693
    }
694
 
695
    int days = static_cast<int>(difference);
696
 
697
    //Check if the room is not already reserved.
698
 
699
    time_t testDate;
700
    for(unsigned int x = 0; x < reservations.size(); x++)
701
    {
702
        testDate = reservations[x].getReservationstart();
703
        for(int y = 0; y <= days; y++)
704
        {
705
            for(int z = 0; z <= reservations[x].getReservationLength(); z++)
706
            {
707
                if(date2 == testDate)
708
                {
709
                    return true;
710
                }
711
                testDate = testDate + (60 * 60 * 24);
712
            }
713
            date2 = date2 + (60 * 60 * 24);
714
        }
715
    }
716
    return false;
717
     
718
}
This reference code might help you.

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11635--Hotel Booking

Post by mahade hasan » Sat Jan 05, 2013 7:38 pm

edited but still RE.....
getting RE ..........Why plz help me..........

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int infinity = 1000000000;

struct data {
    long city,H, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};



int main()
{
   long I,K,L,M,N,NoCity,NoHtl,NoRut;
   
   while(scanf("%ld",&NoCity)&&NoCity>0)
   {
      scanf("%ld",&NoHtl);
      bool Hotel[110]={0};
      while(NoHtl--)
      {
         scanf("%ld",&K);
         Hotel[K]=1;
      }
      
      vector<long> Edge[10009],Cost[10009];
      scanf("%ld",&NoRut);
      while(NoRut--)
      {
         scanf("%d %d %d",&I,&K,&L);
         Edge[I].push_back(K);
         Edge[K].push_back(I);
         Cost[I].push_back(L);
         Cost[K].push_back(L);
      }
      
      bool Status[10009]={0};
      N=infinity;
      priority_queue<data>Q;
      data u,v;
      
      u.city=1;
      u.dist=0;
      u.H=0;
      
      Q.push(u);
      while(!Q.empty())
      {
         u=Q.top();
         Q.pop();
         if(u.city==NoCity&&N>u.H) {N=u.H;continue;}
         for(I=0;I<Edge[u.city].size();I++)
         {
            v.city=Edge[u.city][I];
            v.dist=u.dist+Cost[u.city][I];
            v.H=u.H;
            if(v.dist>600)
            {
               if(Status[v.city]==0&&Hotel[u.city]==1)
               {
                  ++v.H;
                  Q.push(v);
                  Status[v.city]=1;
               }
            }
            else if(Status[v.city]==0)
            Status[v.city]=1,Q.push(v);
            
         }
      }
      if(N==infinity) printf("-1\n");
      else printf("%d\n",N);
   }
   
   return 0;
}

[/color]
Last edited by mahade hasan on Tue Jan 15, 2013 4:25 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

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

Re: 11635--Hotel Booking

Post by brianfry713 » Mon Jan 07, 2013 4:05 am

There could be a hotel in city 9999.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11635--Hotel Booking

Post by mahade hasan » Tue Jan 15, 2013 4:26 pm

brianfry713 wrote:There could be a hotel in city 9999.
edited but still RE......

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int infinity = 1000000000;

struct data {
    long city,H, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};



int main()
{
   long I,K,L,M,N,NoCity,NoHtl,NoRut;
   
   while(scanf("%ld",&NoCity)&&NoCity>0)
   {
      scanf("%ld",&NoHtl);
      bool Hotel[110]={0};
      while(NoHtl--)
      {
         scanf("%ld",&K);
         Hotel[K]=1;
      }
      
      vector<long> Edge[10009],Cost[10009];
      scanf("%ld",&NoRut);
      while(NoRut--)
      {
         scanf("%d %d %d",&I,&K,&L);
         Edge[I].push_back(K);
         Edge[K].push_back(I);
         Cost[I].push_back(L);
         Cost[K].push_back(L);
      }
      
      bool Status[10009]={0};
      N=infinity;
      priority_queue<data>Q;
      data u,v;
      
      u.city=1;
      u.dist=0;
      u.H=0;
      
      Q.push(u);
      while(!Q.empty())
      {
         u=Q.top();
         Q.pop();
         if(u.city==NoCity&&N>u.H) {N=u.H;continue;}
         for(I=0;I<Edge[u.city].size();I++)
         {
            v.city=Edge[u.city][I];
            v.dist=u.dist+Cost[u.city][I];
            v.H=u.H;
            if(v.dist>600)
            {
               if(Status[v.city]==0&&Hotel[u.city]==1)
               {
                  ++v.H;
                  Q.push(v);
                  Status[v.city]=1;
               }
            }
            else if(Status[v.city]==0)
            Status[v.city]=1,Q.push(v);
            
         }
      }
      if(N==infinity) printf("-1\n");
      else printf("%d\n",N);
   }
   
   return 0;
}

[/color]
we r surrounded by happiness
need eyes to feel it!

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

Re: 11635--Hotel Booking

Post by brianfry713 » Tue Jan 15, 2013 10:07 pm

Try input:

Code: Select all

10000
1 9999
2
1 9999 600
9999 10000 600
0
Output should be 1.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11635--Hotel Booking

Post by mahade hasan » Wed Jan 16, 2013 5:20 am

plz give some critical input for this problem ..........
we r surrounded by happiness
need eyes to feel it!

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

Re: 11635--Hotel Booking

Post by brianfry713 » Wed Jan 16, 2013 10:30 pm

brianfry713 wrote:Try input:

Code: Select all

10000
1 9999
2
1 9999 600
9999 10000 600
0
Output should be 1.
Your code produces an RE because your Hotel array is only size 110 and there could be a hotel in city 9999.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 11635--Hotel Booking

Post by mahade hasan » Sat Jan 19, 2013 6:45 am

mahade hasan wrote:plz give some critical input for this problem ..........
because after correction it gives WA.............
we r surrounded by happiness
need eyes to feel it!

Post Reply

Return to “Volume 116 (11600-11699)”