804 - Petri Net Simulation

All about problems in Volume 8. 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
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

804 - Petri Net Simulation

Post by Jan » Mon Aug 22, 2005 11:32 pm

I have solved the problem but getting WA.
Can anyone tell me what should be the output for the following input set...

Input:

Code: Select all

2
1 0
2
-1 2 0
-2 1 0
100
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
100
3
1 0 0
3
-1 2 3 0
-2 1 0
-3 1 0
1
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
9
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
10
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
8
0
My code returns
Output:

Code: Select all

Case 1: still live after 100 transitions
Places with tokens: 1 (1)

Case 2: dead after 9 transitions
Places with tokens: 2 (1)

Case 3: still live after 1 transitions
Places with tokens: 2 (1) 3 (1)

Case 4: still live after 9 transitions
Places with tokens: 2 (1)

Case 5: dead after 9 transitions
Places with tokens: 2 (1)

Case 6: still live after 8 transitions
Places with tokens: 1 (1)
Thanks in advance.
Last edited by Jan on Tue Aug 23, 2005 12:26 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

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

Post by Jan » Tue Aug 23, 2005 12:24 pm

Finally got accepted. :D

The output given is correct...
Ami ekhono shopno dekhi...
HomePage

imnew
New poster
Posts: 5
Joined: Sun Feb 12, 2006 6:37 am

How to make it fast?

Post by imnew » Sun Feb 12, 2006 9:57 am

People are solving this within a pretty small time limit........................I could get no better idea than brute force simulation.........Any idea?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Mar 28, 2006 10:24 am

I keep getting TLE for this problem too.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Mar 31, 2006 5:23 am

The 10 sec time limit might be too tight for this problem.

lpereira
New poster
Posts: 5
Joined: Wed Nov 16, 2005 7:35 pm
Location: Campinas - SP - Brazil
Contact:

Post by lpereira » Fri May 26, 2006 9:11 pm

Brute force will do it. Remember that you can greedly get the first active transition you find. This should speed up. Also, if one of the imputs do not suffice, you can also discard that transition, since it's surely not active.

p137
New poster
Posts: 1
Joined: Mon Jul 10, 2006 9:54 am

Post by p137 » Mon Jul 10, 2006 10:05 am

My program returns exactly the same output, but I still get "wrong answer". Has anybody an idea, what kind of reason this could have? (Is it important whether I print a blank line before/after output?)
@Jan: What did you do to get accepted?

Thanks in advance!
p137

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

Post by Jan » Wed Oct 25, 2006 12:19 am

p137 wrote:@Jan: What did you do to get accepted?
I just simulate the process efficiently. May be you have missed this line
The input data will be selected to guarantee the uniqueness of the correct output displays.
Hope it helps :D .
Ami ekhono shopno dekhi...
HomePage

lucaskt
New poster
Posts: 3
Joined: Thu Mar 15, 2007 1:03 am

Re: 804 - Petri Net Simulation

Post by lucaskt » Fri Nov 21, 2008 11:28 pm

I can't find any test cases that make this fail, but am still getting WA, any ideas?

Code: Select all

#include <stdio.h>

int main() {
	int mi[120][120];
	int mc[120][120];
	int s[120];
	int c, d, f, g, n, t;

	int i, j, k;

	scanf(" %d", &n);
	g = 1;
	while (n != 0) {
		if (g > 1) putchar('\n');

		for (i = 0; i < n; i++) {
			scanf(" %d", &s[i]);
		}
		scanf(" %d", &t);

		for (i = 0; i < n; i++) {
			for (j = 0; j < t; j++) {
				mc[i][j] = mi[i][j] = 0;
			}
		}

		for (i = 0; i < t; i++) {
			scanf("%d", &k);
			while (k != 0) {
				if (k < 0) {
					mi[-k - 1][i]++;
					mc[-k - 1][i]--;
				} else {
					mc[k - 1][i]++;
				}
				
				scanf("%d", &k);
			}
		}

		scanf(" %d", &f);

		c = 0;
		while (c < f) {
			d = 0;
			for (i = 0; i < t; i++) {
				for (j = 0; j < n; j++) {
					if (s[j] < mi[j][i]) {
						break;
					}
				}

				if (j == n) {
					for (j = 0; j < n; j++) {
						s[j] += mc[j][i];
					}

					c++;
					d = 1;
					if (c == f) goto end;
				}
			}
			if (!d) {
				break;
			}
		}

end:
		if (!d) {
			printf("Case %d: dead after %d transitions\n", g++, c);
		} else {
			printf("Case %d: still live after %d transitions\n", g++, c);
		}

		printf("Places with tokens:");
		for (i = 0; i < n; i++) {
			if (s[i] > 0) {
				printf(" %d (%d)", i + 1, s[i]);
			}
		}
		putchar('\n');

		scanf(" %d", &n);
	}
	return 0;
}
I've tried the set Jan sent, and it got the same answers. I also tried this (appended to Jan's set):

Code: Select all

2
2 0
2
-1 2 2 0
-2 -2 -2 1 0
10

2
2 0
2
-1 2 2 0
-2 -2 -2 1 0
6
expecting:

Code: Select all

Case 7: dead after 6 transitions
Places with tokens: 2 (2)

Case 8: still live after 6 transitions
Places with tokens: 2 (2)
and it worked, but the judge still gives me WA.

Thanks in advance,
Lucas

jurajz
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 804 - Petri Net Simulation

Post by jurajz » Mon Oct 23, 2017 11:22 pm

I had many WA's because I didn't assume, that NT (number of transitions) can be zero. After this assumption, I had AC.

Sample input:

Code: Select all

2
1 0
2
-1 2 0
-2 1 0
100
2
0 0
2
-1 2 0
-2 1 0
0
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
100
2
0 0
2
-1 2 0
-2 1 0
0
0
Correct output:

Code: Select all

Case 1: still live after 100 transitions
Places with tokens: 1 (1)

Case 2: still live after 0 transitions
Places with tokens:

Case 3: dead after 9 transitions
Places with tokens: 2 (1)

Case 4: still live after 0 transitions
Places with tokens:


Post Reply

Return to “Volume 8 (800-899)”