10138 - CDVII

[frode]

Does anyone have some test data they would like to share?

Frode

[BiK]

The problem statement is very unclear to me. How should I interpret the following:

"enter" records that are not paired with an "exit" record are ignored, as are "exit" records not paired with an "enter" record

What if I have only one vehicle and the following photos are ordered chronologically:

exit, enter, enter, exit, exit, exit, enter

Which one is paired with which one?

Besides my program checked the input data and it turned out that there are photos for the same vehicle with the same time even though the statement claims the opposite.[/b][/quote]

[Delf]

What if I have only one vehicle and the following photos are ordered chronologically:

exit, enter, enter, exit, exit, exit, enter

Which one is paired with which one?

"Each "enter" record is paired with the chronologically next record for the same vehicle provided it is an "exit" record"

Therefore, 3-rd and 4-th photos are paired.


Who can write some tests for this problem?

[fpmc]

After many many tries, here's some subtle information:

There are NO cases where the same vehicle contains entries where day, hours, minutes are all same.

There WILL be cases where there are no matching pairs at all. In that case the vehicle did not use the highway and so should not be printed (as stated in the description).

There WILL be cases where the entrance and exit are the same for one matching pair. In this case the $1/trip still counts, the cost per km is obviously $0, and this vehicle is considered to have used the highway (so +$2 account fee and so should be printed).

A more obvious one is that the entrance may be > exit: use absolute values.

Some test cases:

Code: Select all

2

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
ABCD123 01:01:06:01 enter 17
765DEF 01:01:07:00 exit 95
ABCD123 01:01:08:03 exit 95
765DEF 01:01:05:59 enter 17

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
ABCD123 01:01:06:01 enter 17
765DEF 01:01:07:00 exit 95
ABCD123 01:01:08:03 exit 95
765DEF 01:01:05:59 enter 95
123455 01:01:05:33 enter 13
EEF 01:01:06:03 enter 13
EEF 01:01:06:14	exit 6

and output from my AC program

Code: Select all

765DEF $10.80
ABCD123 $18.60

765DEF $3.00
ABCD123 $18.60
EEF $4.40

Hopefully this helps ^_^

Frank

[mullusko]

As is so often the case for me this code passes all the tests I can devise for it yet I still get WA. Can anyone come up with some test data to make this program fail?

[cpp]
/* @JUDGE_ID: 31585PK 10138 C++ */


#include <map>
#include <list>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const bool ENTER = 1;
const bool EXIT = 0;


string col_to_sp( string in )
{
replace( in.begin(), in.end(), ':', ' ' );
return in;
}


string getline( istream &input )
{
string result;
getline( input, result );
return result;
}


class event
{
public:
unsigned time; // (( day*24 + hr ) * 60 ) + min
int month;
bool type;
//string ID;
int loc;

void set_time( int in_month, int day, int hr, int min )
{
month = in_month;
time = (( day*24 + hr ) ) * 60 + min;
}

event( int in_month=0, int day=0, int hr=0, int min=0, string i_type="", int i_loc = 0 )
{
if( i_type == "enter" )
type = ENTER;
else
type = EXIT;
set_time( in_month, day, hr, min );
loc = i_loc;
}

bool operator<( const event comp ) const
{
if( month < comp.month )
return true;
if( month == comp.month )
if( time < comp.time )
return true;
return false;
}
};


int main( )
{
map< string, list< event > > cam_log;
vector<int> toll;
int cases;

istringstream buffs;

buffs.str( getline( cin ) );
buffs >> cases;
buffs.clear();
buffs.str( "" );

while( cases-- ){
while( buffs.str().empty() ){
if( !cin )
return 1;
buffs.str( getline( cin ) );
}
for( int x = 0; x < 24; x++ ){
int temp;
buffs >> temp;
toll.push_back( temp );
}

buffs.clear();
buffs.str( col_to_sp(getline( cin )) );
while( ! buffs.str().empty() ){
string temp_ID;
buffs >> temp_ID;
int month, day, hour, min;
buffs >> month >> day >> hour >> min;
string type;
buffs >> type;
int temp_loc;
buffs >> temp_loc;
cam_log[ temp_ID ].push_back( event( month, day, hour, min, type, temp_loc ) );
buffs.clear();
buffs.str( col_to_sp(getline( cin )) );
}

for( map< string, list< event > >::iterator cam_exam = cam_log.begin(); cam_exam != cam_log.end(); cam_exam++ ){
unsigned tolltotal = 0;
string tag_ID = cam_exam->first;
cam_exam->second.sort();

while( !cam_exam->second.empty() ){
event enter;
do{
enter = cam_exam->second.front();
cam_exam->second.pop_front();
if( cam_exam->second.empty() )
break;
}while( enter.type != ENTER );
if( cam_exam->second.empty() )
break;
if( cam_exam->second.front().type == EXIT ){
event exit = cam_exam->second.front();//calc
cam_exam->second.pop_front();
tolltotal += ( 100 + ( toll[ ( enter.time%(24*60) / 60 ) ] * abs( enter.loc - exit.loc ) ) );
}
//else just get the next thing
}
if( tolltotal != 0 ){
tolltotal += 200;
cout << tag_ID << " $";
cout << tolltotal / 100 << ".";
if( tolltotal % 100 < 10 )
cout << "0";
cout << tolltotal % 100 << endl;
}
}
if( cases )
cout << endl;
}


return 0;
}
[/cpp]

