Partitioning Tiles with Distinct Runs¶
Estimated time limit: 1.5 seconds. Memory limit: 128 MB.
The limit is 2 times the slowest median runtime of the reference program on the target platform, rounded up to a multiple of \(0.5\) seconds. See the evaluation environment.
Story¶
A workshop receives batches of tiles marked with a type and a number. Its organizer wants to pack every tile into prescribed groups, using each distinct run at most once.
(This story was rewritten by GPT-6.)
Formal Problem Statement¶
There are \(m\) tile types. Each type may have numbers \(1,\ldots,n\) . Starting with no tiles, you receive \(k\) batches. Batch \(i\) contains \(a_i\) tiles of type \(b_i\) and number \(c_i\) . Identical tiles are accumulated regardless of which batch supplied them.
Decide whether every tile can be used exactly once in a partition into the following groups:
- A run consists of three or five consecutive numbers of one type, with exactly one tile of each number. Runs must be pairwise distinct: a fixed combination of type, starting number and length may occur at most once.
- An identical-tile group consists of three or four tiles with the same type and number. Any number of identical copies of such a group is allowed.
Either category may contain zero groups. Runs of different types or lengths are distinct. Determine whether a valid partition exists.
Input Format¶
The first line contains \(n,m,k\) . Each of the next \(k\) lines contains \(a_i,b_i,c_i\) .
Output Format¶
Print 1 if a valid partition exists, or 0 otherwise.
Samples¶
Sample 1¶
Input¶
5 1 5
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
Output¶
1
Sample 2¶
Input¶
3 1 3
2 1 1
2 1 2
2 1 3
Output¶
0
Sample 3¶
Input¶
1 2 3
1 1 1
2 1 1
4 2 1
Output¶
1
Sample Explanation¶
The first sample uses one run of length five. In the second, the only possible run starts at one and has length three; it may be used only once, leaving three tiles that cannot form a valid group. In the third, the first two batches combine into an identical triple, and the four tiles of the other type form their own group.
Constraints and Guarantees¶
\(1\le n,m,k\le5\times10^6\) , \(1\le a_i\le10^9\) , \(1\le b_i\le m\) , \(1\le c_i\le n\) .
| Score | Additional constraints |
|---|---|
| 100% | None |