SRM 572 Div 1 500 문제 해결
Mark
이 문제는 세부적으로 어렵구나!TLE 시간이 아니잖아!한 문제의 난점에 너무 신경 쓰지 마세요. 잘못 판단할 수도 있으니까. T.T
원제 묘사
Problem Statement
Elly and Kristina play a game called "Bulls". Initially each of them thinks of a non-negative integer with K digits, possibly containing leading zeroes. Then they take alternating turns, trying to guess the opponent's number. After each guess, the other person says how many positions were guessed correctly. For example if Kristina's number was "1337"and Elly's guess was "1738", Kristina should answer 2, since the digits at positions 0 and 2 (zero-based indices from the left) are correct. A guessed position is called "bull's hit", or simply a "bull", thus the name of the game. Elly has already made several guesses. She wonders if the information she has is enough to uniquely determine Kristina's number. You are given the guesses so far in a vector guesses and the corresponding number of bull's hits in vector bulls. If a unique number satisfies the given information, return it as a string. If there is more than one number that is valid according to the current guesses, return "Ambiguity"(quotes for clarity only). If no number satisfies the given information, then Kristina has lied and you should return "Liar"instead.
Definition
Class:
EllysBulls
Method:
getNumber
Parameters:
vector , vector
Returns:
string
Method signature:
string getNumber(vector guesses, vector bulls)
(be sure your method is public)
Notes
-
The game "Bulls"is a simplification of a game played in Bulgaria, called "Kravi & Bikove"("Cows & Bulls").
Constraints
-
guesses will contain between 1 and 50 elements, inclusive.
-
Each element of guesses will contain between 2 and 9 characters, inclusive.
-
All elements of guesses will contain the same number of characters.
-
All elements of guesses will consist only of digits ('0'-'9').
-
bulls will contain the same number of elements as guesses.
-
Each element of bulls will be between 0 and K-1, inclusive, where K is the length of each element ofguesses.
Examples
0)
{"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"}
{2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0}
Returns: "1337"
From {1234->2, 2222->0, 4444->0} it follows that the number is {1?3?}. The additional information {4321->1} tells us that either the digit at position 1 (0-indexed) is 3, or that the one at position 3 is 1. However, since {1111->1} and we already know that the 0-th digit is 1, then the third digit cannot be 1. Now we know that the number is {133?}. When trying {7777->1} we see that Kristina's number contains a 7, which cannot be anywhere else except in the last position. Thus, her number is 1337.
1)
{"0000", "1111", "2222"}
{2, 2, 2}
Returns: "Liar"
There are supposed to be two 0s, two 1s and two 2s in a four-digit number. Thus, Kristina is clearly a liar.
2)
{"666666", "666677", "777777", "999999"}
{2, 3, 1, 0}
Returns: "Ambiguity"
Some of the possible configurations that satisfy the current results are the numbers 636172, 336617, 660007. Thus, the answer is ambiguous.
3)
{"000", "987", "654", "321", "100", "010"}
{2, 1, 0, 0, 1, 1}
Returns: "007"
The guesses, as well as the answer, can have leading zeroes.
4)
{"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: "54"
5)
{"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"}
{1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1}
Returns: "4266642"
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
신뢰 서술
숫자 맞추기 게임은 해 봤지, 정답이 S라고 가정해 봐.
n<=50개의 길이가 같고 최장 9의 숫자열 (S 길이와 같다) 을 주고, 문자열마다 S 숫자와 위치가 같은 위치 개수를 주어라.
요구 사항:
1、풀이 없으면 Liar 내보내기
2. 멀티플렉스 시 Ambiguity 출력
3. 만약 단해하면 출력한다.
계산법
수색하다.
원래는 모든 위치에서 직접 검색하려고 했는데 분명히 1e9 * 50은 TLE 아sad를 원합니다.
최대 9자리 숫자가 나오자 상태 압축 + 검색, 즉 문자열마다 어떤 위치가 정확한지 매거하는 것이 생각났다.그렇다면 이론적으로 복잡도는 최고 2 ^ 9 * 2 ^ 9 * 50
가지치기+최적화
1. 모든 숫자를 다 열거하면 나머지 만족 여부를 직접 판단한다.
2. 만약에 다해를 발견하면 출력 다해를 출력한다.
3. 이미 열거한 위치는 열거하지 않는다
4、정확한 개수에 따라 큰 순서에서 작은 순서로 검색 트리를 줄인다
디테일
1. 무해와 다해의 판단에 있어 dfs 함수 안의if(x>=n)에서는 중점이다.
1) 한 사람이 일일이 열거하지 않으면 다해일 수 있다 | 뒤에 한 사람이 무해할 수 있다면 무해다
2) 어떤 분이 풀리지 않으면 바로 풀리지 않는다
함수의 작용
init: 초기화 멱수 그룹mi, mm는 각 이진수 1개의 수를 기록하고,ri는 i개 1개의 수를 포함하는 이진수 어떤 것들이 있는지 기록한다.
check: 현재 직렬과 현재 해제에 대해 어떤 위치가 중합되는지 판단하고 2진 압축
makebad: 현재 해답과 현재 열의 매거진에 대해 새로운bad 그룹을 만듭니다. (한 사람의 숫자는 사용할 수 없습니다.)
ins: 현재 열에 열거할 때 풀이에 몇 개의 수를 넣었습니다
reset:ins의 역과정
isbad: 일일이 열거할 때 사용할 수 없는 위치와 수를 만났다
puliccheck: 이미 일일이 열거한 상황에 대해 판단한 후 정확한지 여부
ffs: 매거 프로세스(위치 x, 이미 얻은 위치 압축all, 사용할 수 없는 위치와 수bad)
코드 typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
typedef vector<int> VI;
class EllysBulls {
public:
vector <string > g ;
VI r;
int len , n;
int ans[100] , out[100];
int mm[1 << 10] , mi[10];
VI ri[10];
void init(){
REP(i , len) {ri[i].clear() , mi[i] = 1 << i;}
REP_C(i , (1 << len)){
mm[i] = 0;
int j = i;
while(j){
mm[i] += j & 1;
j >>= 1;
}
ri[mm[i]].PB(i);
}
}
int check(int x){
int res = 0;
REP(i , len){
if (ans[i] != -1 && g[x][i] == '0' + ans[i])
res |= mi[i];
}
return res;
}
void makebad(int x , int now , bool newbad[10][10] , bool bad[10][10]){
REP_2(i , j , len , 10) newbad[i][j] = bad[i][j];
REP(i , len)
if (!(now & mi[i]))
newbad[i][g[x][i] - '0'] = 1;
else{
REP(j , 10)
newbad[i][j] = (j == g[x][i] - '0');
}
}
void ins(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = g[x][i] - '0';
}
void reset(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = -1;
}
bool isbad(int x , int now , bool bad[10][10]){
REP(i , len) if (now & mi[i])
if (bad[i][g[x][i] - '0']) return true;
return false;
}
int publiccheck(int st){
for( ; st < n ; ++st){
int res = 0;
REP(i , len)
res += ans[i] == g[st][i] - '0';
if (res != r[st]) return 0;
}
return 1;
}
int dfs(int x , int all , bool bad[10][10]){
if(all == mi[len] - 1) return publiccheck(x + 1);
if (x >= n){
int ret = 1;
REP(i , len){
if (ans[i] != -1 || (all & mi[i])) continue;
int res = -1;
REP(j , 10){
if (!bad[i][j]){
if (res != -1) ret = 2;
res = j;
}
}
if (res == -1) return 0;
ans[i] = res;
}
REP(i , len) out[i] = ans[i];
if (ret > 1) return 2;
return 1;
}
int now = check(x);
if (mm[now] > r[x]) return 0;
bool newbad[10][10];
int ret = 0;
REP_C(i , SZ(ri[r[x] - mm[now]])){
int add = ri[r[x] - mm[now]][i];
if (add & all) continue;
if (isbad(x , add , bad)) continue;
makebad(x , (add | now) , newbad , bad);
ins(x , add);
ret += dfs(x + 1 , (all | add) , newbad);
reset(x , add);
if (ret > 1) {
return ret;
}
}
return ret;
}
string getNumber(vector <string> guesses, vector <int> bulls) {
g = guesses;
r = bulls;
len = g[0].length();
n = SZ(g);
REP_2(i , j , n , i){
if(r[j] < r[i]){
swap(r[i] , r[j]);
swap(g[i] , g[j]);
}
}
FLC(ans , -1);
init();
bool bad[10][10];
RST(bad);
int res = dfs(0 , 0 , bad);
if (res == 0) return "Liar";
if (res > 1) return "Ambiguity";
string ret = "";
REP(i , len){
ret += (out[i] + '0');
}
return ret;
}
};
데이터 int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string guesses[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
int bulls[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
string expected__ = "1337";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string guesses[] = {"0000", "1111", "2222"};
int bulls[] = {2, 2, 2};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string guesses[] = {"666666", "666677", "777777", "999999"};
int bulls[] = {2, 3, 1, 0};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string guesses[] = {"000", "987", "654", "321", "100", "010"};
int bulls[] = {2, 1, 0, 0, 1, 1};
string expected__ = "007";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string guesses[] = {"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"};
int bulls[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
string expected__ = "54";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 5: {
string guesses[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"};
int bulls[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
string expected__ = "4266642";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 6: {
string guesses[] = {"689717881","729469886","836709781","182159888","389571851","802979001","855698811","883017381","287479881","689187881","186272081","549279841","829259582","889209851","465277831","489034841","854257830","583859981","451171881","829977181","589259281","584819788","189275655","389989186","888219281","389364881","289619892","488379911","739371471","399229321","589077481","889372855","074279488","489276833","879734481","849279825","715279981","386309883","899779505","115174081","687279667","987289061","789279812","082577871","419709881","178279821","587503881","815432882","809271664","886556286"};
int bulls[] = {5,4,4,4,5,4,3,4,6,5,5,6,5,7,4,4,3,4,4,5,6,3,4,4,6,5,4,4,3,4,5,5,4,5,4,6,5,4,4,3,4,4,6,4,5,5,4,3,4,3};
string expected__ = "ABC";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 7: {
string guesses[] = {"000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999"};
int bulls[] = {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,2,0};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 8: {
string guesses[] = {"00000000", "10000001", "07000008", "02000020", "00600070", "00300300", "00050600", "00044000", "80005000"};
int bulls[] = {0, 1, 1, 1, 1, 1, 1, 1, 1};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
default:
return -1;
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
Problem Statement
Elly and Kristina play a game called "Bulls". Initially each of them thinks of a non-negative integer with K digits, possibly containing leading zeroes. Then they take alternating turns, trying to guess the opponent's number. After each guess, the other person says how many positions were guessed correctly. For example if Kristina's number was "1337"and Elly's guess was "1738", Kristina should answer 2, since the digits at positions 0 and 2 (zero-based indices from the left) are correct. A guessed position is called "bull's hit", or simply a "bull", thus the name of the game. Elly has already made several guesses. She wonders if the information she has is enough to uniquely determine Kristina's number. You are given the guesses so far in a vector
Definition
Class:
EllysBulls
Method:
getNumber
Parameters:
vector
Returns:
string
Method signature:
string getNumber(vector
(be sure your method is public)
Notes
-
The game "Bulls"is a simplification of a game played in Bulgaria, called "Kravi & Bikove"("Cows & Bulls").
Constraints
-
guesses will contain between 1 and 50 elements, inclusive.
-
Each element of guesses will contain between 2 and 9 characters, inclusive.
-
All elements of guesses will contain the same number of characters.
-
All elements of guesses will consist only of digits ('0'-'9').
-
bulls will contain the same number of elements as guesses.
-
Each element of bulls will be between 0 and K-1, inclusive, where K is the length of each element ofguesses.
Examples
0)
{"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"}{2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0}Returns: "1337"From {1234->2, 2222->0, 4444->0} it follows that the number is {1?3?}. The additional information {4321->1} tells us that either the digit at position 1 (0-indexed) is 3, or that the one at position 3 is 1. However, since {1111->1} and we already know that the 0-th digit is 1, then the third digit cannot be 1. Now we know that the number is {133?}. When trying {7777->1} we see that Kristina's number contains a 7, which cannot be anywhere else except in the last position. Thus, her number is 1337.
1)
{"0000", "1111", "2222"}{2, 2, 2}Returns: "Liar"There are supposed to be two 0s, two 1s and two 2s in a four-digit number. Thus, Kristina is clearly a liar.
2)
{"666666", "666677", "777777", "999999"}{2, 3, 1, 0}Returns: "Ambiguity"Some of the possible configurations that satisfy the current results are the numbers 636172, 336617, 660007. Thus, the answer is ambiguous.
3)
{"000", "987", "654", "321", "100", "010"}{2, 1, 0, 0, 1, 1}Returns: "007"The guesses, as well as the answer, can have leading zeroes.
4)
{"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"}{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}Returns: "54"5)
{"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"}{1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1}Returns: "4266642"This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
신뢰 서술
숫자 맞추기 게임은 해 봤지, 정답이 S라고 가정해 봐.
n<=50개의 길이가 같고 최장 9의 숫자열 (S 길이와 같다) 을 주고, 문자열마다 S 숫자와 위치가 같은 위치 개수를 주어라.
요구 사항:
1、풀이 없으면 Liar 내보내기
2. 멀티플렉스 시 Ambiguity 출력
3. 만약 단해하면 출력한다.
계산법
수색하다.
원래는 모든 위치에서 직접 검색하려고 했는데 분명히 1e9 * 50은 TLE 아sad를 원합니다.
최대 9자리 숫자가 나오자 상태 압축 + 검색, 즉 문자열마다 어떤 위치가 정확한지 매거하는 것이 생각났다.그렇다면 이론적으로 복잡도는 최고 2 ^ 9 * 2 ^ 9 * 50
가지치기+최적화
1. 모든 숫자를 다 열거하면 나머지 만족 여부를 직접 판단한다.
2. 만약에 다해를 발견하면 출력 다해를 출력한다.
3. 이미 열거한 위치는 열거하지 않는다
4、정확한 개수에 따라 큰 순서에서 작은 순서로 검색 트리를 줄인다
디테일
1. 무해와 다해의 판단에 있어 dfs 함수 안의if(x>=n)에서는 중점이다.
1) 한 사람이 일일이 열거하지 않으면 다해일 수 있다 | 뒤에 한 사람이 무해할 수 있다면 무해다
2) 어떤 분이 풀리지 않으면 바로 풀리지 않는다
함수의 작용
init: 초기화 멱수 그룹mi, mm는 각 이진수 1개의 수를 기록하고,ri는 i개 1개의 수를 포함하는 이진수 어떤 것들이 있는지 기록한다.
check: 현재 직렬과 현재 해제에 대해 어떤 위치가 중합되는지 판단하고 2진 압축
makebad: 현재 해답과 현재 열의 매거진에 대해 새로운bad 그룹을 만듭니다. (한 사람의 숫자는 사용할 수 없습니다.)
ins: 현재 열에 열거할 때 풀이에 몇 개의 수를 넣었습니다
reset:ins의 역과정
isbad: 일일이 열거할 때 사용할 수 없는 위치와 수를 만났다
puliccheck: 이미 일일이 열거한 상황에 대해 판단한 후 정확한지 여부
ffs: 매거 프로세스(위치 x, 이미 얻은 위치 압축all, 사용할 수 없는 위치와 수bad)
코드 typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
typedef vector<int> VI;
class EllysBulls {
public:
vector <string > g ;
VI r;
int len , n;
int ans[100] , out[100];
int mm[1 << 10] , mi[10];
VI ri[10];
void init(){
REP(i , len) {ri[i].clear() , mi[i] = 1 << i;}
REP_C(i , (1 << len)){
mm[i] = 0;
int j = i;
while(j){
mm[i] += j & 1;
j >>= 1;
}
ri[mm[i]].PB(i);
}
}
int check(int x){
int res = 0;
REP(i , len){
if (ans[i] != -1 && g[x][i] == '0' + ans[i])
res |= mi[i];
}
return res;
}
void makebad(int x , int now , bool newbad[10][10] , bool bad[10][10]){
REP_2(i , j , len , 10) newbad[i][j] = bad[i][j];
REP(i , len)
if (!(now & mi[i]))
newbad[i][g[x][i] - '0'] = 1;
else{
REP(j , 10)
newbad[i][j] = (j == g[x][i] - '0');
}
}
void ins(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = g[x][i] - '0';
}
void reset(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = -1;
}
bool isbad(int x , int now , bool bad[10][10]){
REP(i , len) if (now & mi[i])
if (bad[i][g[x][i] - '0']) return true;
return false;
}
int publiccheck(int st){
for( ; st < n ; ++st){
int res = 0;
REP(i , len)
res += ans[i] == g[st][i] - '0';
if (res != r[st]) return 0;
}
return 1;
}
int dfs(int x , int all , bool bad[10][10]){
if(all == mi[len] - 1) return publiccheck(x + 1);
if (x >= n){
int ret = 1;
REP(i , len){
if (ans[i] != -1 || (all & mi[i])) continue;
int res = -1;
REP(j , 10){
if (!bad[i][j]){
if (res != -1) ret = 2;
res = j;
}
}
if (res == -1) return 0;
ans[i] = res;
}
REP(i , len) out[i] = ans[i];
if (ret > 1) return 2;
return 1;
}
int now = check(x);
if (mm[now] > r[x]) return 0;
bool newbad[10][10];
int ret = 0;
REP_C(i , SZ(ri[r[x] - mm[now]])){
int add = ri[r[x] - mm[now]][i];
if (add & all) continue;
if (isbad(x , add , bad)) continue;
makebad(x , (add | now) , newbad , bad);
ins(x , add);
ret += dfs(x + 1 , (all | add) , newbad);
reset(x , add);
if (ret > 1) {
return ret;
}
}
return ret;
}
string getNumber(vector <string> guesses, vector <int> bulls) {
g = guesses;
r = bulls;
len = g[0].length();
n = SZ(g);
REP_2(i , j , n , i){
if(r[j] < r[i]){
swap(r[i] , r[j]);
swap(g[i] , g[j]);
}
}
FLC(ans , -1);
init();
bool bad[10][10];
RST(bad);
int res = dfs(0 , 0 , bad);
if (res == 0) return "Liar";
if (res > 1) return "Ambiguity";
string ret = "";
REP(i , len){
ret += (out[i] + '0');
}
return ret;
}
};
데이터 int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string guesses[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
int bulls[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
string expected__ = "1337";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string guesses[] = {"0000", "1111", "2222"};
int bulls[] = {2, 2, 2};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string guesses[] = {"666666", "666677", "777777", "999999"};
int bulls[] = {2, 3, 1, 0};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string guesses[] = {"000", "987", "654", "321", "100", "010"};
int bulls[] = {2, 1, 0, 0, 1, 1};
string expected__ = "007";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string guesses[] = {"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"};
int bulls[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
string expected__ = "54";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 5: {
string guesses[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"};
int bulls[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
string expected__ = "4266642";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 6: {
string guesses[] = {"689717881","729469886","836709781","182159888","389571851","802979001","855698811","883017381","287479881","689187881","186272081","549279841","829259582","889209851","465277831","489034841","854257830","583859981","451171881","829977181","589259281","584819788","189275655","389989186","888219281","389364881","289619892","488379911","739371471","399229321","589077481","889372855","074279488","489276833","879734481","849279825","715279981","386309883","899779505","115174081","687279667","987289061","789279812","082577871","419709881","178279821","587503881","815432882","809271664","886556286"};
int bulls[] = {5,4,4,4,5,4,3,4,6,5,5,6,5,7,4,4,3,4,4,5,6,3,4,4,6,5,4,4,3,4,5,5,4,5,4,6,5,4,4,3,4,4,6,4,5,5,4,3,4,3};
string expected__ = "ABC";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 7: {
string guesses[] = {"000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999"};
int bulls[] = {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,2,0};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 8: {
string guesses[] = {"00000000", "10000001", "07000008", "02000020", "00600070", "00300300", "00050600", "00044000", "80005000"};
int bulls[] = {0, 1, 1, 1, 1, 1, 1, 1, 1};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
default:
return -1;
}
}
}
수색하다.
원래는 모든 위치에서 직접 검색하려고 했는데 분명히 1e9 * 50은 TLE 아sad를 원합니다.
최대 9자리 숫자가 나오자 상태 압축 + 검색, 즉 문자열마다 어떤 위치가 정확한지 매거하는 것이 생각났다.그렇다면 이론적으로 복잡도는 최고 2 ^ 9 * 2 ^ 9 * 50
가지치기+최적화
1. 모든 숫자를 다 열거하면 나머지 만족 여부를 직접 판단한다.
2. 만약에 다해를 발견하면 출력 다해를 출력한다.
3. 이미 열거한 위치는 열거하지 않는다
4、정확한 개수에 따라 큰 순서에서 작은 순서로 검색 트리를 줄인다
디테일
1. 무해와 다해의 판단에 있어 dfs 함수 안의if(x>=n)에서는 중점이다.
1) 한 사람이 일일이 열거하지 않으면 다해일 수 있다 | 뒤에 한 사람이 무해할 수 있다면 무해다
2) 어떤 분이 풀리지 않으면 바로 풀리지 않는다
함수의 작용
init: 초기화 멱수 그룹mi, mm는 각 이진수 1개의 수를 기록하고,ri는 i개 1개의 수를 포함하는 이진수 어떤 것들이 있는지 기록한다.
check: 현재 직렬과 현재 해제에 대해 어떤 위치가 중합되는지 판단하고 2진 압축
makebad: 현재 해답과 현재 열의 매거진에 대해 새로운bad 그룹을 만듭니다. (한 사람의 숫자는 사용할 수 없습니다.)
ins: 현재 열에 열거할 때 풀이에 몇 개의 수를 넣었습니다
reset:ins의 역과정
isbad: 일일이 열거할 때 사용할 수 없는 위치와 수를 만났다
puliccheck: 이미 일일이 열거한 상황에 대해 판단한 후 정확한지 여부
ffs: 매거 프로세스(위치 x, 이미 얻은 위치 압축all, 사용할 수 없는 위치와 수bad)
코드 typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
typedef vector<int> VI;
class EllysBulls {
public:
vector <string > g ;
VI r;
int len , n;
int ans[100] , out[100];
int mm[1 << 10] , mi[10];
VI ri[10];
void init(){
REP(i , len) {ri[i].clear() , mi[i] = 1 << i;}
REP_C(i , (1 << len)){
mm[i] = 0;
int j = i;
while(j){
mm[i] += j & 1;
j >>= 1;
}
ri[mm[i]].PB(i);
}
}
int check(int x){
int res = 0;
REP(i , len){
if (ans[i] != -1 && g[x][i] == '0' + ans[i])
res |= mi[i];
}
return res;
}
void makebad(int x , int now , bool newbad[10][10] , bool bad[10][10]){
REP_2(i , j , len , 10) newbad[i][j] = bad[i][j];
REP(i , len)
if (!(now & mi[i]))
newbad[i][g[x][i] - '0'] = 1;
else{
REP(j , 10)
newbad[i][j] = (j == g[x][i] - '0');
}
}
void ins(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = g[x][i] - '0';
}
void reset(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = -1;
}
bool isbad(int x , int now , bool bad[10][10]){
REP(i , len) if (now & mi[i])
if (bad[i][g[x][i] - '0']) return true;
return false;
}
int publiccheck(int st){
for( ; st < n ; ++st){
int res = 0;
REP(i , len)
res += ans[i] == g[st][i] - '0';
if (res != r[st]) return 0;
}
return 1;
}
int dfs(int x , int all , bool bad[10][10]){
if(all == mi[len] - 1) return publiccheck(x + 1);
if (x >= n){
int ret = 1;
REP(i , len){
if (ans[i] != -1 || (all & mi[i])) continue;
int res = -1;
REP(j , 10){
if (!bad[i][j]){
if (res != -1) ret = 2;
res = j;
}
}
if (res == -1) return 0;
ans[i] = res;
}
REP(i , len) out[i] = ans[i];
if (ret > 1) return 2;
return 1;
}
int now = check(x);
if (mm[now] > r[x]) return 0;
bool newbad[10][10];
int ret = 0;
REP_C(i , SZ(ri[r[x] - mm[now]])){
int add = ri[r[x] - mm[now]][i];
if (add & all) continue;
if (isbad(x , add , bad)) continue;
makebad(x , (add | now) , newbad , bad);
ins(x , add);
ret += dfs(x + 1 , (all | add) , newbad);
reset(x , add);
if (ret > 1) {
return ret;
}
}
return ret;
}
string getNumber(vector <string> guesses, vector <int> bulls) {
g = guesses;
r = bulls;
len = g[0].length();
n = SZ(g);
REP_2(i , j , n , i){
if(r[j] < r[i]){
swap(r[i] , r[j]);
swap(g[i] , g[j]);
}
}
FLC(ans , -1);
init();
bool bad[10][10];
RST(bad);
int res = dfs(0 , 0 , bad);
if (res == 0) return "Liar";
if (res > 1) return "Ambiguity";
string ret = "";
REP(i , len){
ret += (out[i] + '0');
}
return ret;
}
};
데이터 int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string guesses[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
int bulls[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
string expected__ = "1337";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string guesses[] = {"0000", "1111", "2222"};
int bulls[] = {2, 2, 2};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string guesses[] = {"666666", "666677", "777777", "999999"};
int bulls[] = {2, 3, 1, 0};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string guesses[] = {"000", "987", "654", "321", "100", "010"};
int bulls[] = {2, 1, 0, 0, 1, 1};
string expected__ = "007";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string guesses[] = {"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"};
int bulls[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
string expected__ = "54";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 5: {
string guesses[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"};
int bulls[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
string expected__ = "4266642";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 6: {
string guesses[] = {"689717881","729469886","836709781","182159888","389571851","802979001","855698811","883017381","287479881","689187881","186272081","549279841","829259582","889209851","465277831","489034841","854257830","583859981","451171881","829977181","589259281","584819788","189275655","389989186","888219281","389364881","289619892","488379911","739371471","399229321","589077481","889372855","074279488","489276833","879734481","849279825","715279981","386309883","899779505","115174081","687279667","987289061","789279812","082577871","419709881","178279821","587503881","815432882","809271664","886556286"};
int bulls[] = {5,4,4,4,5,4,3,4,6,5,5,6,5,7,4,4,3,4,4,5,6,3,4,4,6,5,4,4,3,4,5,5,4,5,4,6,5,4,4,3,4,4,6,4,5,5,4,3,4,3};
string expected__ = "ABC";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 7: {
string guesses[] = {"000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999"};
int bulls[] = {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,2,0};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 8: {
string guesses[] = {"00000000", "10000001", "07000008", "02000020", "00600070", "00300300", "00050600", "00044000", "80005000"};
int bulls[] = {0, 1, 1, 1, 1, 1, 1, 1, 1};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
default:
return -1;
}
}
}
init: 초기화 멱수 그룹mi, mm는 각 이진수 1개의 수를 기록하고,ri는 i개 1개의 수를 포함하는 이진수 어떤 것들이 있는지 기록한다.
check: 현재 직렬과 현재 해제에 대해 어떤 위치가 중합되는지 판단하고 2진 압축
makebad: 현재 해답과 현재 열의 매거진에 대해 새로운bad 그룹을 만듭니다. (한 사람의 숫자는 사용할 수 없습니다.)
ins: 현재 열에 열거할 때 풀이에 몇 개의 수를 넣었습니다
reset:ins의 역과정
isbad: 일일이 열거할 때 사용할 수 없는 위치와 수를 만났다
puliccheck: 이미 일일이 열거한 상황에 대해 판단한 후 정확한지 여부
ffs: 매거 프로세스(위치 x, 이미 얻은 위치 압축all, 사용할 수 없는 위치와 수bad)
코드 typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
typedef vector<int> VI;
class EllysBulls {
public:
vector <string > g ;
VI r;
int len , n;
int ans[100] , out[100];
int mm[1 << 10] , mi[10];
VI ri[10];
void init(){
REP(i , len) {ri[i].clear() , mi[i] = 1 << i;}
REP_C(i , (1 << len)){
mm[i] = 0;
int j = i;
while(j){
mm[i] += j & 1;
j >>= 1;
}
ri[mm[i]].PB(i);
}
}
int check(int x){
int res = 0;
REP(i , len){
if (ans[i] != -1 && g[x][i] == '0' + ans[i])
res |= mi[i];
}
return res;
}
void makebad(int x , int now , bool newbad[10][10] , bool bad[10][10]){
REP_2(i , j , len , 10) newbad[i][j] = bad[i][j];
REP(i , len)
if (!(now & mi[i]))
newbad[i][g[x][i] - '0'] = 1;
else{
REP(j , 10)
newbad[i][j] = (j == g[x][i] - '0');
}
}
void ins(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = g[x][i] - '0';
}
void reset(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = -1;
}
bool isbad(int x , int now , bool bad[10][10]){
REP(i , len) if (now & mi[i])
if (bad[i][g[x][i] - '0']) return true;
return false;
}
int publiccheck(int st){
for( ; st < n ; ++st){
int res = 0;
REP(i , len)
res += ans[i] == g[st][i] - '0';
if (res != r[st]) return 0;
}
return 1;
}
int dfs(int x , int all , bool bad[10][10]){
if(all == mi[len] - 1) return publiccheck(x + 1);
if (x >= n){
int ret = 1;
REP(i , len){
if (ans[i] != -1 || (all & mi[i])) continue;
int res = -1;
REP(j , 10){
if (!bad[i][j]){
if (res != -1) ret = 2;
res = j;
}
}
if (res == -1) return 0;
ans[i] = res;
}
REP(i , len) out[i] = ans[i];
if (ret > 1) return 2;
return 1;
}
int now = check(x);
if (mm[now] > r[x]) return 0;
bool newbad[10][10];
int ret = 0;
REP_C(i , SZ(ri[r[x] - mm[now]])){
int add = ri[r[x] - mm[now]][i];
if (add & all) continue;
if (isbad(x , add , bad)) continue;
makebad(x , (add | now) , newbad , bad);
ins(x , add);
ret += dfs(x + 1 , (all | add) , newbad);
reset(x , add);
if (ret > 1) {
return ret;
}
}
return ret;
}
string getNumber(vector <string> guesses, vector <int> bulls) {
g = guesses;
r = bulls;
len = g[0].length();
n = SZ(g);
REP_2(i , j , n , i){
if(r[j] < r[i]){
swap(r[i] , r[j]);
swap(g[i] , g[j]);
}
}
FLC(ans , -1);
init();
bool bad[10][10];
RST(bad);
int res = dfs(0 , 0 , bad);
if (res == 0) return "Liar";
if (res > 1) return "Ambiguity";
string ret = "";
REP(i , len){
ret += (out[i] + '0');
}
return ret;
}
};
데이터 int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string guesses[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
int bulls[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
string expected__ = "1337";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string guesses[] = {"0000", "1111", "2222"};
int bulls[] = {2, 2, 2};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string guesses[] = {"666666", "666677", "777777", "999999"};
int bulls[] = {2, 3, 1, 0};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string guesses[] = {"000", "987", "654", "321", "100", "010"};
int bulls[] = {2, 1, 0, 0, 1, 1};
string expected__ = "007";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string guesses[] = {"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"};
int bulls[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
string expected__ = "54";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 5: {
string guesses[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"};
int bulls[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
string expected__ = "4266642";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 6: {
string guesses[] = {"689717881","729469886","836709781","182159888","389571851","802979001","855698811","883017381","287479881","689187881","186272081","549279841","829259582","889209851","465277831","489034841","854257830","583859981","451171881","829977181","589259281","584819788","189275655","389989186","888219281","389364881","289619892","488379911","739371471","399229321","589077481","889372855","074279488","489276833","879734481","849279825","715279981","386309883","899779505","115174081","687279667","987289061","789279812","082577871","419709881","178279821","587503881","815432882","809271664","886556286"};
int bulls[] = {5,4,4,4,5,4,3,4,6,5,5,6,5,7,4,4,3,4,4,5,6,3,4,4,6,5,4,4,3,4,5,5,4,5,4,6,5,4,4,3,4,4,6,4,5,5,4,3,4,3};
string expected__ = "ABC";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 7: {
string guesses[] = {"000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999"};
int bulls[] = {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,2,0};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 8: {
string guesses[] = {"00000000", "10000001", "07000008", "02000020", "00600070", "00300300", "00050600", "00044000", "80005000"};
int bulls[] = {0, 1, 1, 1, 1, 1, 1, 1, 1};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
default:
return -1;
}
}
}
typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned UINT;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}
/* -&$&#*( &#*@)^$@&*)*/
const int MOD = 1000000007;
const int INF = 0x7fffffff;
const int N = 50;
typedef vector<int> VI;
class EllysBulls {
public:
vector <string > g ;
VI r;
int len , n;
int ans[100] , out[100];
int mm[1 << 10] , mi[10];
VI ri[10];
void init(){
REP(i , len) {ri[i].clear() , mi[i] = 1 << i;}
REP_C(i , (1 << len)){
mm[i] = 0;
int j = i;
while(j){
mm[i] += j & 1;
j >>= 1;
}
ri[mm[i]].PB(i);
}
}
int check(int x){
int res = 0;
REP(i , len){
if (ans[i] != -1 && g[x][i] == '0' + ans[i])
res |= mi[i];
}
return res;
}
void makebad(int x , int now , bool newbad[10][10] , bool bad[10][10]){
REP_2(i , j , len , 10) newbad[i][j] = bad[i][j];
REP(i , len)
if (!(now & mi[i]))
newbad[i][g[x][i] - '0'] = 1;
else{
REP(j , 10)
newbad[i][j] = (j == g[x][i] - '0');
}
}
void ins(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = g[x][i] - '0';
}
void reset(int x , int now){
REP(i , len) if (now & mi[i])
ans[i] = -1;
}
bool isbad(int x , int now , bool bad[10][10]){
REP(i , len) if (now & mi[i])
if (bad[i][g[x][i] - '0']) return true;
return false;
}
int publiccheck(int st){
for( ; st < n ; ++st){
int res = 0;
REP(i , len)
res += ans[i] == g[st][i] - '0';
if (res != r[st]) return 0;
}
return 1;
}
int dfs(int x , int all , bool bad[10][10]){
if(all == mi[len] - 1) return publiccheck(x + 1);
if (x >= n){
int ret = 1;
REP(i , len){
if (ans[i] != -1 || (all & mi[i])) continue;
int res = -1;
REP(j , 10){
if (!bad[i][j]){
if (res != -1) ret = 2;
res = j;
}
}
if (res == -1) return 0;
ans[i] = res;
}
REP(i , len) out[i] = ans[i];
if (ret > 1) return 2;
return 1;
}
int now = check(x);
if (mm[now] > r[x]) return 0;
bool newbad[10][10];
int ret = 0;
REP_C(i , SZ(ri[r[x] - mm[now]])){
int add = ri[r[x] - mm[now]][i];
if (add & all) continue;
if (isbad(x , add , bad)) continue;
makebad(x , (add | now) , newbad , bad);
ins(x , add);
ret += dfs(x + 1 , (all | add) , newbad);
reset(x , add);
if (ret > 1) {
return ret;
}
}
return ret;
}
string getNumber(vector <string> guesses, vector <int> bulls) {
g = guesses;
r = bulls;
len = g[0].length();
n = SZ(g);
REP_2(i , j , n , i){
if(r[j] < r[i]){
swap(r[i] , r[j]);
swap(g[i] , g[j]);
}
}
FLC(ans , -1);
init();
bool bad[10][10];
RST(bad);
int res = dfs(0 , 0 , bad);
if (res == 0) return "Liar";
if (res > 1) return "Ambiguity";
string ret = "";
REP(i , len){
ret += (out[i] + '0');
}
return ret;
}
}; int run_test_case(int casenum) {
switch (casenum) {
case 0: {
string guesses[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
int bulls[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
string expected__ = "1337";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 1: {
string guesses[] = {"0000", "1111", "2222"};
int bulls[] = {2, 2, 2};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 2: {
string guesses[] = {"666666", "666677", "777777", "999999"};
int bulls[] = {2, 3, 1, 0};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 3: {
string guesses[] = {"000", "987", "654", "321", "100", "010"};
int bulls[] = {2, 1, 0, 0, 1, 1};
string expected__ = "007";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 4: {
string guesses[] = {"28", "92", "70", "30", "67", "63", "06", "65",
"11", "06", "88", "48", "09", "65", "48", "08"};
int bulls[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
string expected__ = "54";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 5: {
string guesses[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
"4166623", "1166638", "2767693", "8650248", "2486509",
"6138934", "4018642", "6236742", "2961643", "8407361",
"2097376", "6575410", "6071777", "3569948", "2606380"};
int bulls[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
string expected__ = "4266642";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
// custom cases
case 6: {
string guesses[] = {"689717881","729469886","836709781","182159888","389571851","802979001","855698811","883017381","287479881","689187881","186272081","549279841","829259582","889209851","465277831","489034841","854257830","583859981","451171881","829977181","589259281","584819788","189275655","389989186","888219281","389364881","289619892","488379911","739371471","399229321","589077481","889372855","074279488","489276833","879734481","849279825","715279981","386309883","899779505","115174081","687279667","987289061","789279812","082577871","419709881","178279821","587503881","815432882","809271664","886556286"};
int bulls[] = {5,4,4,4,5,4,3,4,6,5,5,6,5,7,4,4,3,4,4,5,6,3,4,4,6,5,4,4,3,4,5,5,4,5,4,6,5,4,4,3,4,4,6,4,5,5,4,3,4,3};
string expected__ = "ABC";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 7: {
string guesses[] = {"000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999", "000000000", "111111111", "222222222", "333333333", "444444444", "555555555", "666666666", "777777777", "888888888", "999999999"};
int bulls[] = {1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,2,0};
string expected__ = "Liar";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
case 8: {
string guesses[] = {"00000000", "10000001", "07000008", "02000020", "00600070", "00300300", "00050600", "00044000", "80005000"};
int bulls[] = {0, 1, 1, 1, 1, 1, 1, 1, 1};
string expected__ = "Ambiguity";
clock_t start__ = clock();
string received__ = EllysBulls().getNumber(vector <string>(guesses, guesses + (sizeof guesses / sizeof guesses[0])), vector <int>(bulls, bulls + (sizeof bulls / sizeof bulls[0])));
return verify_case(casenum, expected__, received__, clock()-start__);
}
default:
return -1;
}
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