[ahsanlatif]

Hello,
I am facing a problem in one of the sample provided in the problem statement.
How come the cost for the vehicle 765DEF in sample input is $10.87- My algorithm is as follows

and it gives $ 18.47 for this vehicle but for all other test data provided it works fine.

Algorithm:
1) Calculate the speed of the vehicle in units of km per min using the

(entrance_pos-exit_pos)/total_minutes_spent.

In this test data: distance covered is 78 km and time spent 61 min. so speed=1.2786 km/min

2) Then I calculate the minutes_per_hour through out the trip.

In test data: 1 min in the time range (5:00 ~ 5:59) @ 10 cents/min
60 min in the range (6:00 ~ 6:59) @ 20 cents/min

Now the cost should be:
(1 * 1.2786 * 10)+(60*1.2786*20)+100+200
=12.786+1534.32+100+200
=1847.106 cents
=18.47$

Am I making any mistake?(I know I am but where is it)
Waiting for your reply.

Thanks in advance

[Leonid]

Problem description:

A particular toll highway, the CDVII, has a fare structure that works as follows: travel on the road costs a certain amount per km travelled, depending on the time of day when the travel begins.

So you shouldn't "Calculate the speed of the vehicle in units of km per min".
Simply: $$ = travel_entrance_price_at_a_time_entered*(travel_end - travel_begin);

[ahsanlatif]

Thanks Leonid,
I missed that point in the statement. Can you provide some critical test data(input/output).

Thanx again!!

[Leonid]

Thanks Leonid,
I missed that point in the statement. Can you provide some critical test data(input/output).

Thanx again!!

try this one: (input)

1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
GLBUVL2TPTUCVR8MKMC 05:11:03:25 exit 90
YN0NO2YHIAA 05:23:02:52 enter 61
YLEO3KAE3W841XAIO 05:30:19:29 enter 78
B1CUWJZI0083XOG 05:15:10:27 exit 35
TDRD4FM 05:19:17:50 enter 9
VB5NA 05:18:14:57 exit 87
AY 05:08:23:15 enter 59
T5A2OHJC53WR 05:26:22:06 enter 9
CM0U9YUA12Y 05:30:03:07 enter 76
BKQTNZ9OT61BQ 05:24:03:51 enter 3
1 05:16:22:15 enter 58
1DSRVW3VVCB8SIY 05:23:01:54 enter 51
ZZT 05:25:17:40 exit 13
GOXOTET4P3JPR9KSQ5 05:06:11:51 enter 66
CM0U9YUA12Y 05:03:20:04 exit 79
UBB4LYEWM5 05:29:20:07 exit 23
2R27ZSDDLG77OVIT9RJ 05:26:17:07 enter 72
IRN1VCFX8KH 05:10:11:41 enter 7
NVG9YKZPLPLPJ1S2LN1N 05:16:14:55 enter 99
DBUA8 05:29:04:34 enter 69
KHTKQO7F6 05:19:20:25 enter 66
T5A2OHJC53WR 05:16:02:05 enter 62
WA7MZ2EUDTJKCB 05:11:22:20 exit 79
I7LP 05:04:05:35 exit 14
VRQ2ECL 05:14:06:00 exit 31
GV5QEE 05:28:14:00 exit 74
GLBUVL2TPTUCVR8MKMC 05:03:07:47 enter 74
FCP6QN207YMN 05:24:04:40 enter 96
QPM870QV4D1CLWI1 05:26:23:55 enter 48
D 05:05:09:54 exit 31
1 05:28:13:47 enter 32
1DSRVW3VVCB8SIY 05:29:04:59 exit 91
QPM870QV4D1CLWI1 05:22:19:53 exit 61
WL 05:17:08:04 exit 78
6D51YFQB 05:10:04:03 enter 44
3H4LI1KVBCX4GM 05:07:23:52 exit 1
5U3BEI 05:04:03:48 exit 27
NVG9YKZPLPLPJ1S2LN1N 05:15:00:22 exit 50
6D51YFQB 05:28:21:22 enter 36
K42FAELL48AHKPVRFY 05:23:01:50 exit 16
MM09ENQ 05:13:22:09 exit 24
Y30EGA6IKO3NGRFZL3IY 05:27:04:47 exit 80
BGEO6D8ZUOG86 05:27:04:27 exit 41
WL 05:24:09:06 enter 12
22WHS9NTB3Y0TUKY 05:03:19:46 exit 89
5U3BEI 05:15:11:29 exit 52
KHTKQO7F6 05:13:16:17 enter 84
93KWIKL 05:01:23:04 enter 77
FCP6QN207YMN 05:16:06:28 enter 4
YJLWF1DYJN 05:23:22:48 exit 11
Y30EGA6IKO3NGRFZL3IY 05:15:11:19 exit 0
LZ 05:01:12:07 exit 82
BOCRA 05:30:14:26 enter 47
PR8OLVNX2SATF4G 05:13:10:29 enter 77
GLBUVL2TPTUCVR8MKMC 05:28:04:58 exit 59
QPM870QV4D1CLWI1 05:22:02:00 enter 55
ZI67765FTJ 05:20:11:16 enter 26
I7LP 05:11:12:46 exit 84
MW4CVD2 05:04:16:21 exit 99
RZ423QQYDTRHE 05:26:09:52 enter 77
YN0NO2YHIAA 05:22:12:47 enter 27
6D51YFQB 05:17:01:49 exit 31
6Z 05:24:13:06 exit 42
YSDV2CMK49I 05:19:19:02 exit 5
J3WZWPO 05:12:10:05 exit 38
TJY1Q 05:22:23:33 enter 25
TYQTZDE 05:24:22:06 enter 52
AY 05:19:01:46 exit 97
JTLC2 05:09:23:27 exit 64
3112OV4J6 05:01:10:28 exit 9
TDDBGG2NDZH 05:28:03:03 enter 16
VB5NA 05:08:07:32 enter 15
22WHS9NTB3Y0TUKY 05:29:14:46 exit 99
AY 05:29:09:29 exit 81
HBQ 05:08:06:52 enter 44
ZBCXBO9JBXN 05:11:23:00 enter 52
4RTV 05:12:00:24 exit 90
BOCRA 05:15:04:09 exit 2
9WJ 05:05:01:14 exit 36

