黄牛の争

ID: 6344

远端评测题

1000~5000ms

500MiB

尝试: 0

已通过: 0

难度: 6

上传者:

root

标签>

2021

Special Judge

O2优化

洛谷月赛

题目背景

Source：天空之城

本题背景中「黄牛」仅代指某游戏中的一种怪物，与一般含义的「黄牛」无关。

本题「推荐题目」三灰一黑，但不太能说明本题难度和他们差不多（

相传在很久很久之前梅兰德大陆上空漂浮着一座天空之城，是当时财富、力量、荣誉中心，突然有一天再也不见踪影。

如今已多个世纪不见痕迹的天空之城突然出现，王国的勇士去探索一番，但是飞船船票可不是那么好得到的。

飞艇码头的船长是梅德龙 · 杜鲁夫，船长为了牟利要求大家必须买票上船，没有票的旅行者无法登船。

დ琢喵作为一届黄牛的首领——黄牛党，派出了 $q$ 组黄牛买断了梅德龙 · 杜鲁夫的船票。

她以高价卖出这些船票，并通过差价获取巨额利润。

为维护飞艇码头的治安，梅德龙 · 杜鲁夫规定不允许人类和黄牛打架，当然船长并没有规定黄牛之间不可以打架。

题目描述

დ琢喵的手下有两种黄牛：

I 类黄牛「攻击」为 $a$ ，「血量」为 $A$ ；
II 类黄牛「攻击」为 $b$ ，「血量」为 $B$ 。

黄牛之间的作战，满足以下条件：

任意时刻，某一方「血量」 $\le 0$ 时，其对手胜利；
每一回合，「攻击」高者先手；
每回合每方出手一次，造成的伤害即其「攻击」值。

构造的 III 类黄牛应当满足下面条件：

「攻击」数值与 I 类黄牛和 II 类黄牛都不同；
I 类黄牛和 II 类黄牛作战 II 类黄牛胜利；（若输入不满足该条件则应直接输出 -1 -1）
II 类黄牛和 III 类黄牛作战 III 类黄牛胜利；
III 类黄牛和 I 类黄牛作战 I 类黄牛胜利。

请给出一种合法的构造。

题意简述

解方程：（若 $x=\text{true}$ 则 $[x]=1$ 反之 $=0$ ）

\begin{aligned}\left\lceil\frac{A}{b}\right\rceil&+[b<a]\le\left\lceil\frac{B}{a}\right\rceil\\\left\lceil\frac{B}{c}\right\rceil&+[c<b]\le\left\lceil\frac{C}{b}\right\rceil\\\left\lceil\frac{C}{a}\right\rceil&+[a<c]\le\left\lceil\frac{A}{c}\right\rceil\\c&\ne a~\text{and}~c\ne b\end{aligned}

已知 $a,A,b,B$ ，解 $c,C$ 。

输入格式

本题多测。

第一行一个正整数 $q$ 。

接下来 $q$ 行，每行四个正整数 $a,A,b,B$ 。

数据满足 $a\ne b$ 。

输出格式

一共 $q$ 行，每行两个正整数表示你构造的 III 类黄牛的「攻击」数值和「血量」数值，无解时输出 -1 -1。

本题采用 Special Judge，所有满足要求的解均给分。

输入数据 1

输出数据 1

4 1
1 5
2 3

输入数据 2

输出数据 2

输入数据 3

1
1 1 999 999

输出数据 3

-1 -1

提示

样例说明

对于样例 #1，可设 A 是 $(1,5)$ ，B 是 $(2,3)$ ，C 是 $(4,1)$ 。

其中二元组 $(x,y)$ 表示一个「攻击」为 $x$ ，「血量」为 $y$ 的黄牛。

下面的表格展现了 A、B、C 的对战情况，括号中的数字表示每回合开始时它们的「血量」数值。

A 和 B 单挑	B 和 C 单挑	C 和 A 单挑
$\begin{aligned}&\texttt{A(5)~B(3)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(3)~B(2)}\overset{\texttt{A-2~B-1}}{\Rightarrow\Rightarrow}\\&\texttt{A(1)~B(1)}\overset{\texttt{A-2}}{\Rightarrow}\\&\texttt{A}\le\texttt{0~\color{red}B win}\end{aligned}$	$\begin{aligned}&\texttt{B(3)~C(1)}\overset{\texttt{B-4}}{\Rightarrow}\\&\texttt{B}\le\texttt{0~\color{red}C win}\end{aligned}$	$\begin{aligned}&\texttt{A(5)~C(1)}\overset{\texttt{A-4~C-1}}{\Rightarrow\Rightarrow}\\&\texttt{C}\le\texttt{0~\color{red}A win}\end{aligned}$

因此输出剩下一类黄牛即给分。

对于样例 #2：钦定 III 类黄牛攻击力为 $11$ ，已经足以击倒 II 类黄牛，血量为 $11\sim14$ 都可以输给 I 类黄牛。

因此任意输出一组均给分。

