## 10881 - Piotr's Ants

Moderator: Board moderators

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

### 10881 - Piotr's Ants

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..

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

i'm confused,
Sorry For My Poor English..

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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
Contact:
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
Ami ekhono shopno dekhi...
HomePage

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

### hmm,......

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

thank you, all.

i rewrote my source code and finally got AC

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

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am
what's the method used for this problem?
I think simple simulation can cause TLE

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

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

### Re: 10881 - Piotr's Ants

Can you give more hints?

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

### Re: 10881 - Piotr's Ants

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

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

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
My signature:
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

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

#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

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...