10881 - Piotr's Ants

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

10881 - Piotr's Ants

Post by wook » Sun Aug 07, 2005 8:30 am

I have solved this problem
(i think it would be enough fast to ACCEPT, if my output is correct)
but i got WA(WRONG ANSWER) in 0.227 sec

i can't find critical input data that makes different between my output and correct output,
but for it when more than two ants are at the same location.

that is, can this input exist, if more than two ants are at the same start location?
if it exist, what do i have to output?

Code: Select all

10 1 3
3 L
3 R
3 L
if there is a input like above,

i think

2 Turning
2 Turning
4 R

2 Turning
4 R
2 Turning

..etc..

is correct answer,

but the ants that is located at 2 are not TURNING!!

i'm confused,
please help me.
Sorry For My Poor English.. :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Aug 07, 2005 10:19 am

Two ants are never at the same starting location.

Make sure that you print the ants in the correct order.
If only I had as much free time as I did in college...

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 09, 2005 11:52 am

What is the output of the following input set?

Input:

Code: Select all

6
10 1 2
3 R
4 L
10 1 2
1 R 
2 L
10 1 2
1 R 
3 L
3 2 2
1 R
3 L
3 1 2
1 R 
3 L
10 2 3
1 R
2 R
3 R
Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

hmm,......

Post by wook » Tue Aug 09, 2005 3:13 pm

my output for input above :

for
Case #1:
3 L
4 R

Case #2:
1 L
2 R

Case #3:
2 Turning
2 Turning

Case #4:
1 L
3 R

Case #5:
2 Turning
2 Turning

Case #6:
3 R
4 R
5 R
isn't it correct?
Sorry For My Poor English.. :)

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

finally AC

Post by wook » Wed Aug 10, 2005 5:24 pm

thank you, all.

i rewrote my source code and finally got AC :)

it's fast ! and ranked first :P
Sorry For My Poor English.. :)

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword » Thu Dec 29, 2005 2:32 pm

what's the method used for this problem?
I think simple simulation can cause TLE

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Dec 29, 2005 3:26 pm

Sorting

wahab
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

Re: 10881 - Piotr's Ants

Post by wahab » Fri Jan 09, 2009 6:52 pm

Can you give more hints?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10881 - Piotr's Ants

Post by Angeh » Fri Feb 19, 2010 10:21 am

any hints to solve this problem ....
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: 10881 - Piotr's Ants

Post by .. » Wed Mar 17, 2010 8:07 am

Hope the one asking about hint is still interesting in this problem.

spoiler alert














Consider we have 3 ants
Ant_a at position P_a, facing R
Ant_b at position P_b, facing R
Ant_c at position P_c, facing L
with P_a < P_b < P_c

If you simulate the scenario you will find that the ant Ant_a will turn around at time (P_c - P_a)/2, just like the ant_b doesn't exist!
When generalize the idea you will find that you can imagine the ant will not turn around, but pass through each other at collision. So the remaining is how to map the pass-through scenario to the turn-around scenario. This part I leave it to you to have fun :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10881 - Piotr's Ants

Post by Angeh » Thu Mar 18, 2010 2:26 pm

Thanks for your hints ....:)
i konw these facts, but i'm cofused how to use them ...
i have thought about it for 2 days but still .... nothing ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

messiNayan
New poster
Posts: 7
Joined: Thu Feb 20, 2014 7:07 pm

Re: 10881 - Piotr's Ants

Post by messiNayan » Sun Feb 26, 2017 9:33 am

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

using namespace std;

#define SIZE 10000

typedef struct
{
char direction;
int ant_no;
double location;
}STATUS;

typedef struct
{
int r;
int l;
}PAIR;

bool compare1(STATUS i, STATUS j)
{
return i.location < j.location;
}

bool compare2(STATUS i, STATUS j)
{
return i.ant_no < j.ant_no;
}

int main(void)
{
int i, j, l, n, case_no, num_of_cases, r_index, r_location;
double t, dist, temp_dist;

STATUS ants_status[SIZE];
PAIR pair[500];

scanf("%d", &num_of_cases);

case_no = 1;
while (case_no <= num_of_cases)
{
memset(ants_status, 0, SIZE);
scanf("%d%lf%d", &l, &t, &n);
i = 0;
while (i < n)
{
scanf("%lf %c", &ants_status.location, &ants_status.direction);
ants_status.ant_no = i;
i++;
}
sort(ants_status, ants_status + n, compare1);




while (1)
{
i = 0;
j = 1;
r_location = -1;
temp_dist = 0xffff - 1;
dist = 0xffff - 1;
memset(pair, 0, 500);

while (i < n)
{
if (ants_status.direction == 'R')
{
r_index = i;
r_location = ants_status.location;
}
else
{
if (r_location != -1)
{
temp_dist = (ants_status.location - r_location) / 2.0;
r_location = -1;

if (temp_dist < dist)
{
dist = temp_dist;
pair[0].r = r_index;
pair[0].l = i;

}
else if (temp_dist == dist)
{
pair[j].r = r_index;
pair[j].l = i;
j++;
}
}
}
i++;
}

if (dist == t)
{
for (i = 0; i < n; i++)
{
if (ants_status.direction == 'R')
ants_status.location += dist;
else
ants_status.location -= dist;

}

for (i = 0; i < j; i++)
{
ants_status[pair.l].direction = 'T';
ants_status[pair[i].r].direction = 'T';
}
break;
}
else if (dist < t)
{
t -= dist;
for (i = 0; i < n; i++)
{
if (ants_status[i].direction == 'R')
ants_status[i].location += dist;
else
ants_status[i].location -= dist;
}

for (i = 0; i < j; i++)
{
ants_status[pair[i].l].direction = 'R';
ants_status[pair[i].r].direction = 'L';
}

dist = 0xffff;

}
else
{
for (i = 0; i < n; i++)
{
if (ants_status[i].direction == 'R')
ants_status[i].location += t;
else
ants_status[i].location -= t;

}
break;
}
}

sort(ants_status, ants_status + n, compare2);

printf("Case #%d:\n", case_no);

for (i = 0; i < n; i++)
{
if (ants_status[i].location > l)
printf("Fell off\n");
else
{
if (ants_status[i].direction == 'T')
printf("%d Turning\n", (int)ants_status[i].location);
else
printf("%d %c\n", (int)ants_status[i].location, ants_status[i].direction);

}
}

case_no++;
}



return 0;
}
I think my algorithm is faster than trivial solution but still getting time limit exit

feodorv
New poster
Posts: 5
Joined: Mon Jun 06, 2016 12:42 pm

Re: 10881 - Piotr's Ants

Post by feodorv » Mon Feb 27, 2017 2:13 pm

messiNayan wrote:I think my algorithm is faster than trivial solution but still getting time limit exit
Sorry, your algorithm is not fast enough. In truth it is very slow. Please, try my input on uDebug...

Post Reply

Return to “Volume 108 (10800-10899)”