Description

This problem will give you a sequence of positive integers.  Use this sequence to create a linked list to store those integers.  Next, the problem will give you another sequence of positive integers, p₀, p₁,…p_k-1.  Delete the nodes in the position at p₀, p₁, …p_k-1 of the linked list, where 1<=p₀<p₁<…p_k-1<=N. If the node is not existing,do nothing. And show the final results.

For example, if the first sequence is 1, 2, 3, 4, 5, 6,7, a linked list is created as

If the second sequence is 1, 1, 4, do the follows.

After p₁=1, the list becomes

because the first node is 1.  After p₂ = 1, the list becomes

because the first node is 2.  After p₃ = 4, the list becomes

because the fourth node is 6.

The framework of the program is provided.

1. Create a linked list from the input  (createList)
2. while there are still some data pi
3.     read in pi 
4.     delete node at pi  (deleteNode)
5. print the remaining list (printList)
6. free the list (freeList)

You will be provided with main.c and function.h. main.c contains the implementation of function printList, and freeList, and function.h contains the definition of node and the interface of createList(&head) and deleteNode(&head, pi).  You only need to implement createList(&head) and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the node at pi to be deleted.

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

For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose c compiler) 

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

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head){ Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } } void freeList(Node *head){ Node *temp; for(temp=head; temp!=NULL; temp=head){ head = head->next; free(temp); } } int main() { Node *head; int data; head = createList(); while(1){ scanf("%d", &data); if(data>-1){ deleteNode(&head,data); }else break; } printList(head); freeList(head); return 0; }

function.h

#include <stdlib.h> #include <stdio.h> typedef struct _Node { int data; struct _Node *next; } Node; void deleteNode(Node ** nd, int data); Node* createList();

Input

The input contains 2 sequence of positive integers as the linklist and the order, except the last one, which is -1, indicating the end of the sequence. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Discuss

Description

Define the level 1 string s1 = “OuQ”,
and the level k string sk = “O” + sk−1 + “u” + sk−1 + “Q”.

For example:

• s2 = “O” + s1 + “u” + s1 + “Q” = “OOuQuOuQQ”
• s3 = “OOOuQuOuQQuOOuQuOuQQQ”

Given 3 integeres k,l,r.
Please find all characters of sk[l],sk[l+1],...sk[r−1],sk[r]

Input

There’re multiple testcases in input.
Three integers k,l,r on each line.

• 1 ≤ k ≤ 50
• 0 ≤ l ≤ r < length of sk
• 1 ≤ |r−l+1| ≤ 100

Output

For each testcase, print |r−l+1| characters,sk[l],sk[l+1],...sk[r−1],sk[r], for a line.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Discuss

Description

There will be a launch of a new, powerful and unusual collider very soon, which located along a straight line. n particles will be launched inside it. All of them are located in a straight line and there can not be two or more particles located in the same point. The coordinates of the particles coincide with the distance in meters from the center of the collider, xi is the coordinate of the i-th particle and its position in the collider at the same time. All coordinates of particle positions are even integers.

You know the direction of each particle movement — it will move to the right or to the left after the collider’s launch start. All particles begin to move simultaneously at the time of the collider’s launch start. Each particle will move straight to the left or straight to the right with the constant speed of 1 meter per microsecond. The collider is big enough so particles can not leave it in the foreseeable time.

Write the program which finds the moment of the first collision of any two particles of the collider. In other words, find the number of microseconds before the first moment when any two particles are at the same point.

This Problem is reproduced from http://codeforces.com/problemset/problem/699/A

Input

The first line contains the positive integer n (1  ≤ n  ≤ 200 000) — the number of particles.

The second line contains n symbols “L” and “R”. If the i-th symbol equals “L”, then the i-th particle will move to the left, otherwise the i-th symbol equals “R” and the i-th particle will move to the right.

The third line contains the sequence of pairwise distinct even integers x1,x2,...,xn (0 ≤ xi ≤ 10⁹) — the coordinates of particles in the order from the left to the right. It is guaranteed that the coordinates of particles are given in the increasing order.

Output

In the first line print the only integer — the first moment (in microseconds) when two particles are at the same point and there will be an explosion.

Print the only integer −1, if the collision of particles doesn’t happen.

Remember ‘\n’ on the end of each line.

Sample Input  Download

Sample Output  Download

