## 617 - Nonstop Travel

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

### 617 - Nonstop Travel

Hello, can anybody help me out
on this problem?
In my code, I assumed the times are
real numbers because I got a lot of
WA's assuming they were ints.

Thanks for any help.
Broderick

[c]
#include <stdio.h>
#include <math.h>

typedef struct {
double loc;
double g,y,r;
} light_t;

int n;
light_t light[6];

int checkspeed(int s) {
int i,t;
double v = (double)s / 3600;
for (i=0; i<n; i++) {
t = light.loc/v;
t = fmod(t, light.g + light.y + light.r);
if (t > light.g + light.y + 1e-7) return 0;
}
return 1;
}

int main () {
int i,j,ngood,good[71],cnum=1;

while (scanf("%d ", &n)==1 && n!=-1) {
memset(good, 0, sizeof(good));
for (i=0; i<n; i++)
scanf("%lf %lf %lf %lf ",&light.loc, &light.g, &light.y, &light.r);
for (i=30,ngood=0; i<=60; i++) {
if (checkspeed(i)) {
ngood++;
good[i] = 1;
}
}
printf("Case %d: ", cnum++);
if (!ngood) printf("No acceptable speeds.");
else {
for (i=30; !good[i]; i++) ;
if (!good[i+1]) {
printf("%d",i);
i++;
}
else {
for (j=i+1;good[j]; j++) ;
printf("%d-%d", i,j-1);
i=j;
}
for (; i<=60; ) {
while (!good[i] && i<=60) i++;
if (i>60) break;
for (j=i,i++; good[i] && i<=60; i++) ;
if (j==i+1) printf(", %d", j);
else printf(", %d-%d", j,i-1);
}
}
printf("\n");
}
return 0;
}
[/c]

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### 617

Hi,

I got a WA for the following code.

I have a strong feeling that the error is due to inaccuracy in using floating point real numbers. However, the possibility of a flawed algorithm must not be ruled out.

I would appreciate any help provided, as well as sample test cases. Thank you in advance.

[cpp]#include <fstream.h>
#include <string.h>

#define ERROR 0.000001

#ifdef ONLINE_JUDGE
#define fin cin
#define fout cout
#else
ifstream fin("input.dat");
ofstream fout("output.dat");
#endif

bool can[31];
int nlight;
double dist[6], green[6], yellow[6], red[6];

bool input() {
int i;

fin >> nlight;
if (nlight < 0)
return false;

for (i = 0; i < nlight; i++) {
fin >> dist >> green >> yellow >> red;
green /= 3600;
yellow /= 3600;
red /= 3600;
}

return true;
}

void process(int ncase) {
bool acc;
double speed, time;
int i, j;

memset(can, -1, sizeof(can));
for (i = 0; i <= 30; i++) {
speed = (double)((double)i + (double)30);
for (j = 0; j < nlight; j++) {
time = dist[j] / speed;
while (time - (green[j] + yellow[j] + red[j]) > ERROR)
time -= green[j] + yellow[j] + red[j];
if (time - (green[j] + yellow[j]) > ERROR) {
can = false;
break;
}
}
}

fout << "Case " << ncase << ':';
acc = false;
for (i = 0; i <= 30; i++) {
if (can) {
for (j = i; j <= 30; j++)
if (!can[j])
break;
j--;
if (acc)
fout << ',';
if (i == j)
fout << ' ' << (i + 30);
else
fout << ' ' << (i + 30) << '-' << (j + 30);
i = j + 1;
acc = true;
}
}
if (!acc)
fout << " No acceptable speeds.";
fout << endl;
}

int main() {
int ncase = 1;
while (input())
process(ncase++);
return 0;
}
[/cpp]

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Try this input / output:
Input:

Code: Select all

``````1
5.5 40 8 25

3
10.7 10 2 75
12.5 12 5 57
17.93 15 4 67

0

1
10 1 1 0

1
10 1 1 1

-1
``````
Output:

Code: Select all

``````Case 1: 30, 32-33, 36-38, 41-45, 48-54, 59-60
Case 2: No acceptable speeds.
Case 3: 30-60
Case 4: 30-60
Case 5: 30-33, 36-37, 40, 43, 45, 47-48, 50-51, 53-57, 59-60
``````
JP!

tuman
New poster
Posts: 24
Joined: Sat Oct 22, 2005 7:30 pm
Location: CUET
Contact:

### 617 -(Non stop travel )Help me plz (WA)

hi all, I need help in this problem.
I am continuously getting wrong answer in this problem.
But i could n't find out my fault in this problem. I hv tried several test cases but all the output is correct as far as my concern.

