#include <iostream>
#include <vector>
#include <limits>

#define DEBUG_TRIAL false

class Trial{
    public:
        const size_t HEIGHT;
        std::string record;
        
        //Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
        //Eggs is the eggs remaining.
        //Start is the bottom floor.
        //End is one above the top floor.
        const size_t BREAKING_HEIGHT;
        size_t eggs;
        size_t start;
        size_t end;
        
        
        size_t floorsLeft(){
            return (end-start);
        }
        
        size_t middle(){
            return start + (floorsLeft()/2UL);
        }
        
        size_t drops = 0;
        Trial(const size_t BREAKING_HEIGHT, size_t eggs, size_t start, size_t end): BREAKING_HEIGHT(BREAKING_HEIGHT), eggs(eggs), start(start), end(end), HEIGHT(end), record(end, '_'){
            record[BREAKING_HEIGHT] = 'B'; //Marking the breaking point
        }
        
        bool foundAnswer(){
            return ((record[0] == 'X') || (record.find("OX")!=std::string::npos));
        }
        
        //returns true if the egg broke.
        //height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
        bool drop(size_t height){
            
            #if DEBUG_TRIAL
                std::cout << "Start: " << start << ". End: " << end << ". Floors Left: " << floorsLeft() << ". Middle Index: " << middle() << std::endl;
            #endif
            
            drops++;
            bool cracked = height >= BREAKING_HEIGHT;
            if(cracked) --eggs;
            
            //Update the record
            record[height] = (height >= BREAKING_HEIGHT)? 'X' : 'O';
            
            #if DEBUG_TRIAL
                //Print the record
                std::cout << record << std::endl;
            #endif
        
            return cracked;
        }
        
        size_t nowWhat(){
            if(foundAnswer()){
                return drops;
            }else if(eggs <= 0){ //Ran out of eggs
                throw "Algorithm failed! No more eggs!";
                return 1UL;
            }else if(eggs > 1){
                return wrecklessSearch();
            }else{
                return safeSearch();
            }
        }
        
        size_t safeSearch(){
            if(drop(start)){
                --end;
            }else{
                ++start;
            }
            
            return nowWhat();
        }
        
        size_t wrecklessSearch(){
            //If the egg breaks
            if(drop(middle())){
                end -= (floorsLeft()/2UL);
            }else{ //egg doesn't crack
                start += (floorsLeft()/2UL);
            }
            
            return nowWhat();
        }
        
        //returns the amount of drops needed to find the answer
        size_t search(){
            return nowWhat();
        }
};

//Height is the height of the building in floors.
//Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
//Eggs is the eggs given.
//returns the amount of drops needed to find the answer
size_t search(const size_t height, const size_t BREAKING_HEIGHT, size_t eggs){
    Trial trial(BREAKING_HEIGHT, eggs, 0, height);
    return trial.search();
}

class TrialStats {
    public:
        size_t min = std::numeric_limits<size_t>::max();
        size_t max = 0;
        double mean = -1.0;
        
        void printStats(){
            // Print the results
            std::cout << "Minimum drops: " << min << std::endl;
            std::cout << "Maximum drops: " << max << std::endl;
            std::cout << "Mean drops: " << mean << std::endl;
        }
};

//Benchmarks all the possible breaking points of a single building height with a number of eggs.
TrialStats trial(const size_t HEIGHT, const size_t eggs){
    
    TrialStats stats;
    int totaldrops = 0;

    //Test every possible breaking point
    //Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
    for (int breakingHeight = 0; breakingHeight < HEIGHT; ++breakingHeight) {
        size_t drops = search(HEIGHT, breakingHeight, eggs);

        stats.min = std::min(stats.min, drops);
        stats.max = std::max(stats.max, drops);
        totaldrops += drops;
    }

    // Calculate the mean number of drops
    stats.mean = static_cast<double>(totaldrops) / HEIGHT;
    
    return stats;
}

//Benchmarks a single building height from 1 egg to MAX_EGGS
void testTower(const size_t height, const size_t MAX_EGGS){
    //Drop every amount of eggs that you'd need.
    for (int eggs = 1; eggs <= MAX_EGGS; ++eggs) {
        std::cout << "Building height: " << height << ". Num eggs: " << eggs << std::endl;
        
        TrialStats stats = trial(height, eggs);
        stats.printStats();
        
        std::cout << std::endl << std::endl;
    }
}

