LA 3529

From Algorithmist
Jump to navigation Jump to search

LA 3529 - Widget Factory[edit]

Summary[edit]

There are N types of widgets, each type takes a fixed number of days (between 3 and 9) to be produced. In the factory there were several workers. For each of them we know the information "He started on weekday X, produced c1 widgets of type t1, ..., ck widgets of type tk and finished on weekday Y". The task is to determine the production time for each of the widgets.

There may be inputs where there is no answer or more than one answer, in these cases you just have to output a corresponding message.

Explanation[edit]

Note that if we want to know the number of days D a widget takes to be completed, it is enough to determine (D modulo 7).

Each worker's information can be translated into a linear congruence modulo 7. The resulting set of equations can be solved using Gaussian elimination.

Notes[edit]

Note that all operations when solving the set of equations are done modulo 7. Seven (the number of days in a week) is a prime number. Thus (the set {0,1,2,3,4,5,6} with addition and multiplication modulo 7) is a field. In other words, each number other than 0 has a multiplicative inverse, and thus we can divide in . E.g. in 2*4 = 1, so instead of dividing a number by 4 we can multiply it by 2.

Input[edit]

2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE
3
1 MON WED
3
0 0

Output[edit]

8 3
Inconsistent data.