Give a look at my code:
//code deleted after accepted

// I dont know why. Everytime i post my w.a code here and very soon i find my fault by my own. //
Here is some input and output of my accepted code,if u get pass all of that then i assure that u will get ac.

input:
1
5.5 40 8 25

3
10.7 10 2 75
12.5 12 5 57
17.93 15 4 67

0

1
10 1 1 0

1
10 1 1 1

1
5.5 40 8 25
3
10.7 10 2 75
12.5 12 5 57
17.93 15 4 67

4
1.0 10 1 10
2.0 10 1 10
3.0 10 1 10
4.0 10 1 10

5
15.1 1 1 1
10.2 10 20 30
8.95 30 5 30
25.0 10 1 10
50.0 12 2 35

6
25.0 30 1 95
10.5 10 10 10
25.1 10 5 30
16.7 6 50 2
98.1 1 1 100
37.25 15 6 38

output:

Case 1: 30, 32-33, 36-38, 41-45, 48-54, 59-60
Case 2: No acceptable speeds.
Case 3: 30-60
Case 4: 30-60
Case 5: 30-33, 36-37, 40, 43, 45, 47-48, 50-51, 53-57, 59-60
Case 6: 30, 32-33, 36-38, 41-45, 48-54, 59-60
Case 7: No acceptable speeds.
Case 8: 34, 42, 55-57
Case 9: 54, 60
Case 10: No acceptable speeds.

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia
Thank you tuman, with help of your I/O I found out my error... I have AC now

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

### 617(Nonstop Travel) WA!

please give me more I/O! thanks!

Code: Select all

``````#include <iostream>
#include <vector>
using namespace std;

static const int lowest_speed = 30;
static const int heighest_speed = 60;

class traffic_t{
double _l;
int _g, _y, _r;
public:
bool can_pass(int speed){
double sec = _l*3600/speed;
return (sec - (int)(sec/(_g+_y+_r))*(_g+_y+_r)) <= _g+_y;
}
friend istream& operator>>(istream& in, traffic_t& tra){
in>>tra._l>>tra._g>>tra._y>>tra._r;
}
};

static void _fmt_print_(const vector<int>& nostop_speeds){
static int id = 1;

cout<<"Case "<<id++<<": ";
if(nostop_speeds.empty()){
cout<<"No acceptable speeds."<<endl;
return;
}

int i=0;
bool has_comma = false;
while(i<nostop_speeds.size()){
int speed = nostop_speeds.at(i);
int l = speed, h = speed;
while(++i < nostop_speeds.size() && (h+1 == nostop_speeds.at(i)))
h++;
if(has_comma) cout<<", ";
has_comma = true;
if(l == h)cout<<l;
else cout<<l<<"-"<<h;

}
cout<<endl;
}

int main(int argc, char** argv){
int n;
while(cin>>n && n>=0){
vector<traffic_t> v(n);
vector<int> nostop_speeds;

for(int i=0; i<n; i++)
cin>>v[i];

for(int speed = lowest_speed; speed<=heighest_speed; speed++){
bool can_pass = true;

for(int i=0; i<n; i++)
if(!v[i].can_pass(speed)){
can_pass = false;
break;
}
if(can_pass) nostop_speeds.push_back(speed);
}
_fmt_print_(nostop_speeds);
}
return 0;
}

``````

dma
New poster
Posts: 8
Joined: Wed Dec 12, 2007 1:05 pm

### Re: 617(Nonstop Travel) WA!

it's so...
if I compile it without argument -O2, I got the AC! Why?

leelove
New poster
Posts: 2
Joined: Sat May 26, 2012 8:19 pm

### Re: 617 - Nonstop Travel

Code: Select all

``````/* Q617 Nonstop Travel */
got AC, removed
``````
Last edited by leelove on Mon Jun 04, 2012 3:52 am, edited 1 time in total.

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

### Re: 617 - Nonstop Travel

Input:

Code: Select all

``````5
15.1 1 1 1
10.2 10 20 30
8.95 30 5 30
25.0 10 1 10
50.0 12 2 35

-1``````
AC output:

Code: Select all

``Case 1: 54, 60``
Check input and AC output for thousands of problems on uDebug!

leelove
New poster
Posts: 2
Joined: Sat May 26, 2012 8:19 pm

### Re: 617 - Nonstop Travel

I got AC finally!
I just change a line:
from:

Code: Select all

``arrivetime = L[i]/x*3600;``
to:

Code: Select all

``arrivetime = L[i]*3600/x;``
amazing! It must be the float error precision problem.