//Benchmarks all buildings from 0 to MAX_HEIGHT
void benchmark(const size_t MAX_HEIGHT){
    const size_t MAX_EGGS = 2;
    //Test every building
    for (size_t height = 1; height <= MAX_HEIGHT; ++height) {
        testTower(height, std::min(height, MAX_EGGS));
    }
}

int main() {
    constexpr size_t MAX_HEIGHT = 36;
    
    benchmark(MAX_HEIGHT);

    return 0;
}

#include <iostream>
using namespace std;

int main {
   cout << 1; 
}

#include<iostream>
using namespace std;

const int rows = 8;
const int cols = 8;
char chessboard[rows][cols];

void setBoard(char chessboard[][cols]);
void printBoard(char chessboard[][cols]);

void setBoard(char chessboard[][cols]) {
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            if(i % 2 == 0 && j % 2 == 0) {
                chessboard[i][j] = 'x';
            } else {
                if(i % 2 != 0 && j % 2 == 1) {
                    chessboard[i][j] = 'x';
                } else {
                    chessboard[i][j] = '-';
                }
            }
        }
    }
    return;
}

void printBoard(char chessboard[][cols]) {
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            cout << chessboard[i][j] << " ";
        }
        cout << endl;
    }
    return;
}

int main(int argc, char const *argv[])
{
    setBoard(chessboard);
    printBoard(chessboard);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(vector<int> &hT, int i)
{
  int size = hT.size();
  int largest = i;
  int l = 2 * i + 1;
  int r = 2 * i + 2;
  if (l < size && hT[l] > hT[largest])
    largest = l;
  if (r < size && hT[r] > hT[largest])
    largest = r;

  if (largest != i)
  {
    swap(&hT[i], &hT[largest]);
    heapify(hT, largest);
  }
}
void insert(vector<int> &hT, int newNum)
{
  int size = hT.size();
  if (size == 0)
  {
    hT.push_back(newNum);
  }
  else
  {
    hT.push_back(newNum);
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(hT, i);
    }
  }
}
void deleteNode(vector<int> &hT, int num)
{
  int size = hT.size();
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == hT[i])
      break;
  }
  swap(&hT[i], &hT[size - 1]);

  hT.pop_back();
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(hT, i);
  }
}
void printArray(vector<int> &hT)
{
  for (int i = 0; i < hT.size(); ++i)
    cout << hT[i] << " ";
  cout << "\n";
}

int main()
{
  vector<int> heapTree;

  insert(heapTree, 3);
  insert(heapTree, 4);
  insert(heapTree, 9);
  insert(heapTree, 5);
  insert(heapTree, 2);

  cout << "Max-Heap array: ";
  printArray(heapTree);

  deleteNode(heapTree, 4);

  cout << "After deleting an element: ";

  printArray(heapTree);
}

#include "goat.h" //include goat.h

void Goat::setBreed(string breed) {
   this->breed = breed;
}
void Goat::setWeight(float weight) {
   this->weight = weight;
}
void Goat::setName(string name) {
   this->name = name;
}
void Goat::setGender(char gender) {
   this->gender = gender;
}
void Goat::setSpayed(bool goatIsSpayed) {
   this->goatIsSpayed = goatIsSpayed;
}
void Goat::setRegistrationID(string registrationID) {
   this->registrationID = registrationID;
}
void Goat::setColor(string color) {
   this->color = color;
}
void Goat::setOtherComments(string otherComments) {
   this->otherComments = otherComments;
}
string Goat::getBreed() {
   return breed;
}
float Goat::getWeight() {
   return weight;
}
string Goat::getName() {
   return name;
}
char Goat::getGender() {
   return gender;
}
bool Goat::getSpayed() {
   return goatIsSpayed;
}
string Goat::getRegistrationID() {
   return registrationID;
}
string Goat::getColor() {
   return color;
}
string Goat::getOtherComments() {
   return otherComments;
}

Goat::Goat() {
   breed = "";
   weight = 0.0;
   name = "";
   gender = '\0';
   goatIsSpayed = false;
   registrationID = "";
   color = "";
   otherComments = "";
}

