QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492263#7179. Fischer's Chess Guessing Gameno_RED_no_DEADAC ✓32ms3892kbC++201.6kb2024-07-26 10:55:552024-07-26 10:55:56

Judging History

你现在查看的是最新测评结果

  • [2024-07-26 10:55:56]
  • 评测
  • 测评结果:AC
  • 用时:32ms
  • 内存:3892kb
  • [2024-07-26 10:55:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int main() {
	string piece = "KQRRBBNN";
	sort(piece.begin(), piece.end());
	vector<string> cand;
	do {
		// the king is placed between the two rooks
		int l = piece.find('R');
		int r = piece.find_last_of('R');
		int k = piece.find('K');
		if (k < l || k > r) {
			continue;
		}
		// the white bishop s are placed on opposite-colored squares
		int b1 = piece.find('B');
		int b2 = piece.find_last_of('B');
		if (b1 % 2 == b2 % 2) {
			continue;
		}
		cand.push_back(piece);
	} while (next_permutation(piece.begin(), piece.end()));


	string str;
	while (cin >> str) {
		if (str == "END") {
			break;
		}
		cin >> *new int;
		auto cur = cand;

		while (1) {
			double best = numeric_limits<double>::max();
			string base;
			if (cur.size() == 960) {
				base = "RBBNNQKR";
			} else {
                // DONE UP HERE
				for (auto x : cur) {
					array<int, 9> freq{};
					for (auto y : cur) {
						int cnt = 0;
						for (int i = 0; i < 8; i++) {
							if (x[i] == y[i]) {
								cnt++;
							}
						}
						freq[cnt]++;
					}
					double sum = 0;
					for (int x : freq) {
						if (x) {
							sum += x * sqrt(x);
						}
					}
					if (sum < best) {
						best = sum;
						base = x;
					}
				}
			}
			cout << base << endl;
			int num;
			cin >> num;
			if (num == 8) {
				break;
			}
			vector<string> ncur;
			for (auto x : cur) {
				int cnt = 0;
				for (int i = 0; i < 8; i++) {
					if (x[i] == base[i]) {
						cnt++;
					}
				}
				if (cnt == num) {
					ncur.push_back(x);
				}
			}
			cur = move(ncur);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

GAME 1
2
3
1
1
2
8
END

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 6 (1 test case)

Test #2:

score: 0
Accepted
time: 28ms
memory: 3752kb

input:

GAME 1
2
3
1
1
2
8
GAME 2
1
4
4
3
8
GAME 3
1
3
6
8
GAME 4
1
3
3
0
8
GAME 5
3
3
3
8
GAME 6
2
5
3
4
8
GAME 7
1
3
4
4
5
8
GAME 8
2
2
3
1
8
GAME 9
2
2
2
1
1
8
GAME 10
1
2
1
1
5
8
GAME 11
3
3
4
2
8
GAME 12
2
3
0
3
6
8
GAME 13
2
3
2
3
3
8
GAME 14
2
4
3
3
8
GAME 15
3
4
3
2
8
GAME 16
2
4
6
8
GAME 17
2
5
6
8...

output:

RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
BBRKQNNR
RKRBBQNN
RBBNNQKR
RNQBBKRN
RKNQBBRN
NBRQBKRN
RKRBBNQN
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RKRBBNNQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
NBNRBKRQ
RKRBQNBN
RBBNNQKR
RKBNQBRN
RKBQNRNB
RKRBNQBN
RBBNNQKR
RKNBQNBR
RKNNQRBB
RKBBQNRN
RKRBNNBQ
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNKRBBNQ
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #3:

score: 0
Accepted
time: 24ms
memory: 3636kb

input:

GAME 1
2
5
2
8
GAME 2
3
2
2
2
1
8
GAME 3
2
6
4
8
GAME 4
3
2
2
1
4
8
GAME 5
2
8
GAME 6
4
1
4
2
8
GAME 7
3
4
2
2
8
GAME 8
2
4
4
5
8
GAME 9
3
4
2
1
8
GAME 10
4
2
3
6
8
GAME 11
3
3
4
8
GAME 12
3
5
4
3
8
GAME 13
3
2
1
1
8
GAME 14
2
2
5
8
GAME 15
2
2
4
3
8
GAME 16
2
4
2
4
1
8
GAME 17
4
1
2
8
GAME 18
3
1
1...

output:

RBBNNQKR
RKNBQNBR
RKNNQRBB
RKQBBNNR
RBBNNQKR
RKBNQBRN
NRQNBBKR
BBRNQKNR
BRKNNQRB
RKNBBQNR
RBBNNQKR
RKNBQNBR
RNKBQNBR
RKNBBNQR
RBBNNQKR
RKBNQBRN
NRQNBBKR
BBRNQKNR
RNKQNBBR
RKQBNNBR
RBBNNQKR
RKNBQNBR
RBBNNQKR
BBRNQNKR
RQBBNKNR
RBBQNKRN
RKNBNQBR
RBBNNQKR
RKBNQBRN
RKBQNNRB
RBBKQRNN
RKQNBBNR
RBBNNQKR
RKN...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #4:

score: 0
Accepted
time: 26ms
memory: 3636kb

input:

GAME 1
0
1
4
3
8
GAME 2
0
2
2
1
3
8
GAME 3
0
0
1
8
GAME 4
0
0
4
5
8
GAME 5
1
1
1
2
3
8
GAME 6
0
1
3
1
8
GAME 7
1
1
0
3
8
GAME 8
0
1
6
5
8
GAME 9
1
0
2
2
2
8
GAME 10
1
0
4
4
4
8
GAME 11
0
0
4
8
GAME 12
2
1
2
3
8
GAME 13
1
2
4
4
8
GAME 14
0
4
3
4
8
GAME 15
0
2
0
4
8
GAME 16
0
2
1
3
8
GAME 17
1
1
3
1
2...

output:

RBBNNQKR
BNRBKRQN
NRKQRBBN
BRKQRNNB
QRKRBBNN
RBBNNQKR
BNRBKRQN
NNRQBKRB
BQNRKNRB
NQRKRBBN
NRKRBBQN
RBBNNQKR
BNRBKRQN
QRNKRNBB
NRKRBBNQ
RBBNNQKR
BNRBKRQN
QRNKRNBB
NRKRQNBB
QRKRBNNB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
NRKRBQNB
RBBNNQKR
BNRBKRQN
NRKQRBBN
BRNKRBNQ
NRKRBNQB
RBBNNQKR
RNQBBKRN
BNR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #5:

score: 0
Accepted
time: 29ms
memory: 3688kb

input:

GAME 1
1
2
0
2
2
8
GAME 2
1
4
3
1
8
GAME 3
1
2
1
0
3
8
GAME 4
1
1
1
2
1
8
GAME 5
1
3
1
8
GAME 6
2
3
1
4
8
GAME 7
3
4
2
8
GAME 8
4
1
3
3
8
GAME 9
4
1
4
4
8
GAME 10
2
1
1
3
2
8
GAME 11
2
2
5
5
8
GAME 12
2
2
4
2
8
GAME 13
3
2
1
2
8
GAME 14
2
4
4
3
8
GAME 15
3
1
2
0
8
GAME 16
3
2
0
4
2
8
GAME 17
2
2
2
4...

output:

RBBNNQKR
RNQBBKRN
BRKBNNRQ
RKNQBRNB
NBRKBRQN
RQNKRBBN
RBBNNQKR
RNQBBKRN
RKNQBBRN
NRKBBQRN
RNQKRBBN
RBBNNQKR
RNQBBKRN
BRKBNNRQ
BBQRKRNN
NQNBRKBR
RNNKRBBQ
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRKBNRBQ
RQNKRNBB
RBBNNQKR
RNQBBKRN
RKNBBRNQ
RNQKRNBB
RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
RNNKRQBB
RBBNNQKR
RKB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #6:

score: 0
Accepted
time: 32ms
memory: 3828kb

input:

GAME 1
2
0
3
5
8
GAME 2
1
2
2
6
8
GAME 3
2
0
2
5
3
8
GAME 4
2
1
2
3
3
8
GAME 5
1
1
1
4
8
GAME 6
3
2
2
0
8
GAME 7
0
1
3
4
8
GAME 8
0
1
4
1
8
GAME 9
0
0
3
4
8
GAME 10
0
0
6
4
8
GAME 11
0
0
4
4
8
GAME 12
1
2
2
3
8
GAME 13
2
1
4
3
4
8
GAME 14
1
0
2
8
GAME 15
2
2
1
4
8
GAME 16
3
2
3
1
8
GAME 17
2
2
1
4
4...

output:

RBBNNQKR
RKNBQNBR
BBRKNRQN
QRBKNRNB
QRBKNBRN
RBBNNQKR
RNQBBKRN
BRKBNNRQ
NRBQKBRN
NRBKQBRN
RBBNNQKR
RKNBQNBR
BBRKNRQN
BRKNNBRQ
BRQNNKRB
NRBKNBRQ
RBBNNQKR
RKNBQNBR
NRBQKBNR
BRNNKQRB
NRKRNQBB
QRBKNNRB
RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
NRBKQNRB
RBBNNQKR
RKBNQBRN
NRQNBBKR
BBRNQKNR
NRBKNQRB
RBBNNQKR
BNR...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #7:

score: 0
Accepted
time: 25ms
memory: 3684kb

input:

GAME 1
3
3
5
8
GAME 2
4
2
1
6
8
GAME 3
4
2
1
8
GAME 4
3
3
2
5
8
GAME 5
2
3
1
3
5
8
GAME 6
3
2
1
3
5
8
GAME 7
2
2
2
6
8
GAME 8
2
2
2
8
GAME 9
2
2
1
0
8
GAME 10
3
3
5
5
8
GAME 11
2
1
4
0
8
GAME 12
3
3
4
1
8
GAME 13
1
3
4
1
8
GAME 14
1
5
3
3
8
GAME 15
1
3
5
5
8
GAME 16
2
3
1
5
5
8
GAME 17
2
2
2
4
4
8
G...

output:

RBBNNQKR
RKBNQBRN
RKBQNRNB
RBBQKRNN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNKRQN
RBBNNQKR
BBRNQNKR
QNBRNBKR
RBBNKRNQ
RBBNNQKR
RKBNQBRN
RKBQNRNB
RBKNBRQN
RBQNKRBN
RBBNNQKR
RKNBQNBR
NRQBNKBR
RNKNQRBB
RBKQRNBN
RBNQKRBN
RBBNNQKR
RKBNQBRN
NRQNBBKR
BBRNNKRQ
RBKNRNBQ
RBNNKRBQ
RBBNNQKR
RKNBQNBR
RBQKBNRN
RNB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #8:

score: 0
Accepted
time: 19ms
memory: 3628kb

input:

GAME 1
1
1
1
1
4
8
GAME 2
1
2
3
0
8
GAME 3
2
4
2
4
8
GAME 4
2
3
3
4
8
GAME 5
2
2
1
4
3
8
GAME 6
1
0
1
2
8
GAME 7
1
1
4
5
8
GAME 8
2
0
6
4
8
GAME 9
2
0
4
1
2
8
GAME 10
0
6
6
8
GAME 11
0
8
GAME 12
0
6
8
GAME 13
1
0
3
8
GAME 14
0
5
3
3
8
GAME 15
1
1
8
GAME 16
2
1
1
4
8
GAME 17
1
1
3
5
8
GAME 18
2
1
2
2...

output:

RBBNNQKR
RNQBBKRN
BNRNKRQB
NRBKRBQN
BRKBQNNR
QRNBKNBR
RBBNNQKR
RNQBBKRN
BRKBNNRQ
BQRKNBRN
NRQBKNBR
RBBNNQKR
RKNBQNBR
RKNQNRBB
NBNRQKBR
NRNBKQBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRNBKQNR
QRNNKBBR
RBBNNQKR
RKNBQNBR
RBQKBNRN
NRNQBBKR
BRNKNBQR
NRQNKBBR
RBBNNQKR
RNQBBKRN
BRKNRNQB
BBNRKRNQ
NRNQKBBR
RBBNNQKR
RNQ...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #9:

score: 0
Accepted
time: 21ms
memory: 3748kb

input:

GAME 1
3
1
2
4
8
GAME 2
4
2
3
1
8
GAME 3
3
1
3
4
8
GAME 4
2
4
2
5
8
GAME 5
2
3
4
2
8
GAME 6
3
0
3
2
8
GAME 7
2
1
5
3
8
GAME 8
2
1
6
8
GAME 9
2
1
5
2
8
GAME 10
1
1
2
0
0
8
GAME 11
1
0
0
5
8
GAME 12
1
2
0
0
8
GAME 13
4
1
4
8
GAME 14
4
3
4
4
8
GAME 15
5
3
5
8
GAME 16
3
4
2
3
5
8
GAME 17
2
2
5
4
8
GAME ...

output:

RBBNNQKR
RKBNQBRN
BBNNRKQR
QNBBRNKR
QBBRKNNR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RQKNNBBR
NBBRKQNR
RBBNNQKR
RKBNQBRN
BBNNRKQR
RBNQKNBR
NBBRKNQR
RBBNNQKR
RKNBQNBR
RKNQNRBB
NBNRQKBR
QBNRKNBR
RBBNNQKR
RKNBQNBR
NRQBNKBR
BRKBNNQR
NBQRKNBR
RBBNNQKR
RKBNQBRN
NNRBBQKR
BQNBNRKR
NBNRKQBR
RBBNNQKR
RKNBQNBR
NRBQKBNR
BRK...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #10:

score: 0
Accepted
time: 22ms
memory: 3892kb

input:

GAME 1
3
0
2
5
8
GAME 2
3
2
2
8
GAME 3
4
5
5
8
GAME 4
2
2
0
2
8
GAME 5
1
3
2
4
8
GAME 6
2
2
0
3
5
8
GAME 7
3
1
4
8
GAME 8
2
1
4
3
3
8
GAME 9
3
1
5
5
8
GAME 10
4
4
4
3
8
GAME 11
3
0
3
2
4
8
GAME 12
3
2
3
8
GAME 13
1
4
1
8
GAME 14
1
3
3
3
8
GAME 15
1
4
1
6
8
GAME 16
2
3
5
2
8
GAME 17
2
3
6
8
GAME 18
1...

output:

RBBNNQKR
RKBNQBRN
NNRBBQKR
BBRKNNQR
BBRQNKNR
RBBNNQKR
RKBNQBRN
NRQNBBKR
BBRNQKNR
RBBNNQKR
BBRNQNKR
BBRNKQNR
BBRNNKQR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BQRBNKNR
RBBNNQKR
RNQBBKRN
RKNBBRNQ
QNNBRKBR
BNRBQKNR
RBBNNQKR
RKNBQNBR
RBQKBNRN
BRNNKBQR
BNRBKQNR
BNRBNKQR
RBBNNQKR
RKBNQBRN
BBNNRKQR
QBRNBKNR
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Test #11:

score: 0
Accepted
time: 14ms
memory: 3684kb

input:

GAME 1
3
1
2
4
2
8
GAME 2
3
1
1
2
8
GAME 3
4
2
3
2
8
GAME 4
4
3
4
2
2
8
GAME 5
4
3
5
2
8
GAME 6
3
2
4
2
5
8
GAME 7
3
0
3
5
8
GAME 8
2
5
2
3
8
GAME 9
4
3
1
8
GAME 10
4
4
3
2
8
GAME 11
3
1
3
3
8
GAME 12
3
3
0
2
8
GAME 13
4
3
1
5
8
GAME 14
3
2
4
2
4
8
GAME 15
5
3
2
4
8
GAME 16
5
5
3
3
8
GAME 17
4
2
5
8...

output:

RBBNNQKR
RKBNQBRN
BBNNRKQR
QNBBRNKR
QBBRKNNR
RQNBBNKR
RBBNNQKR
RKBNQBRN
BBNNRKQR
NRBBKQNR
RNQBBNKR
RBBNNQKR
BBRNQNKR
QNBRNBKR
RQKNNBBR
RNNBBQKR
RBBNNQKR
BBRNQNKR
RBQNBKNR
NBBNRKQR
RBQKNNBR
RQNNBBKR
RBBNNQKR
BBRNQNKR
RBQNBKNR
QBBNRKNR
RNQNBBKR
RBBNNQKR
RKBNQBRN
NRQNBBKR
BRKNNBQR
NNBQRBKR
RNNQBBKR
RBB...

result:

ok (c) correct after 96 tests, max moves 6 (96 test cases)

Extra Test:

score: 0
Extra Test Passed