1. Write down an algorithm in pseudo-code whose running time where input is an array whose length defines the problem size. Take the cost of execution of each line of the algorithm as 1.

2. Make comment about the following paragraph:

“You are given two independent algorithms and whose running time complexities are and , respectively. If we add a new line to our algorithm in which it calls the algorithm then the running time complexity of the modified algorithm becomes ”.

1. What will print?
int[][] numbers = { { 1, 2, 3, 4 },{ 5, 6, 7, 8 },{ 9, 10, 11, 12 } };
System.out.println(numbers[1][3]);

a) 13

b) 4

c) 8

d) 12

2. With what value does currYear = yearsArr[2] assign currYear?
int[ ] yearsArr = new int[4];
yearsArr[0] = 1999;
yearsArr[1] = 2012;
yearsArr[2] = 2025;         

a) 4

b) 1999

c) 2012

d) 2025

3. What will print?
String [][] names = { { "Elliot", "Darlene", "Angela", "Tyrell" },
{ "Joanna", "Phillip", "Tomero", "Trenton" },
{ "Mobley", "Whiterose", "Cisco", "Leon", "Mr. Robot" } };
System.out.println(names[2][4]);

a) Elliot

b) Angela

c) Joanna

d) Mr. Robot

4. What will print?
int[][] myNumbers = { {1, 2, 3, 4}, {5, 6, 7, 8}, {1, 2, 3, 4} };
int x = myNumbers[2][2];
System.out.println(x);

a) 5

b) 3

c) 7

d) 8

5. What will print?
int[][] myNumbers = { {1, 2, 3, 4}, {5, 6, 7, 8} };
int x = myNumbers[1][2];
System.out.println(x);

a) 5

b) 3

c) 7

d) 8

Consider two sets of integers represented in arrays, X = [x1, x2, . . . , xn] and Y =
[y1, y2, . . . , yn]. Write two versions of a FindSetUnion(X, Y ) algorithm to find the union of X
and Y as an array. An element is in the union of X and Y if it appears in at least one of X and Y .
You may make use any algorithm introduced in the lectures to help you develop your solution. That
is, you do not have to write the ‘standard’ algorithms – just use them. Therefore, you should be able
to write each algorithm in about 10 lines of code. You must include appropriate comments
in your pseudocode.

question:

(a) [2 Marks] Write a pre-sorting based algorithm of FindSetUnion(X, Y ). Your algorithm
should strictly run in O(n log n).
(b) [2 Marks] Write a Hashing based algorithm of FindSetUnion(X, Y ). Your algorithm should
run in O(n).

Python language!!!!!

№1

The translation from the Berland language into the Birland language is not an easy task. Those languages are very similar: a berlandish word differs from a birlandish word with the same meaning a little: it is spelled (and pronounced) reversely. For example, a Berlandish word code corresponds to a Birlandish word edoc. However, it's easy to make a mistake during the «translation». Vasya translated word s from Berlandish into Birlandish as t. Help him: find out if he translated the word correctly.

Input

The first line contains word s, the second line contains word t. The words consist of lowercase Latin letters. The input data do not consist unnecessary spaces. The words are not empty and their lengths do not exceed 100 symbols.

Output

If the word t is a word s, written reversely, print YES, otherwise print NO.

Examples

input

code
edoc

output

YES

№2

Anton likes to play chess, and so does his friend Danik.

Once they have played n games in a row. For each game it's known who was the winner — Anton or Danik. None of the games ended with a tie.

Now Anton wonders, who won more games, he or Danik? Help him determine this.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of games played.

The second line contains a string s, consisting of n uppercase English letters 'A' and 'D' — the outcome of each of the games. The i-th character of the string is equal to 'A' if the Anton won the i-th game and 'D' if Danik won the i-th game.

Output

If Anton won more games than Danik, print "Anton" (without quotes) in the only line of the output.

If Danik won more games than Anton, print "Danik" (without quotes) in the only line of the output.

If Anton and Danik won the same number of games, print "Friendship" (without quotes).

Examples

input

6
ADAAAA

output

Anton

№3

You can not just take the file and send it. When Polycarp trying to send a file in the social network "Codehorses", he encountered an unexpected problem. If the name of the file contains three or more "x" (lowercase Latin letters "x") in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed.

Determine the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. Print 0 if the file name does not initially contain a forbidden substring "xxx".

You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by 11. For example, if you delete the character in the position 22 from the string "exxxii", then the resulting string is "exxii".

Input

The first line contains integer nn (3≤n≤100)(3≤n≤100) — the length of the file name.

The second line contains a string of length nn consisting of lowercase Latin letters only — the file name.

Output

Print the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. If initially the file name dost not contain a forbidden substring "xxx", print 0.