Goat::Goat(string goatBreed, float goatWeight, string goatName, char goatGender, bool goatSpayedStatus, string goatRegistrationID, string goatColor, string goatOtherComments) {
  
   breed = goatBreed;
   weight = goatWeight;
   name = goatName;
   gender = goatGender;
   goatIsSpayed = goatSpayedStatus;
   registrationID = goatRegistrationID;
   color = goatColor;
   otherComments = goatOtherComments;
}

Goat::~Goat() {
   cout << "goat destroyed" << endl;
}

void Goat::printinfo() {  
   cout << "Breed: " << breed << endl << "weight: " << weight << endl << "Name: " << name << endl << "Gender: " << gender << endl << "is Spayed: ";
   if(goatIsSpayed) {  //here I do a logical test on boolean goatIsSpayed. if true cout << true else cout << false
      cout << "True";
   } else {
      cout << "False";
   }
   cout << endl << "Registration ID: " << registrationID << endl << "Color Description: " << color << endl << "Other Comments: " << otherComments << endl << endl;
}

//From https://create.arduino.cc/projecthub/abhilashpatel121/easyfft-fast-fourier-transform-fft-for-arduino-9d2677
#include <cmath>
#include <iostream>
const unsigned char sine_data[] = {	//Quarter a sine wave
	0, 
	4, 9, 13, 18, 22, 27, 31, 35, 40, 44, 
	49, 53, 57, 62, 66, 70, 75, 79, 83, 87, 
	91, 96, 100, 104, 108, 112, 116, 120, 124, 127, 
	131, 135, 139, 143, 146, 150, 153, 157, 160, 164, 
	167, 171, 174, 177, 180, 183, 186, 189, 192, 195, //Paste this at top of program
	198, 201, 204, 206, 209, 211, 214, 216, 219, 221, 
	223, 225, 227, 229, 231, 233, 235, 236, 238, 240, 
	241, 243, 244, 245, 246, 247, 248, 249, 250, 251, 
	252, 253, 253, 254, 254, 254, 255, 255, 255, 255
};
float sine(int i){	//Inefficient sine
	int j=i;
	float out;
	while(j < 0) j = j + 360;
	while(j > 360) j = j - 360;
	if(j > -1 && j < 91) out = sine_data[j];
	else if(j > 90 && j < 181) out = sine_data[180 - j];
	else if(j > 180 && j < 271) out = -sine_data[j - 180];
	else if(j > 270 && j < 361) out = -sine_data[360 - j];
	return (out / 255);
}

float cosine(int i){	//Inefficient cosine
	int j = i;
	float out;
	while(j < 0) j = j + 360;
	while(j > 360) j = j - 360;
	if(j > -1 && j < 91) out = sine_data[90 - j];
	else if(j > 90 && j < 181) out = -sine_data[j - 90];
	else if(j > 180 && j < 271) out = -sine_data[270 - j];
	else if(j > 270 && j < 361) out = sine_data[j - 270];
	return (out / 255);
}

//Example data:

