Description
A celebrity is defined as a person who is known by everybody but does not know anyone. How can you find any celebrities among N people?
You can freely ask anyone as follows: “Hey, you know Mr. (or Ms.) X?” Suppose that there are N people. Design a method that
-
determines whether there is some celebrities among the people
-
if there is any celebrities, find them efficiently (minimizing the number of questions you make).
Three code files are given: main.cpp, party.cpp, solve.cpp. The “Party” object has three functions.
setRandomCase(): generates a random case for the relations among people.
askAToKnowB(A, B): check whether A knows B. If true, 1. Otherwise, 0.
answer(x): check whether x is a celebrity or not. It should be called only once
Your task is to implement function “solve” in “solve.cpp” that returns the celebrity. If there is no one, feed function answer() with -1.
Imagine an electric calculator which has only two arithmetic operations, i.e., assignment operation(:=) and multiplication operation (x). We want to let this machine compute b = an for given numbers a and n. Design a method that produce a code for this machine, minimizing the number of multiplications.
Input
16
Output
4124816