Examples

input

6
xxxiii

output

1

write a persuasive essay of 250 words about the use of technology .

Implement a dictionary application using C++ with the following features:

• Load a dictionary file.

• Given a prefix string that the user specifies, print the first word or all words in the dictionary with that string as their prefix.

• Given two strings A and B that the user specifies, replace all occurrences of A in the dictionary file with B.

• Spawning a new editor (e.g., vim) to allow the user to modify the dictionary file. Save the dictionary file afterwards.

You must use either C or C++ to implement your dictionary application. All your source code must be put within one (1) file. You will only submit that one file.

Your program should not have any extra library dependencies.

Please provide the coding in C++.

Person class
You will implement the Person Class in Visual Studio. A person object may be associated with multiple accounts. A person initiates activities (deposits or withdrawal) against an account that is captured in a transaction object.
A short description of each class member is given below:

Person
Class
Fields
-   password : string

Properties
+   «C# property, setter private» IsAuthenticated : bool
+   «C# property, setter absent» SIN : string
+   «C# property, setter absent» Name : string

Methods
+   «Constructor» Person(name : string, sin : string)
+   Login(password : string) : void
+   Logout() : void
+   ToString() : string

Fields:
⦁   password – this private string field represents the password of this person.
(N.B. Password are not normally stored as text but as a hash value. A hashing function operates on the password and the result is stored in the field. When a user supplies a password it is passed through the same hashing function and the result is compared to the value of the field.).
Properties:
⦁   SIN – this string property represents the sin number of this person. This getter is public and setter is absent.
⦁   IsAuthenticated – this property is a bool representing if this person is logged in with the correct password. This is modified in the Login() and the Logout() methods. This is an auto-implemented property, and the getter is public and setter is private
⦁   Name – this property is a string representing the name of this person. The getter is public and setter is absent.
Methods:
⦁   public Person( string name, string sin ) – This public constructor takes two parameters: a string representing the name of the person and another string representing the SIN of this person. It does the following:
⦁   The method assigns the arguments to the appropriate fields.
⦁   It also sets the password to the first three letters of the SIN. [use the Substring(start_position, length) method of the string class]
⦁   public void Login( string password ) – This method takes a string parameter representing the password and does the following:
⦁   If the argument DOES NOT match the password field, it does the following:
⦁   Sets the IsAuthenticated property to false
⦁   Creates an AccountException object using argument AccountEnum.PASSWORD_INCORRECT
⦁   Throws the above exception
⦁   If the argument matches the password, it does the following:
⦁   Sets the IsAuthenticated property is set to true
This method does not display anything
⦁   public void Logout( ) – This is public method does not take any parameters nor does it return a value.
This method sets the IsAuthenticated property to false
This method does not display anything
⦁   public override string ToString( )– This public method overrides the same method of the Object class. It returns a string representing the name of the person and if he is authenticated or not.
ITransaction interface
You will implement the ITransaction Interface in Visual Studio. The three sub classes implement this interface.
A short description of each class member is given below:

ITransaction
Interface
Methods
   Withdraw(amount : double, person : Person) : void
   Deposit(amount : double, person : Person) : void

Methods:
⦁   void Withdraw(double amount, Person person).
⦁   void Deposit(double amount, Person person).

Transaction class
You will implement the Transaction Class in Visual Studio. The only purpose of this class is to capture the data values for each transaction. A short description of the class members is given below:
All the properties are public with the setter absent.
Transaction
Class
Properties
+   «C# property, setter absent » AccountNumber : string
+   «C# property, setter absent» Amount : double
+   «C# property, setter absent» Originator : Person
+   «C# property, setter absent» Time : DateTime

Methods
+   «Constructor» Transaction(accountNumber : string, amount : double, endBalance : double, person : Person, time : DateTime)
+   ToString() : string

Properties:
All the properties are public with the setter absent
⦁   AccountNumber – this property is a string representing the account number associated with this transaction. The getter is public and the setter is absent.
⦁   Amount – this property is a double representing the account of this transaction. The getter is public and the setter is absent.
⦁   Originator – this property is a Person representing the person initiating this transaction. The getter is public and the setter is absent.
⦁   Time – this property is a DateTime (a .NET built-in type) representing the time associated with this transaction. The getter is public and the setter is absent.
Methods:
⦁   public Transaction( string accountNumber, double amount, Person person, DateTime time ) – This public constructor takes five arguments. It assigns the arguments to the appropriate fields.
⦁   public override string ToString( ) – This method overrides the same method of the Object class. It does not take any parameter and it returns a string representing the account number, name of the person, the amount and the time that this transition was completed. [you may use ToShortTimeString() method of the DateTime class]. You must include the word Deposit or Withdraw in the output.
A better type would have been a struct instead of a class.
ExceptionEnum enum
You will implement this enum in Visual Studio. There are seven members:
ACCOUNT_DOES_NOT_EXIST,
CREDIT_LIMIT_HAS_BEEN_EXCEEDED,
NAME_NOT_ASSOCIATED_WITH_ACCOUNT,
NO_OVERDRAFT,
PASSWORD_INCORRECT,
USER_DOES_NOT_EXIST,
USER_NOT_LOGGED_IN
The members are self-explanatory.
AccountException class
You will implement the AccountException Class in Visual Studio. This inherits from the Exception Class to provide a custom exception object for this application. It consists of seven strings and two constructors:
AccountException
Class
→ Exception
Fields

