Page 1 of 1
617 - Nonstop Travel
Posted: Wed Sep 11, 2002 12:17 am
by 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]
617
Posted: Mon Jun 23, 2003 12:46 pm
by 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]
Posted: Sat Jun 28, 2003 10:32 pm
by 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!
617 -(Non stop travel )Help me plz (WA)
Posted: Mon Apr 24, 2006 1:38 pm
by 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.
Posted: Wed Jan 17, 2007 11:11 am
by jurajz
Thank you tuman, with help of your I/O I found out my error... I have AC now
617(Nonstop Travel) WA!
Posted: Thu Jan 10, 2008 5:40 am
by 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;
}
Re: 617(Nonstop Travel) WA!
Posted: Thu Jan 10, 2008 7:48 am
by dma
it's so...
if I compile it without argument -O2, I got the AC! Why?
Re: 617 - Nonstop Travel
Posted: Mon May 28, 2012 4:12 am
by 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
Re: 617 - Nonstop Travel
Posted: Fri Jun 01, 2012 1:03 am
by 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:
Re: 617 - Nonstop Travel
Posted: Mon Jun 04, 2012 3:51 am
by leelove
I got AC finally!
I just change a line:
from:
to:
amazing! It must be the float error precision problem.