11635 - Hotel booking

Moderator: Board moderators

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

11635 - Hotel booking

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 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;
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 )
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;
}
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 ) {
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;
}
``````

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

Re: 11635--Hotel Booking

Getting WA in this prob,pls help getting frustrated

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

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

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

Re: 11635--Hotel Booking

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 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() {
//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;
}
``````
You should not always say what you know, but you should always know what you say.

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

Re: 11635--Hotel Booking

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
Contact:

Re: 11635--Hotel Booking

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

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

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

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
016
void displayMain();
017
018
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
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
041
displayMain();
042
return 0;
043
}
044

045
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
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
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
230
getString("Is this new room a suite? (Y/N): ", tempChar);
231
232
getString("Does this new room have two beds? (Y/N): ", tempChar);
233
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
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
307
cout << "Would you like to request a room by number? (Y/N): ";
308
309
cout << endl;
310
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
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
360
cin.get();
361
getString("Would you like a suite? (Y/N) : ", answer);
362
363
cout << endl;
364
getString("Would you like a smoking room? (Y/N) : ", answer);
365
366
cout << endl;
367
getString("Would you like two beds? (Y/N) : ", answer);
368
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
386
for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
387
{
388
if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
389
390
}
391
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
405
for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
406
{
407
if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
408
409
}
410
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
466
{
467
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
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
}
``````

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

Re: 11635--Hotel Booking

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

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

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

Re: 11635--Hotel Booking

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

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!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

Re: 11635--Hotel Booking

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

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!