and output:

1DSRVW3VVCB8SIY $3.80
6D51YFQB $3.65
AY $12.12
GLBUVL2TPTUCVR8MKMC $4.28
QPM870QV4D1CLWI1 $3.18
VB5NA $8.76

[nnicool]

I passed All test case

my test data..
---------------------------------------------------------------------------
1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
GLBUVL2TPTUCVR8MKMC 05:11:03:25 exit 90
YN0NO2YHIAA 05:23:02:52 enter 61
6D51YFQB 05:28:21:22 enter 36
YLEO3KAE3W841XAIO 05:30:19:29 enter 78
B1CUWJZI0083XOG 05:15:10:27 exit 35
TDRD4FM 05:19:17:50 enter 9
VB5NA 05:18:14:57 exit 87
AY 05:08:23:15 enter 59
T5A2OHJC53WR 05:26:22:06 enter 9
CM0U9YUA12Y 05:30:03:07 enter 76
6D51YFQB 05:10:04:03 enter 44
BKQTNZ9OT61BQ 05:24:03:51 enter 3
1 05:16:22:15 enter 58
1DSRVW3VVCB8SIY 05:23:01:54 enter 51
1DSRVW3VVCB8SIY 05:29:04:59 exit 91
ZZT 05:25:17:40 exit 13
GOXOTET4P3JPR9KSQ5 05:06:11:51 enter 66
CM0U9YUA12Y 05:03:20:04 exit 79
UBB4LYEWM5 05:29:20:07 exit 23
2R27ZSDDLG77OVIT9RJ 05:26:17:07 enter 72
IRN1VCFX8KH 05:10:11:41 enter 7
6D51YFQB 05:10:04:03 enter 44
NVG9YKZPLPLPJ1S2LN1N 05:16:14:55 enter 99
DBUA8 05:29:04:34 enter 69
KHTKQO7F6 05:19:20:25 enter 66
T5A2OHJC53WR 05:16:02:05 enter 62
WA7MZ2EUDTJKCB 05:11:22:20 exit 79
I7LP 05:04:05:35 exit 14
VRQ2ECL 05:14:06:00 exit 31
GV5QEE 05:28:14:00 exit 74
GLBUVL2TPTUCVR8MKMC 05:03:07:47 enter 74
FCP6QN207YMN 05:24:04:40 enter 96
QPM870QV4D1CLWI1 05:26:23:55 enter 48
D 05:05:09:54 exit 31
1 05:28:13:47 enter 32
QPM870QV4D1CLWI1 05:26:23:55 enter 48
QPM870QV4D1CLWI1 05:22:19:53 exit 61
WL 05:17:08:04 exit 78
3H4LI1KVBCX4GM 05:07:23:52 exit 1
5U3BEI 05:04:03:48 exit 27
NVG9YKZPLPLPJ1S2LN1N 05:15:00:22 exit 50
K42FAELL48AHKPVRFY 05:23:01:50 exit 16
MM09ENQ 05:13:22:09 exit 24
Y30EGA6IKO3NGRFZL3IY 05:27:04:47 exit 80
BGEO6D8ZUOG86 05:27:04:27 exit 41
WL 05:24:09:06 enter 12
5U3BEI 05:15:11:29 exit 52
KHTKQO7F6 05:13:16:17 enter 84
6D51YFQB 05:17:01:49 exit 31
93KWIKL 05:01:23:04 enter 77
FCP6QN207YMN 05:24:04:40 enter 96
FCP6QN207YMN 05:16:06:28 enter 4
YJLWF1DYJN 05:23:22:48 exit 11
Y30EGA6IKO3NGRFZL3IY 05:15:11:19 exit 0
LZ 05:01:12:07 exit 82
BOCRA 05:30:14:26 enter 47
PR8OLVNX2SATF4G 05:13:10:29 enter 77
GLBUVL2TPTUCVR8MKMC 05:28:04:58 exit 59
QPM870QV4D1CLWI1 05:22:02:00 enter 55
ZI67765FTJ 05:20:11:16 enter 26
I7LP 05:11:12:46 exit 84
MW4CVD2 05:04:16:21 exit 99
RZ423QQYDTRHE 05:26:09:52 enter 77
YN0NO2YHIAA 05:22:12:47 enter 27
6D51YFQB 05:28:21:22 enter 36
6Z 05:24:13:06 exit 42
YSDV2CMK49I 05:19:19:02 exit 5
J3WZWPO 05:12:10:05 exit 38
TJY1Q 05:22:23:33 enter 25
TYQTZDE 05:24:22:06 enter 52
AY 05:19:01:46 exit 97
JTLC2 05:09:23:27 exit 64
3112OV4J6 05:01:10:28 exit 9
TDDBGG2NDZH 05:28:03:03 enter 16
VB5NA 05:08:07:32 enter 15
22WHS9NTB3Y0TUKY 05:29:14:46 exit 99
22WHS9NTB3Y0TUKY 05:03:19:46 exit 89
AY 05:29:09:29 exit 81
HBQ 05:08:06:52 enter 44
ZBCXBO9JBXN 05:11:23:00 enter 52
4RTV 05:12:00:24 exit 90
BOCRA 05:15:04:09 exit 2
9WJ 05:05:01:14 exit 36


