617 - Nonstop Travel

[broderic]

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]

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]

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]

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]

Thank you tuman, with help of your I/O I found out my error... I have AC now

[dma]

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]

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

[leelove]

I pass the data posted here, but I still got WA, why? Please help me!

Code: Select all

/* Q617 Nonstop Travel */
got AC, removed

[brianfry713]

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

[leelove]

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.