Properties

Methods
+   «Constructor» AccountException(reason : ExceptionEnum)

Fields:
There are no fields
Properties:
There are no properties
Methods:
⦁   AccountException( ExceptionEnum reason )– this public constructor simply invokes the base constructor with an appropriate argument. Use the ToString() of the enum type.

M = [4,3,7,6,5,2,4,1,0,7]

Construct a binary search tree for M. Then traverse it (post order)

Written in C++. I need to create function printShort exactly like this description: "printShort ( ) - prints the Date in the format m/d/yy (no leading zeros for month and day, and two last digits for year with leading zeros (use fill digit ‘0’) if necessary). Use the accessors to get the values of the data members. " Right now it is showing the correct output for month and day, but still printing a 4 digit year. How would I only print the last two digits of the variable year? For example, with March 31, 2020 the year's value is set to '2020', but it should be written 3/31/20

Function code:

void Date::printShort(){

    cout<<getMonth()<<"/";
    cout<<getDay()<<"/";
    cout<<setfill('0')<<setw(2)<<getYear();

}//end printShort

Q1. [10 pts, 1pt each] General knowledge of Computer, True or False (fill in T or F)

1. (      ) Register is implemented inside the main memory on computer board.
2. (      ) Von Neumann architecture has data and instructions in the same memory.
3. (      ) Servers are the largest class of computers and span the widest range of applications and performance.
4. (      ) Control unit is active part of the computer, following the instructions of the program to the letter. It adds numbers, tests numbers, controls other components, and so on.
5. (      ) Assembler translates from a high-level notation to assembly language.
6. (      ) Input device is a mechanism that conveys the result of a computation to a user or another computer.
7. (      ) ISA is the interface between software and hardware.
8. (      ) The MIPS architecture as simulated in QtSpim is big-endian.
9. (      ) The addressing mode of instruction sw $t0,32($s0) is PC-relative addressing mode.
10. (      ) Memory in MIPS architecture can store 2³² words.

Python Questions：

Q1. list_1= ['wind', 'spring', 'summer', 'purse', 'great', 'sports']

Use re.search() in the re package and list comprehension to find all words in list_1 that does not contain the letter "r".

Q2.

str_1= '''I live in a room by the sea,
where the view is great and the food is free.
Some of the tenants come and go.
Some I eat, if they're too slow.
One end of me is firmly locked.
The other end just gently rocks.
I live in a room by the sea.
It's perfect for an anemone. '''
Use re.search() in the re package to find all lines that does not start with the letter "s", "S", or "I".

Q3. list_1= ['attitudes', 'ab\nchild', '2!apologies', 'echess', 'fly\n', 'cheer']
Use list comprehension and functions in re package to filter all elements that start with "ch" or end with "es".

Q4. Remove everything from the first occurrence of "e" till end of the string, using the function .sub() from the "re" package

str_1 = 'Two things are infinite: the universe and human stupidity; and I'm not sure about the universe.'

The below mentioned figure shows a General diagnosis flowchart for troubleshooting HP servers. Use
the flowchart to create a C++ program that leads a person through the steps of fixing a bad HP server.
Here is an example of the program’s output (following one of the flow):
Starting General Diagnosis Program.
Recoding symptoms information - DONE.
Rebooting server to see if condition still exists - DONE.
Is this a newly installed server? yes [enter]
Please reseat any components that may have come loose during shipping - DONE.
Rebooting the server - DONE.
Does the condition still exist? no [enter]
Recording all actions taken for future - DONE.
Congratulations, your server problems are solved.
Notice the program ends as soon as a solution is found to the problem.

A situation in which the source of information is more sensitive than the information itself. Explain why the sum of sensitive data might also be sensitive.

*****Software Engineering

Define the following :

QUESTION 1

1.1) Contract Software

1.2) Internal Software Development

1.3) Client

1.4) Object

Briefly describe an example scenario where a strategy design pattern is suitable to use.