and output is..

1DSRVW3VVCB8SIY $3.80
6D51YFQB $3.65
AY $12.12
GLBUVL2TPTUCVR8MKMC $4.28
QPM870QV4D1CLWI1 $3.18
VB5NA $8.76

........................................
i don't know why WA...
Plz help me..

[Darko]

There is already a thread about this problem, why did you make a new one?
http://online-judge.uva.es/board/viewtopic.php?t=3887

That output is correct.

[nnicool]

this test data is same one...

[iran]

Input:

1

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20
A 01:01:23:11 exit 10
A 01:02:00:00 exit 20
A 01:02:00:01 enter 20
A 01:02:01:00 exit 10

Output:
A $6.00

[deadangelx]

I doubt this test case

Code: Select all

1

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20  -----(1)
A 01:01:23:11 exit 10    ------(2)
A 01:02:00:00 exit 20    -------(3)
A 01:02:00:00 enter 30  --------(4)
A 01:02:01:00 exit 10    -------(5)

in this case, the answer pairs should be (1),(2) and (4),(5) or only (1),(2) ?

thx

[DD]

I doubt this test case

Code: Select all

1

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20 -----(1)
A 01:01:23:11 exit 10 ------(2)
A 01:02:00:00 exit 20 -------(3)
A 01:02:00:00 enter 20 --------(4)
A 01:02:01:00 exit 10 -------(5)

in this case, the answer pairs should be (1),(2) and (4),(5) or only (1),(2) ?

thx

You should consider both pairs {(1), (2)} and {(4),(5)} in this input set.
BTW, I just got A.C. and had to say this problem is tricky when a vehicle occurs many times.

In the following are input sets if you don't know how to do when a vehicle occurs many times:

Code: Select all

3

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20
A 01:03:23:11 exit 40
A 01:02:00:01 enter 20
A 01:02:01:00 exit 10

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20
A 01:01:23:11 exit 40
A 01:02:00:01 enter 20
A 01:02:01:00 exit 10

10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
A 01:01:23:10 enter 20
A 01:02:00:00 exit 20
A 01:02:00:01 enter 20
A 01:02:01:00 exit 10

Output:

Code: Select all

A $4.00

A $7.00

A $5.00