Description

d琢喵 has two types of scalpers under her command:

1. Type I scalper: “attack” is $a$, “health” is $A$.
2. Type II scalper: “attack” is $b$, “health” is $B$.

Battles between scalpers follow these rules:

1. At any time, if one side’s “health” $\le 0$, the opponent wins.
2. Each round, the side with higher “attack” acts first.
3. In each round, both sides act once, and the damage dealt equals their “attack” value.

The constructed Type III scalper must satisfy the following:

1. Its “attack” value is different from both Type I and Type II.
2. In a battle between Type I and Type II, Type II wins. (If the input does not satisfy this, output -1 -1 directly.)
3. In a battle between Type II and Type III, Type III wins.
4. In a battle between Type III and Type I, Type I wins.

Please provide one valid construction.

---

Brief statement

Solve the system (if $x=\text{true}$ then $[x]=1$, otherwise $=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}$$

Given $a,A,b,B$, find $c,C$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $q$.

The next $q$ lines each contain four positive integers $a,A,b,B$.

The data guarantees $a\ne b$.

Output Format

Output $q$ lines. Each line contains two positive integers: the constructed Type III scalper’s “attack” value and “health” value. If there is no solution, output -1 -1.

This problem uses Special Judge; any solution that satisfies the requirements will be accepted.

3
1 5 2 3
2 3 4 1
4 1 1 5

4 1
1 5
2 3

4
14 1 10 15
14 1 10 15
14 1 10 15
14 1 10 15

11 11
11 12
11 13
11 14

1
1 1 999 999

-1 -1

Hint

Sample Explanation

For sample #1, we can set $A$ to be $(1,5)$, $B$ to be $(2,3)$, and $C$ to be $(4,1)$.

Here, the pair $(x,y)$ represents a scalper with “attack” $x$ and “health” $y$.

The table below shows the battle results among $A$, $B$, and $C$. The numbers in parentheses indicate their “health” at the start of each round.

A vs. B	B vs. C	C vs. 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}$

Therefore, outputting such a Type III scalper will be accepted.

For sample #2: fixing the Type III scalper’s attack to be $11$ is already enough to defeat the Type II scalper, and a health value in $11\sim14$ can still lose to the Type I scalper.

So any output of one valid pair will be accepted.

For sample #3: the Type II scalper is very strong, making it hard to construct a Type III scalper that can both defeat Type II and lose to Type I.

So outputting -1 -1 will be accepted.

Constraints

Let $M=\max\left(a,A,b,B\right)$:

• Subtask1(10pts): $M\le10,q=399\underline0$.
• Subtask2(20pts): $M\le100,q=399\underline1$, data is random.
• Subtask3(10pts): $M\le10^5,q=99\underline2$, data is random.
• Subtask4(20pts): $M\le10^5,q=99\underline3$.
• Subtask5(10pts): $q=399\underline4$, data is random.
• Subtask6(30pts): $q=399\underline5$, no special restrictions.
• This problem uses different time limits based on testdata strength. If a reasonable full-score solution is being time-hacked, please contact me.

Hint: the last digit of the number of test cases $q$ (namely $\underline0,\underline1,\underline2,\underline3,\underline4,\underline5$) may help you judge the Subtask type.

For $100\%$ of the data: $1\le q<4000,1\le M\le10^8$.

Large Samples

This problem provides test cases that satisfy the constraints of Subtask $2,3,5$.

Compile and run the code below, and you will get E01.in, E02.in, E03.in, which are testdata satisfying the constraints of Subtask $2,3,5$ respectively.

#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();
}

The following Special Judge is also provided. You can compile it and call spj E.in E.out E.ans to get feedback.

#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!");
}

In addition, the attachments include the actual method used to generate the official data. If you have stronger and meaningful testdata, feel free to suggest it in the discussion area and @ the problem setter.

Translated by ChatGPT 5