//-----------------------------FFT Function----------------------------------------------//
float* FFT(int in[],unsigned int N,float Frequency){	//Result is highest frequencies in order of loudness. Needs to be deleted.
	/*
	Code to perform FFT on arduino,
	setup:
	paste sine_data [91] at top of program [global variable], paste FFT function at end of program
	Term:
	1. in[] : Data array, 
	2. N : Number of sample (recommended sample size 2,4,8,16,32,64,128...)
	3. Frequency: sampling frequency required as input (Hz)

	If sample size is not in power of 2 it will be clipped to lower side of number. 
	i.e, for 150 number of samples, code will consider first 128 sample, remaining sample will be omitted.
	For Arduino nano, FFT of more than 128 sample not possible due to mamory limitation (64 recomended)
	For higher Number of sample may arise Mamory related issue,
	Code by ABHILASH
	Contact: [email protected] 
	Documentation:https://www.instructables.com/member/abhilash_patel/instructables/
	2/3/2021: change data type of N from float to int for >=256 samples
	*/

	unsigned int sampleRates[13]={1,2,4,8,16,32,64,128,256,512,1024,2048};
	int a = N;
	int o;
	for(int i=0;i<12;i++){		//Snapping N to a sample rate in sampleRates
		if(sampleRates[i]<=a){
			o = i;
		}
	}
		 
	int in_ps[sampleRates[o]] = {}; //input for sequencing
	float out_r[sampleRates[o]] = {}; //real part of transform
	float out_im[sampleRates[o]] = {}; //imaginory part of transform
	int x = 0; 
	int c1;
	int f;
	for(int b=0;b<o;b++){ // bit reversal
		c1 = sampleRates[b];
		f = sampleRates[o] / (c1 + c1);
		for(int j = 0;j < c1;j++){ 
			x = x + 1;
			in_ps[x]=in_ps[j]+f;
		}
	}

	
	for(int i=0;i<sampleRates[o];i++){ // update input array as per bit reverse order
		if(in_ps[i]<a){
			out_r[i]=in[in_ps[i]];
		}
		if(in_ps[i]>a){
			out_r[i]=in[in_ps[i]-a];
		} 
	}


	int i10,i11,n1;
	float e,c,s,tr,ti;

	for(int i=0;i<o;i++){ //fft
		i10 = sampleRates[i]; // overall values of sine/cosine :
		i11 = sampleRates[o] / sampleRates[i+1]; // loop with similar sine cosine:
		e = 360 / sampleRates[i+1];
		e = 0 - e;
		n1 = 0;

		for(int j=0;j<i10;j++){
			c=cosine(e*j);
			s=sine(e*j); 
			n1=j;

			for(int k=0;k<i11;k++){
				tr = c*out_r[i10 + n1]-s*out_im[i10 + n1];
				ti = s*out_r[i10 + n1]+c*out_im[i10 + n1];

				out_r[n1 + i10] = out_r[n1]-tr;
				out_r[n1] = out_r[n1]+tr;

				out_im[n1 + i10] = out_im[n1]-ti;
				out_im[n1] = out_im[n1]+ti; 

				n1 = n1+i10+i10;
			} 
		}
	}

	/*
	for(int i=0;i<sampleRates[o];i++)
	{
	std::cout << (out_r[i]);
	std::cout << ("\t"); // un comment to print RAW o/p 
	std::cout << (out_im[i]); std::cout << ("i"); 
	std::cout << std::endl;
	}
	*/


	//---> here onward out_r contains amplitude and our_in conntains frequency (Hz)
	for(int i=0;i<sampleRates[o-1];i++){ // getting amplitude from compex number
		out_r[i] = sqrt(out_r[i]*out_r[i]+out_im[i]*out_im[i]); // to increase the speed delete sqrt
		out_im[i] = i * Frequency / N;
		std::cout << (out_im[i]); std::cout << ("Hz");
		std::cout << ("\t");	// un comment to print freuency bin 
		std::cout << (out_r[i]);
		std::cout << std::endl;
	}




	x = 0; // peak detection
	for(int i=1;i<sampleRates[o-1]-1;i++){
		if(out_r[i]>out_r[i-1] && out_r[i]>out_r[i+1]){
			in_ps[x] = i; //in_ps array used for storage of peak number
			x = x + 1;
		} 
	}


	s = 0;
	c = 0;
	for(int i=0;i<x;i++){ // re arraange as per magnitude
		for(int j=c;j<x;j++){
			if(out_r[in_ps[i]]<out_r[in_ps[j]]){
				s=in_ps[i];
				in_ps[i]=in_ps[j];
				in_ps[j]=s;
			}
		}
		c=c+1;
	}
	float* f_peaks = new float[sampleRates[o]];
	for(int i=0;i<5;i++){ // updating f_peak array (global variable)with descending order
		f_peaks[i]=out_im[in_ps[i]];
	}
	return f_peaks;
}

//------------------------------------------------------------------------------------//
//main.cpp
int data[64]={
14, 30, 35, 34, 34, 40, 46, 45, 30, 4, -26, -48, -55, -49, -37,
-28, -24, -22, -13, 6, 32, 55, 65, 57, 38, 17, 1, -6, -11, -19, -34, 
-51, -61, -56, -35, -7, 18, 32, 35, 34, 35, 41, 46, 43, 26, -2, -31, -50,
-55, -47, -35, -27, -24, -21, -10, 11, 37, 58, 64, 55, 34, 13, -1, -7
};

int main(){
	const unsigned int SAMPLE_RATE = 48*1000;	//48khz
	auto result = FFT(data,64,SAMPLE_RATE);
	std::cout << result[0] << " " << result[1] << " " << result[2] << " " << result[3] << std::endl;
	delete[] result;
	return 0;
}