#P1911. 防线

    ID: 1007 传统题 文件IO:tk 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>进阶指南0x08 基本算法 总结与练习习题

防线

防线 (defender.pas/c/cpp) 题目描述 lsp学习数学竞赛 的时候受尽了同仁们 的鄙视,终于有一 天……受尽屈辱的 lsp 黑化成为了黑暗英雄 Lord lsp。就如同中二 漫画的情节一样, Lord lsp 打算毁掉这 个世界。数学竞赛界 的精英 lqr 打算阻止 Lord lsp的阴谋,于是 她集合了一支由数学 竞赛选手组成的超级行动队。由于队员们个个都智商超群,很快,行动队便来到了 Lord lsp 的黑暗城堡的下方。 但是,同样强大的 Lord lsp在城堡周围布置了一条“不可越过”的坚固防线。防线由很 多防具组成,这些防具分成了 N组。我们可以认为防线是一维的,那么每一组防具都分布 在防线的某一段上,并且同一组防具是等距离排列的。也就是说,我们可以用三个整数 S, E和 D来描述一组防具,即这一组防具布置在防线的 S,S + D,S + 2D,...,S + KD(K∈ Z,S + KD≤E,S + (K + 1)D>E)位置上。 黑化的 Lord lsp设计的防线极其精良。如果防线的某个位置有偶数个防具,那么这个位 置就是毫无破绽的(包括这个位置一个防具也没有的情况,因为 0也是偶数) 。只有有奇数 个防具的位置有破绽,但是整条防线上也最多只有一个位置有奇数个防具。作为行动队的队 长,lqr要找到防线的破绽以策划下一步的行动。但是,由于防具的数量太多,她实在是不 能看出哪里有破绽。作为 lqr可以信任的学弟学妹们,你们要帮助她解决这个问题。 输入格式 输入文件的第一行是一个整数 T,表示有 T组互相独立的测试数据。 每组数据的第一行是一个整数 N。 之后 N行,每行三个整数 Si,Ei,Di,代表第 i组防具的三个参数。 输出格式
对于每组测试数据,如果防线没有破绽,即所有的位置都有偶数个防具,输出一行 “There’s no weakness.” (不包含引号) 否则在一行内输出两个空格分隔的整数 P和 C,表示在位置 P有 C个防具。当然 C应 该是一个奇数。 样例输入 3 2 1 10 1 2 10 1 2 1 10 1 1 10 1 4 1 10 1 4 4 1 1 5 1 6 10 1 样例输出 1 1 There’s no weakness. 4 3 数据范围与约定 对于 30% 的数据,满足防具总数不多于 107。 对于 100% 的数据,满足防具总数不多于 108,Si≤Ei,1≤T≤5,N≤200000,0≤Si, Ei,Di≤231-1。