小学数学题
题目背景
露米娅:我来先考你一道小学数学题吧!
琪露诺:好!小学的题我肯定都会!
题目描述
露米娅:有 $ n $ 只妖精要跨过雾之湖,由于湖边大雾弥漫,妖精们看不清湖到底有多大,不想从边上绕过去。
湖上有一~~条船~~个传送器,且这个传送器每次只能载 $ r $ 只妖精跨过湖面(注意传送器可以同时把两侧的妖精分别运到对岸,但每次运送的总妖精数不能超过 $ r $ )。
这些妖精还很喜欢搞事,所以在任何时刻,都需要满足一些条件,其中第一种条件有 $ m_1 $ 个,第二种条件有 $ m_2 $ 个。
第一种条件形如 妖精 $ a $ 和妖精 $ b $ 必须要在湖的同一侧;
第二种条件形如 当妖精 $ a $ 在湖的一侧时,妖精 $ b $ 和妖精 $ c $ 不能同时在湖的另一侧。
现在给出这些条件,求:
1. 至少需要传送器几次才能让所有妖精到湖的对岸
2. 在保证次数最少的前提下,求过河方案数
输入输出格式
输入格式
第一行四个整数 $ n , m_1 , m_2 , r $
接下来 $ m_1 $ 行每行2个整数 $ a , b $,代表第一种条件
接下来 $ m_2 $ 行每行3个整数 $ a , b , c $, 代表第二种条件
输出格式
两个整数,分别为最少使用传送器次数和方案数,用空格分隔
若无法全部过河,输出"-1 0"(不含引号)
输入输出样例
输入样例 #1
1 0 0 1
输出样例 #1
1 1
输入样例 #2
5 0 0 2
输出样例 #2
3 90
输入样例 #3
3 1 0 1
1 2
输出样例 #3
-1 0
说明
对于 $ 30 \% $ 的数据, $ n \leq 10 $
对于另外 $ 10 \% $ 的数据, $ m_1 = m_2 = 0 $
对于 $ 100 \% $ 的数据, $ a,b,c \leq n \leq 15 $, $ m_1 , m_2 \leq 50 $, $ r \leq 10^9 $
请不要相信洛谷评测机的速度,如果得了80分以上,可以等人少的时候再交一次。但如果得了60分以下,说明可能写的不是正解,就不要再虐萌萌哒评测机啦