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 Fibonacci numbers succession (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...). So in order to kill the i-th person, Josephus counts up to the i-th Fibonacci number.

For example, there are 6 people in a circle, and the sequence of counting is Fibonacci number succession (1, 1, 2, 3, 5 …).

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

1.............................(kill 1, and m is changed to 1)

2.............................(kill 2, and m is changed to 2)

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

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

5, 6, 5, 6, 5.............(kill 5)

Then print 6 as answer.

 

Let’s solve this problem using C++. You have been provided with the following class definitions:

 

class Node

{

   friend class Josephus;

   public:

        Node():next( NULL ){

        }

          Node( const int &info ) //constructor

      :number( info ), next( NULL )

      {

      } //end ListNode constructor

   private:

          Node *next;

        int number;

};//end class Node

 

class Josephus

{

    public:

         Josephus();

         ~Josephus();

         Josephus(const int &);

         int kill(); // return the survival’s position

 

    private:

        void generatecircularlinkedList(const int &); // generate circular linked-list

        void generateFib(const int &); // generate a Fibonacci sequence table

        int sequence[50]; // store Fibonacci number

        int noOfPeople;

        Node *head;

};

 

REQUIREMENTS:

In this practice, you are asked to implement the following member functions:

Josephus class:

• constructor
• destructor
• int kill();
• void generatecircularlinkedList(const int &);
• void generateFib(const int &);

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class Node { friend class Josephus; public: Node():next( NULL ){ } Node( const int &info ) //constructor :number( info ), next( NULL ) { } //end ListNode constructor private: Node *next; int number; };//end class Node class Josephus { public: Josephus(); ~Josephus(); Josephus(const int &); int kill(); // return the survival’s position private: void generatecircularlinkedList(const int &); // generate circular linked-list void generateFib(const int &); // generate a Fibonacci sequence table int sequence[50]; // store Fibonacci number int noOfPeople; Node *head; }; #endif // FUNCTION_H

main.cpp

#include <iostream> #include "function.h" using namespace std; int main(){ int numofpeople; while(cin>>numofpeople){ Josephus Jose(numofpeople); int survival = Jose.kill(); cout<<survival<<endl; } }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

Each line contains a number n<=45, which is the number of people. Input is terminated by EOF.

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

Partial Judge Code

10996.cpp

Partial Judge Header

10996.h

Tags

Discuss

Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

For case 1,2 : 1<N<100. 0<=length<100

For case 3,4 : 1<N<1000. 0<=length<1000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S, output all different possible set of K characters in the string with P paddings. And sort them in the dictionary order. A padding is expressed as an underline '_'.

For example, if K=2 and P=1, and the given string S is ‘CDBABBD’, the output would be

_AB
_AC
_AD
_BB
_BC
_BD
_CD
_DD
A_B
A_C
A_D
AB_
AC_
AD_
B_B
B_C
B_D
BB_
BC_
BD_
C_D
CD_
D_D
DD_

Input

The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases. For each case, there is a string S, a positive integer K, and a nonnegative integer P in a line. The length of the S is less than or equal to 100 and S contains only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.

For test 1 & 2: T <= 15, K <= 5, P <= 2,  |S| <= 25

T, K, |S| are all positive integers, P is a nonnegative integer, and K <= |S| for all test cases.

Output

For each test case, print all different possible sets of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss