MTH 4300: Midterm 1 Practice 5

#include<iostream>
int main(){
   long x;
   std::cin>>x;
   long counterAll=0;
   long countConditions;
   while(x>0){
      countConditions=0;
      if(x % 7 != 0){
         ++countConditions;
      }
      if(((x%5==0) || (x%11==0))&&(x%55 !=0)){
         ++countConditions;
      }
      if(((x>100)&&(x<200))||((x>300)&&(x<400))){
         ++countConditions;
      }
      if(countConditions>0){
         ++counterAll;
      }
      std::cin>>x;
   }
   std::cout<<counterAll<<"\n";
   return 0;
}

Let us first consider the case in which aX+15 is the argument of the function modification. The function creates the variable aA. This variable is the pointer to the sequence aX[15], aX[16], \(\dots\). The value *(aA) is equal to \(40\). The function modification will execute the line *aA=(*aA)*10; The content of aX[15] is changed to \(10\cdot 40=400\). The function returns aA[50]+aA[0]+50 which is equal to \(590\).

We now consider the case in which aX+5 is the argument of the function modification. The function creates the variable aA that points to the sequence aX[5], aX[6], \(\dots\). The value *(aA) is equal to \(20\). The function modification will execute the line *aA=(*aA)*1; The content of aX[5] is changed to \(1\cdot 20=20\). The function returns aA[50]+aA[0]+50 which is equal to \(190\).

The final result is total=400+590+20+190=1200.

The main part of the desired program will be done in the recursive function deleteLastKAndReturnListSize. The input of the function is the pointer to the head of the list and the number \(k\). The function will return the total length of the list and delete the last \(k\) elements. This is how the function will be implemented: We first make a recursive call for the list obtained by removing the head. If the total length of the remaining list was less than \(k\), then we delete the head. It remains to observe that recursion constructed in this way will accomplish the required task. After the recursion is complete, we need to check again whether the total length of the list is smaller than or equal than \(k\). If it is, then the pointer to the head should be set to nullptr since the function has deleted the entire list.

#include<iostream>
struct LN{
public:
  double content;
  LN* aNext;
};
long deleteLastKAndReturnListSize(LN* aH, long k){
  if(aH == nullptr){
    return 0;
  }
  if(aH->aNext==nullptr){
    delete aH;
    return 1;
  }
  long numRemaining=deleteLastKAndReturnListSize(aH->aNext, k);
  if(numRemaining < k){
    delete aH;
  }
  else{
    if(numRemaining == k){
      aH->aNext=nullptr;
    }
  }
  return numRemaining+1;
}
LN* deleteLastKTerms(LN* aH,long k){
  long totalLength=deleteLastKAndReturnListSize(aH,k);
  if(totalLength <= k){
    return nullptr;
  }
  return aH;
}
std::string listToStr(LN* aH){
  if(aH==nullptr){return "";}
  return std::to_string(aH->content)+" "+listToStr(aH->aNext);
}
void deleteList(LN* aH){
  if(aH!=nullptr){
    deleteList(aH->aNext);
    delete aH;
  }
}
int main(){
  LN* aH=nullptr;
  double uI;
  std::cin>>uI;
  if(uI>0.0){
    aH=new LN;
    aH->aNext=nullptr;
    aH->content=uI;
    LN* runner=aH;
    std::cin>>uI;
    while(uI > 0.0){
      runner->aNext = new LN;
      runner = runner->aNext;
      runner->aNext = nullptr;
      runner->content = uI;
      std::cin>>uI;
    }
    long k;
    std::cin>>k;
    aH=deleteLastKTerms(aH,k);
    std::cout<<listToStr(aH)<<"\n";
    deleteList(aH);
  }
}

Assume that \((x_0\), \(x_1\), \(\dots\), \(x_{n-1})\) is an \(m\)-separated sequence of length \(n\) whose sum of terms is \(k\). Let us denote \(d_i=x_i-x_{i-1}-m\) for \(i\in\{1\), \(2\), \(\dots\), \(n-1\}\). Let us introduce \(d_0=x_0-1\). The numbers \(d_0\), \(d_1\), \(d_1\), \(\dots\), \(d_n-1\) are all non-negative. We have \begin{eqnarray*} x_i&=& x_{i-1}+(m+d_i)=x_{i-2}+(m+d_{i-1})+(m+d_i)=\cdots\\ &=& x_0+ (m+d_1)+\cdots + (m+d_{i})\\ &=&(1+d_0)+ (m+d_1)+\cdots + (m+d_{i})\\ &=&1+i\cdot m+ (d_0+d_1+\cdots + d_i). \end{eqnarray*} Let us define \begin{eqnarray*} s_i&=&d_0+d_1+\cdots+ d_i,\quad\mbox{for }i\in\{0, 1, \dots, n-1\}.\end{eqnarray*} With this notation we have \begin{eqnarray*}k &=&x_0+x_1+\cdots+x_{n-1}=\sum_{i=0}^{n-1}\left(1+i\cdot m + s_i\right)\\ &=& n + m\cdot\frac{n(n-1)}2+\left(s_0+s_1+\cdots + s_{n-1}\right). \end{eqnarray*} Since \(s_i\geq 0 \) for every \(i\) we must have \(k\geq n+m\cdot \frac{n(n-1)}2\). It suffices to find the largest integer \(n\) for which \[n+m\cdot\frac{n(n-1)}2\leq k.\] For every \(n\) that satisfies the inequality above, we can easily construct an \(m\)-separated sequence \((y_0\), \(y_1\), \(\dots\), \(y_{n-1})\) whose sum of terms is \(n\). This is the sequence \(y\): \begin{eqnarray*} y_i&=& 1 + i\cdot m,\quad\mbox{for }i\in\{0, 1, \dots, n-2\}\\ y_{n-1}&=&1+(n-1)\cdot m+ \left(n-(y_0+\cdots+y_{n-2})\right). \end{eqnarray*} The complete program is given below.

#include<iostream>
long biggestN(long k, long m){
  long b=0;
  while( b + (b*(b-1)*m/2) <= k){
    ++b;
  }
  return b-1;
}
int main(){
  long m,k;
  std::cin>>m>>k;
  std::cout<<biggestN(k,m)<<"\n";
  return 0;
}