对于样例 #3：II 类黄牛十分强大，难以再构造又能击败 II 类黄牛又能输给 I 类黄牛的 III 类黄牛品种。

因此输出 -1 -1 即给分。

数据规模

设 $M=\max\left(a,A,b,B\right)$ ：

Subtask1(10pts)： $M\le10,q=399\underline0$ 。
Subtask2(20pts)： $M\le100,q=399\underline1$ ，数据随机。
Subtask3(10pts)： $M\le10^5,q=99\underline2$ ，数据随机。
Subtask4(20pts)： $M\le10^5,q=99\underline3$ 。
Subtask5(10pts)： $q=399\underline4$ ，数据随机。
Subtask6(30pts)： $q=399\underline5$ ，无特殊限制。
本题根据数据强度设置了不同梯度的时间限制，如果有合理的满分做法被卡了请联系我。

提示：数据组数 $q$ 结尾的数字（ $\underline0,\underline1,\underline2,\underline3,\underline4,\underline5$ ）可能有助于你判断 Subtask 的类型。

对于 $100\%$ 的数据： $1\le q<4000,1\le M\le10^8$ 。

大样例

本题提供符合 Subtask $2,3,5$ 限制的测试用例。

直接编译并运行下面代码，即可得到 E01.in E02.in E03.in 分别是满足 Subtask $2,3,5$ 限制的测试数据。

#include<ctime>
#include<cstdio>
#include<random>
#include<string>
#include<cassert>
#include<cstdlib>
#include<iostream>
#define int long long
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
void printsp(int x){
	print(x), putchar(' ');
}
void println(int x){
	print(x), putchar('\n');
}
char str[] = "E  .in";
const int Buff = 3989;
std::string string;
namespace Data_Maker{
	std::mt19937 rnd(time(0));
	int rand(int l, int r) {
		int x = r - l + 1;
		return (rnd() % x + x) % x + l;
	}
	int a, A, b, B;
	void maker(int subtaskID) {
		int t = Buff + subtaskID;
		if (3 <= subtaskID && subtaskID <= 4)
			t -= 3000;
		println(t);
		if (subtaskID == 2 || subtaskID == 3 || subtaskID == 5) {
			int MOD = 0;
			if (subtaskID == 2) MOD = 100;
			if (subtaskID == 3) MOD = 100000;
			if (subtaskID == 5) MOD = 100000000;
			while (t--) {
				a = rand(1, MOD), A = rand(1, MOD);
				b = rand(1, MOD), B = rand(1, MOD);
				while (b == a)
					b = rand(1, MOD);
				printsp(a), printsp(A), printsp(b), println(B);
			}
		}
	}
	void File(int Test) {
		str[1] = Test / 10 + '0';
		str[2] = Test % 10 + '0';
		freopen(str, "w", stdout);
	}
	void Subtask2() {
		for (int Test = 1; Test <= 1; ++Test) {
			File(Test); maker(2);
		}
	}
	void Subtask3() {
		for (int Test = 2; Test <= 2; ++Test) {
			File(Test); maker(3);
		}
	}
	void Subtask5() {
		for (int Test = 3; Test <= 3; ++Test) {
			File(Test); maker(5);
		}
	}
}
using namespace Data_Maker;
signed main(){
	Subtask2();
	Subtask3();
	Subtask5();
}

另外还提供了下面的 Special Judge，可以编译并通过调用 spj E.in E.out E.ans 来获取返回信息。


#include "testlib.h"
#define int long long
#define inf inf.readLong()
#define ouf ouf.readLong()
#define ans ans.readLong()
bool win(int a, int A, int b, int B){
  int x = 0, f = 1;
  if (a < b)
    a ^= b ^= a ^= b, A ^= B ^= A ^= B, f *= -1;
  while (1) {
    if (B - a <= 0) {
      x = 1;
      break;
    }
    if (A - b <= 0) {
      x = -1;
      break;
    }
    B -= a, A -= b;
  }
  x *= f;
  return x < 0;
}
signed main (signed argc, char**argv) {
  registerTestlibCmd(argc, argv);
  int q = inf;
  for (int t = 1; t <= q; ++t) {
    int a = inf, A = inf, b = inf, B = inf, c = ouf, C = ouf, d = ans, D = ans;
    if (d == -1 && c == -1 && C == -1)
      continue;
    if (c == a)
      quitf (_wa, "Test #%lld, a cannot equal to c!", t);
    if (c < 1 || C < 1)
      quitf (_wa, "Test #%lld, cannot print negative numbers!", t);
    if (!win(c, C, a, A))
      quitf (_wa, "Test #%lld, A cannot beat C!", t);
    if (!win(b, B, c, C))
      quitf (_wa, "Test #%lld, C cannot beat B!", t);
    if (!win(a, A, b, B))
      quitf (_wa, "Test #%lld, B cannot beat A!", t);
  }
  quitf (_ok, "Good job!");
}

题目附件中的是本题实际数据的脚造方式，如有更强有意义的数据欢迎在讨论区中提出并 at 出题人。

#P7905. 黄牛の争