Description

The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

 

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Composite numbers succession (4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, ...). So in order to kill the i-th person, Josephus cousin counts up to the i-th composite.

 

A composite number is a positive integer that has at least one positive divisor other than one or the number itself. In other words, a composite number is any integer greater than one that is not a prime number.

 

For example, there are 6 people in a circle, and the sequence of couting is composite number succession (4, 6, 8, 9, 10, …).

In the beginning, the step to kill m = 4. The sequence of killing people is as follows.

1, 2, 3, 4.............................(kill 4, and m is changed to 6)

5, 6, 1, 2, 3, 5.....................(kill 5, and m is changed to 8)

6, 1, 2, 3, 6, 1, 2, 3.............(kill 3, and m is changed to 9)

6, 1, 2, 6, 1, 2, 6, 1, 2.........(kill 2, and m is changed to 10)

6, 1, 6, 1, 6, 1, 6, 1, 6, 1.....(kill 1)

Then print 6 as answer.

Input

Each line with 1 integers, n. n is the number of people.Input terminated by EOF.

 

Testcase 1 : 1<=n<100

Testcase 2 : 100<=n<1000

Testcase 3 : 1000<=n<10000

Testcase 4 : 10000<=n<50000

Testcase 5 : 50000<=n<100000

Output

The output will consist in separate lines containing the position of the person which life will be saved.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a queue of groups. Each group has a unique ID denoted by a string of uppercase alphabets. The length of an ID is less than or equal to 6 characters.

A new comer has a certain group ID and a personal name. The length of the name is less than or equal to 10. For each new comer, you first check if there exists a group of the same ID. If yes, add this new comer to the end of that group; otherwise, create a new group at the end of the queue, and add this new comer to the new group.

Input

The input contains several lines. Each line presents the group ID and the name of a new comer. The group ID and the name are separated by a space.

The string in the last line is always "END" indicating the end of the input.

Output

The output contains one line. The first string is the ID of the last group in the queue. After that you need to print the name of members in the last group, one by one according to their coming order.
Note that there is a space after every string except the last one, which is ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n <= 10000.

The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.

You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

Your output should contains one line of sequence which represents the order of books from the bottom to the top.
Each number is followed by a single space. And you are asked to add a new line character at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 

Array.cpp
// overloaded assignment operator;
// const return avoids: ( a1 = a2 ) = a3
const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

// determine if two Arrays are equal and
// return true, otherwise return false
bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

// overloaded subscript operator for non-const Arrays;
// reference return creates a modifiable lvalue
int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

// overloaded subscript operator for const Arrays
// const reference return creates an rvalue
int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

// overloaded input operator for class Array;
// inputs values for entire Array
istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

// overloaded output operator for class Array
ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

Inheritance type	Public	Protected	Private
Public data/ functions in the base class	Public in the derived class	Protected in the derived class	Private in the derived class
Protected data/ functions in the base class	Protected in the derived class	Protected in the derived class	Private in the derived class
Private data/fun in the base class	Not accessible in the derived class	Not accessible in the derived class	Not accessible in the derived clas

 
 
 
 
 
 

 

 

 

 

 

Polymorphism
  In the base class
  virtual void foo();
  In the derived class
  virtual void foo() override;

Abstract class and pure virtual function
  virtual void foo() =0;

Prefix/postfix operators
  complex &operator++();  // prefix
  complex operator++(int); // postfix

Operator overloading
  Binary operators
  /*1.non-static member function */
     complex operator+ (const complex&);
  /* 2. non-member function */
     friend complex operator* (const
                      complex&, const complex&);
  Unitary operators
  /*1.non-static member function */
      complex operator-();
  /*2. non-member function */
      friend complex operator~(const complex&);

Inheritance
  class A {
  // A is a base class }
  class B: public A {
  // B inherits A.
  // B is a derived class}

Dynamic allocation
  int *ptr = new int;
  delete ptr;
  int *ptr = new int[100];
  delete [] ptr;

String object
  #include<string>
  using namespace std;
  ...
  string str1 = "Hello";
  string str2 = "World";

Standard C++ Library - <string>

operator[]	For string a, a[pos]: Return a reference to the character at position pos in the string a.
operator+=	Append additional characters at the end of current string.
operator+	Concatenate strings.
operator<	Compare string values. For string a and b, a < b: if a is in front of b in dictionary order, return 1, else return 0.
operator>	Compare string values. For string a and b, a > b: if a is in back of b in dictionary order, return 1, else return 0.
operator==	Compare string values. For string a and b, a == b: if equal, return 1, else return 0;
operator!=	Compare string values. For string a and string b, a != b: if not equal, return 1, else return 0;
compare()	Compare string. For string a and b, a.compare(b): if equal, return 0. If string a is in front of string b in dictionary order, return -1. If string a is in back of string b in dictionary order, return 1.
length()	Return length of string.
swap()	Swap string values.
push_back()	For string a, a.push_back(c): append character c to the end of the string a, increasing its length by one.

 

Standard C++ Library - <sstream>

operator<<	Retrieves as many characters as possible into the stream.
operator>>	Extracts as many characters as possible from the stream.
str	Returns a string object with a copy of the current contents of the stream.

For example(1):
stringstream ss{“Hello”};    // constructor
string str = ss.str();    // a = “Hello”

For example(2):
stringstream ss;
ss<<”75”;
ss<<”76”;
int num;
ss>>num;    // num = 7576

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss