#P11764. 「KFCOI Round #1」生成序列
「KFCOI Round #1」生成序列
题目背景
题目描述
你需要生成一个长度为 的非负整数序列 。
满足 条限制,第 条限制形如:
- 若将 修改为 ,则序列中恰好有 个区间满足修改前后,其区间和的变化量不超过 。
各个限制间独立,即修改操作没有真的执行。
为了防止序列中的数过大,如果存在 ,则认为序列 不满足限制。
若有多个满足条件的序列,输出任意一个即可。若无解,输出 -1
。
输入格式
本题输入均为正整数。
第一行一个数 。
对于每组数据:
第一行两个数 。
接下来 行,每行四个数 。
输出格式
本题使用 SPJ。
每组数据一行。
若有解,输出 个非负整数,第 个数代表 。
若无解,输出 -1
。
2
4 4
4 1 6 1
3 20 10 12
2 3 4 4
4 9 10 10
3 2
1 2 6 0
1 3 6 0
6 20 18 4
-1
提示
样例解释
对于第一组数据:
,,,。
若将 改为 ,则有 个区间的区间和变化量不超过 ,分别为:
[1,1],[1,2],[1,3],[2,2],[2,3],[3,3]
。
若将 改为 ,则所有区间的区间和变化量均不超过 。
若将 改为 ,则有 个区间的区间和变化量不超过 ,分别为:
[1,1],[3,3],[3,4],[4,4]
。
若将 改为 ,则所有区间的区间和变化量均不超过 。
可能存在其他解,输出任意一个即可。
对于第二组数据,可以证明没有符合条件的序列满足限制。
数据范围
本题采用捆绑测试。
- Subtask 1(10 points):,,,。
- Subtask 2(10 points):。
- Subtask 3(10 points):。
- Subtask 4(20 points):,,,。
- Subtask 5(50 points):无特殊限制。
对于所有测试数据,,,,,,,。