Discuss

Description

N queens problem asks how many ways to place N non-attacking queens on an N×N chessboard.

For example, there’re 2 solutions for N = 4:
( 0 means empty spot, Q means queen. )

0 Q 0 0     0 0 Q 0
0 0 0 Q     Q 0 0 0
Q 0 0 0     0 0 0 Q
0 0 Q 0     0 Q 0 0

While, there’s no solution for N = 2:
Below is the all placements. All of them contains queens threaten each other.

Q Q    Q 0    Q 0    0 Q    0 Q    0 0
0 0    Q 0    0 Q    Q 0    0 Q    Q Q

Let’s define a new problem “N-Queens M-Rooks Problem”.
It asks how many ways to place N queens and M rooks on an (N+M)×(N+M)( chessboard such that no two of queens or rooks can attack each other in 1 step.

For N = 1, M = 2, there’re 4 solutions:
( 0 means empty spot, Q means queen, R means rook. )

Q 0 0    0 R 0
0 0 R    R 0 0
0 R 0    0 0 Q

0 R 0    0 0 Q
0 0 R    R 0 0
Q 0 0    0 R 0

Possible move of Queen:

Possible move of Rook:

Input

There’re multiple testcases.
Each testcase is consisted of 2 integers N,M on one line.

It’s guaranteed that:

• 0 ≤ N, M ≤ 9
• 1 ≤ N+M ≤ 9

Output

Print the number of solution for N-Queens M-Rooks Problem for every testcase.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Discuss

Description

The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters xi by yi, and all the letters yi by xi. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that xi coincides with yi. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can’t wait to find out what is the new name the Corporation will receive.

Satisfy Arkady’s curiosity and tell him the final version of the name.

This Problem is reproduced from http://codeforces.com/problemset/problem/591/B

Input

The first line of the input contains two integers n and mm (1 ≤ n, m ≤ 200,000)— the length of the initial name and the number of designers hired, respectively.

The second line consists of nn lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers’ actions: the i-th of them contains two space-separated lowercase English letters xi and yi.

Output

Print the new name of the corporation.

Sample Input  Download

Sample Output  Download

Discuss

Description

Chinese New Year is coming.
Bob decides to say “Happy New Year” to his friends.
Bob and his friends reside on the same street.
We can view the street as a straight line, and the position of their houses as points on the straight line.

Bob is at his home at begining.
He wants to visit each of his friend at least once, and then go back to his home.
Because he is too lazy to move, can you help him to find out the minimun distance he should move?

Input

One integer N on the first line, denoting the number of Bob’s friends.
The second line contains N+1 distinct number x0,x1,x2,...,xn
x0 represents the position of Bob’s house.
x1,x2,...,xn represents the position of Bob’s friends.

It’s guaranteed that:

• 1 ≤ N ≤ 2∗10⁵
• 0 ≤ xi ≤ 10⁹

Output

Print the minimun distance he should move in one line.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Discuss

Description

Problem slightly modified from Codeforces Educational Round 13

The girl Taylor has a beautiful calendar for the year y. In the calendar all days are given with their days of week: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday.

The calendar is so beautiful that she wants to know what is the next year after y when the calendar will be exactly the same. Help Taylor to find that year.

Note that leap years has 366 days. The year is leap if it is divisible by 400 or it is divisible by 4, but not by 100 (https://en.wikipedia.org/wiki/Leap_year).

Input

The first line contains an integer T.

The following are T lines, each line contains integer y (1000 ≤ y < 100000) — the year of the calendar.

Output

For each y, print an integer y' — the next year after y when the calendar will be the same. Note that you should find the first year after y with the same calendar.

Sample Input  Download

Sample Output  Download

Discuss

Description

Problem from Codeforces Education round 1

You are given a string s and should process m queries. Each query is described by two 1-based indices li, ri and integer ki. It means that you should cyclically shift the substring s[li... ri] ki times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is "abacaba" and the query is l1 = 3, r1 = 6, k1 = 1 then the answer is "abbacaa". If after that we would process the query l2 = 1, r2 = 4, k2 = 2 then we would get the string "baabcaa".

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 10000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers li, ri and ki (1 ≤ li ≤ ri ≤ |s|, 1 ≤ ki ≤ 1000000) — the description of the i-th query.

Output

Print the resulting string s after processing all m queries.

Sample Input  Download

Sample Output  Download

Discuss

Description

Problem slightly modified from codeforces educational round 80

You are given two integers A and B, calculate the number of pairs (a,b) such that 1≤a≤A, 1≤b≤B, and the equation a⋅b+a+b=conc(a,b) is true.

conc(a,b) is the concatenation of a and b (for example, conc(12,23)=1223, conc(100,11)=10011). a and b should not contain leading zeroes.

Hints

1. For the first test case in sample input, there is only one suitable pair : a=1, b=9 (1+9+1⋅9=19).

2. Since the number is large in this problem, it is suggested to use long long int.

Input

The first line contains t (1≤t≤100) — the number of test cases.

Each test case contains two integers A and B (1≤A, b≤10^9).

Output

Print one integer — the number of pairs (a,b) such that 1≤a≤A, 1≤b≤B, and the equation a⋅b+a+b=conc(a,b) is true.

Sample Input  Download

Sample Output  Download

Discuss

Description

Problem from codeforces educational round 47

Maxim wants to buy some games at the local game shop. There are n games in the shop, the i-th game costs ci.

Maxim has a wallet which can be represented as an array of integers. His wallet contains m bills, the j-th bill has value aj.

Games in the shop are ordered from left to right, Maxim tries to buy every game in that order.

When Maxim stands at the position i in the shop, he takes the first bill from his wallet (if his wallet is empty then he proceeds to the next position immediately) and tries to buy the i-th game using this bill. After Maxim tried to buy the n-th game, he leaves the shop.

Maxim buys the i-th game if and only if the value of the first bill (which he takes) from his wallet is greater or equal to the cost of the i-th game. If he successfully buys the i-th game, the first bill from his wallet disappears and the next bill becomes first. Otherwise Maxim leaves the first bill in his wallet (this bill still remains the first one) and proceeds to the next game.

For example, for array c=[2,4,5,2,4] and array a=[5,3,4,6] the following process takes place: Maxim buys the first game using the first bill (its value is 5), the bill disappears, after that the second bill (with value 3) becomes the first one in Maxim's wallet, then Maxim doesn't buy the second game because c2>a2, the same with the third game, then he buys the fourth game using the bill of value a2 (the third bill becomes the first one in Maxim's wallet) and buys the fifth game using the bill of value a3.

Your task is to get the number of games Maxim will buy.

Input

The first line of the input contains two integers n and m (1≤n,m≤1000) — the number of games and the number of bills in Maxim's wallet.

The second line of the input contains n integers c1,c2,…,cn (1≤ci≤1000), where ci is the cost of the i-th game.

The third line of the input contains m integers a1,a2,…,am (1≤aj≤1000), where aj is the value of the j-th bill from the Maxim's wallet.

Output

Print a single integer — the number of games Maxim will buy.

Sample Input  Download

Sample Output  Download

Discuss

Description

Problem adapted from ICPC SG Preliminary Contest 2018

Author of original problem : Steven Halim

Licence :

Test case is regenerated in this problem

Alice is a chess knight living in Chessland (an N x N board). The cells in Chessland are numbered from 1 to N^2 in row major order. Each cell has an UPPERCASE alphabet character assigned to it. The Chessland is described by a string S of length N^2 (in row major order). For example for N=5 and S = "IXIXXXXCXAXSXXPXXCSXAGXXX", the Chessland that Alice lives in looks like this:

   12345
   -----
 1|IXIXX
 2|XXCXA
 3|XSXXP
 4|XXCSX
 5|AGXXX

As Alice is a chess knight, she can only move from cell (a,b) to cell (c,d) in Chessland if and only if (a−c)^2+(b−d)^2=5. Alice wonder if she can find her favorite string "ICPCASIASG" in Chessland by starting from a cell with character 'I' and finds the other 9 characters by jumping around in Chessland using chess knight movements. Alice can visit the same cell more than once.

You are of course Bob the computing bee and your job is to help her decide the answer.

Input

The first line of input consists of 1 integer: N (1≤N≤100). The second line contains a string S of N^2 UPPERCASE characters ['A'..'Z'] that describe Chessland.

Output

Print "YES" if Alice can find string "ICPCASIASG" in Chessland or print "NO" otherwise.

Sample Input  Download

Sample Output  Download

Discuss