Once upon a time, Hamza was hungry, only leftover food could be found in the fridge, so he wanted to order online.
Hamza currently has $$$x$$$ JDs, and the sandwich he wants to buy costs $$$y$$$ JDs, can Hamza order food online or he has to face his biggest enemies, leftover food?
The first and only line in the input contains exactly 2 space separated integers $$$x,y$$$($$$1 \le x,y \le 10$$$), the amount of money he has, and the cost of the sandwich.
If Hamza can buy the sandwich print "1"(on a single line without quotes), otherwise print "0"(on a single line without quotes).
4 2
1
1 10
0
5 5
1
A prime number is a natural number greater than 1 and has exactly 2 divisors which are 1 and the number itself.
You are given a prime number $$$n$$$, find any 2 prime numbers $$$a$$$ and $$$b$$$ such that $$$a+b=n$$$ or state that no such pair of primes exists.
The input contains a single prime number $$$n$$$($$$2 \le n \le 10^7$$$).
If there doesn't exist any 2 primes such that their summation is equal to $$$n$$$ then print -1, otherwise print the 2 primes on a single line separated by a space.
5
2 3
11
-1
Matryoshka Dolls are Russia's most popular souvenirs. They are sets of wooden figurines of decreasing size placed one inside another, though they have the same exact shape.
Our Matryoshka Doll is known to have an integer size $$$S$$$ which is the largest doll size in the collection, and each doll should have size $$$X$$$ times less than the doll that holds it($$$\textrm{size of the doll} \le \frac{\textrm{size of the doll that holds it}}{X}$$$).
Given $$$S$$$ and $$$X$$$, What is the maximum number of dolls that can be nested inside each other.
The first and only line contains $$$2$$$ integers $$$S,X$$$($$$1 \le S \le 10^9$$$ , $$$2 \le X \le 10^9$$$).
Output one integer, the maximum number of dolls.
10 2
4
Alice was playing her favorite game, "Tales of the Abyss", while playing she encountered the following puzzle that can be described as a $$$12 \times 12$$$ grid:
A robot is standing somewhere in this grid, you can order the robot to move up, down, right or left. The robot can't move to a blocked cell(fully black cell), but it can move to other cells(white and crossed cells). If you order the robot to move to a blocked cell or to move outside the grid then the robot won't move.
The goal of the puzzle is to move the robot to a crossed cell in at most 1000 moves. You will be given the description of some levels of this puzzle that Alice has solved, can you solve them too?
In the first line you will be given the integer $$$L$$$($$$1 \le L \le 134$$$), the number of levels you need to solve.
Then you will be given $$$L$$$ lines describing the levels, each line will contain two integers $$$r,c$$$($$$1 \le r,c \le 12$$$), the row and column of the cell the robot is currently standing at, it's guaranteed that this cell is not a blocked cell(not a fully black cell). The rows are numbered from top(1) to bottom(12), and columns are numbered from left(1) to right(12).
For each level output exactly 2 lines, the first line containing a single integer $$$n$$$($$$0 \le n \le 1000$$$), representing the number of moves you want to make, and the second line a string of length $$$n$$$ made of the letters 'U','D','R' and 'L'(upper_case) meaning Up, Down, Right and Left describing the moves.
Please note that in order to get accepted you have to follow the above format exactly, printing the number of moves and the string on the same line, or printing lower_case letters instead of upper_case for example might give you a wrong answer verdict.
2 2 3 9 4
4 UUDD 3 LDL
In the first level, the robot moves as follows: $$$(2,3)\rightarrow(1,3)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$$$.
In the second level, the robot moves as follows: $$$(9,4)\rightarrow(9,4)\rightarrow(10,4)\rightarrow(10,3)$$$.
Notice that you need to read the statement of "D. Robots Easy" in order to understand this problem.
Also notice the unusual 5 megabytes memory limit.
Alice now is trying to beat the harder version of this puzzle, the only difference from the easy version is that there are 4 robots instead of 1, when ordering the robots to move in a specific direction, all 4 robots move at the same time(that is you can't order a single robot to move).
If the cell the robot should move to is blocked, then the robot doesn't move, if it's empty or crossed then it does move, if the cell already has another robot standing in it then if that robot in that cell is moving then the current robot will also move, otherwise it will not move.
For example if there's a robot in cell $$$(1,1)$$$ and another in cell $$$(1,2)$$$ and you order the robots to move to the left, then both of these robots won't move, but if there's a robot in cell $$$(1,2)$$$ and another in cell $$$(1,3)$$$ and you order the robots to move to the left then both robots will move to the left.
In order to beat the level you need to move the robots such that in the end each robot is standing in a crossed cell. Alice couldn't solve any of the hard levels, can you solve them with at most 1000 moves for a level?
In the first line you will be given the integer $$$L$$$($$$1 \le L \le 1000$$$), the number of levels you need to solve.
Then you will be given $$$L$$$ lines describing the levels, each line will contain eight integers $$$r_1,c_1,r_2,c_2,r_3,c_3,r_4,c_4$$$($$$1 \le r_i,c_i \le 12,1\le i\le 4$$$), the positions of the robots, it's guaranteed that none of the cells are blocked cells and all four cells are distinct.
The output is the same as the easy version.
1 4 2 4 9 11 2 10 10
2 RU
Kassandra is participating in the Arena Olympics of Sparta. In order to win the arena fight, she has to knockout all the other $$$N$$$ fighters.
Being a computer scientist, she wanted to do it while preserving her energy as much as possible, so she wants to win the fight without being noticed by any of the other fighters. To be more exact, she knows the position of each other fighter in the arena, the angle of the center of his field of view, and the range of his field of view.
If she knocks a fighter out while she's in the field of view of another fighter, she will be noticed and she would have to fight everyone face on. So she wonders if there exists an order of fighters to knockout such that no one notices her during the whole process.
Print any permutation such that if she knocks-out the fighters in this order, she won't be noticed. Or print $$$-1$$$ if there exists no such permutation.
Note that Kassandra can move freely while not knocking someone out to get to the position of any other fighter.
The first line of the input will contain an integer $$$N$$$ $$$(1 \le N \le 3000)$$$.
Each of the following lines will contain 4 integers each: $$$x_i$$$, $$$y_i$$$, $$$a_i$$$, $$$r_i$$$ $$$(-10^{6} \le x_i, y_i \le 10^{6}, 0 \le a_i \le 359, 0 \le r_i \le 89)$$$ - the $$$x$$$ coordinate, $$$y$$$ coordinate, the angle of the center of the field of view, and the range of the field of view of the $$$i_{th}$$$ fighter respectively. No two fighters share the same position.
If there exists such a permutation, print the order of the ids of the $$$N$$$ participants on a single line separated by a space. Otherwise, print $$$-1$$$.
4 -2 1 35 25 -3 -2 35 25 0 -3 110 25 2 1 245 25
2 4 3 1
2 -3 -3 45 45 3 3 225 45
-1
The field of view ranges from the angle $$$a-r$$$ to the angle $$$a+r$$$.
Below is the illustration of the first case:
Dr. Diet has a special process. He has $$$n$$$ rooms in each room he has a patient. Each patient can be characterized by two numbers $$$a_i$$$ and $$$b_i$$$. Each day a stupid robot carrying food goes through the rooms starting from the first room. At the room of the $$$i_{th}$$$ patient if the value $$$a_i$$$ is greater than the amount of available food then the robot stops and returns to the charging mount, otherwise, the robot gives the patient $$$a_i$$$ food and continues on to the next patient. If the patient sees more than $$$b_i$$$ food with the robot after taking $$$a_i$$$ food he gets a stroke and dies.
At the end of the day the doctor checks on the patients and reports how many didn't get food and how many died.
He then updates the robot so that it stops giving food to the rooms with dead patients. The doctor is getting old so he came to you to ask for your help.
He needs you to answer two queries:
1) $$$1 $$$ $$$x $$$ the robot was given $$$x$$$ food you need to tell him how many patients died and how many didn't receive food.
2) $$$2$$$ $$$a$$$ $$$b$$$ $$$c $$$ the doctor got a new patient with values $$$a$$$ and $$$b$$$ the patient is given room $$$c$$$. If the room contains a dead patient then he gets thrown out and the new one gets the room otherwise, the old patient gets released and the new patient takes his place.
The first line contains a single integer $$$n $$$ $$$(1 \le n \le 10^5)$$$, the number of rooms.
Each of the next $$$n$$$ lines contains two integers $$$a_i $$$ and $$$b_i $$$ $$$(1\le a_i\le 10^9,1\le b_i\le 10^{18})$$$, the amount of food the patients demands and the amount he can see without getting a stroke,respectively.
The next line contains a single integer $$$q $$$ $$$(1\le q\le 10^5)$$$, the number of queries;
The next $$$q$$$ lines contain the description of the queries:
1) $$$1 $$$ $$$x $$$ $$$(1\le x\le 10^{18}) $$$, $$$1 $$$ represents the first query and $$$x $$$ represents the amount of food the robot carries.
2) $$$2 $$$ $$$a $$$ $$$b $$$ $$$c $$$ $$$(1\le a\le 10^9,1\le b\le 10^{18},1\le c\le n)$$$, $$$2 $$$ represents the second query the values $$$a,b,c$$$ describe the new patient where $$$a$$$ is the amount of food the patient requires, $$$b$$$ is the amount of food the patient can see safely and finally $$$c$$$ is the index of the room the patient is going to use.
For each query of the first type print two integers $$$a$$$ and $$$b$$$. Where $$$a$$$ is the number of patients who died and $$$b$$$ is the number of patients who didn't receive food.
5 1 10 5 12 103 70 1 1 5 3 4 1 400 2 3 13 3 2 5 3 1 1 3
5 0 0 2
3 1 2 2 3 3 4 5 1 6 1 13 2 1 1 1 2 2 4 2 1 20
1 0 2 0 2 0
A $$$\textbf{circumscribed circle}$$$ of a polygon is the circle that passes through all the vertices of that polygon.
Let's assume we have a $$$\textbf{regular}$$$ polygon, we want to find the area of the circumscribed circle around this polygon. Given the number of vertices and the side length of the polygon, can you find the circle's area?
The only line contains $$$2$$$ integers , $$$V(3 \le V \le 359)$$$ the number of vertices of the polygon and $$$S(1 \le S \le 10^9)$$$
Find the area of the resulting circumscribed circle.Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$$\frac{|a-b|}{max(1,b)}\le 10^{-6}$$$.
8 2
21.452136491
The octagon in the picture illustrates the first example.
3 days, that's how much time the king gave Daffy to find him the ultimate army organization plan before he cuts his head off.
2 days already passed with no progress, but luckily Bugs came to the rescue, he gave Daffy the "ultimate"{} plan as a string, unfortunately Daffy couldn't understand this string, now only 4 hours remain.
A soldier can be described in Bugs's string as this: first the $$$id$$$ of the soldier is written then following it $$$x$$$ brackets $$$()$$$ each for a subordinate of this soldier, each subordinate is described inside their bracket in the same way, for example the following string "$$$2(3(4))(1)$$$"{} means that soldier $$$2$$$ is the supervisor of soldiers $$$3$$$ and $$$1$$$, and soldier $$$3$$$ is the supervisor of soldier $$$4$$$, while soldiers $$$1$$$ and $$$4$$$ doesn't supervise any soldiers. The string Bugs gave you describes the king(he has no supervisor) and his subordinates and their subordinates and so on.
Or more formally: $$$$$$ Soldier = Id+Subordinates$$$$$$ $$$$$$ Subordinates = (Soldier)+Subordinates | \phi$$$$$$ where $$$\phi$$$ is the empty string.
Can you figure out the supervisor of each soldier and save Daffy's head?
In the first line you're given an integer $$$n$$$($$$1 \le n \le 1.4 \times 10^5$$$), the number of soldiers(including the king) in the army.
In the second line you're given Bugs's string as described above, the string's length is less than or equal to $$$10^6$$$.
It's guaranteed that each $$$id$$$ from $$$1$$$ to $$$n$$$ appears exactly once in the string.
Output in a single line $$$n$$$ space separated integers, the $$$i$$$th of these integers is the supervisor of the $$$i$$$th soldier or $$$0$$$ if this soldier has no supervisor(he's the king, notice that there will be only one such soldier).
4 2(3(4))(1)
2 0 2 3
7 4(2)(5(3(6)(1))(7))
3 4 5 0 4 3 5
The mayor built a new Zoo. The Zoo looks like a cycle made up of $$$n$$$ animal viewing locations, the locations are numbered from $$$1$$$ to $$$n$$$ where locations $$$i$$$ and $$$i+1$$$ are adjacent and locations $$$1$$$ and $$$n$$$ are also adjacent. Before entering the Zoo, citizens pick two locations $$$a$$$, $$$b$$$ such that $$$(a \neq b)$$$, and one of the two simple paths connecting them(clockwise or counter clockwise) such that the distance between $$$a$$$ and $$$b$$$ is at most $$$k$$$ along that path.
The citizens then starts walking between the locations following 4 conditions:
1) The citizens shouldn't move outside the path between $$$a$$$ and $$$b$$$.
2) All locations between $$$a$$$ and $$$b$$$ along the chosen path should be visited.
3) The walk should end on the starting location $$$a$$$.
4) The length of the walk is at most $$$m$$$.
How many possible walks can the citizens make? print that number module $$$10^9+7$$$.
The input is made up of one line containing $$$3$$$ integers $$$n$$$, $$$k$$$, $$$m$$$, $$$(1 \leq k \lt n \leq 10^5, 1 \leq m \leq 2000)$$$.
Print one integer $$$x$$$ the answer to the problem module $$$10^9+7$$$.
4 3 3
8
10 5 6
160
Today is the Birthday of a beautiful girl, she's happy and she's telling her friends loudly to bring her birthday gifts. One of her best friends who is fond of puzzles decided to bring her a very special gift, a magic box, this box cannot be opened unless the beautiful girl solves the mysterious puzzle written on the box and writes the answer on a small piece of paper under where the puzzle is written.
"You are given an array $$$a$$$, the answer is obtained by doing OR operation to the numbers in each subset of array $$$a$$$, then by summing all the subset ORing results". Help the beautiful girl to find the answer so she can open the magic box and continue celebrating her blessed birthday.
The first line contains integer $$$n(1\le n \le 20),$$$ the size for array $$$a$$$ The second line contains $$$n$$$ integers, $$$a_{i}(1 \le a_{i} \le 10^5)$$$ the array $$$a$$$ elements
Help the beautiful girl to find the answer for the puzzle.
3 1 2 3
18
Note: a subset of an array $$$a$$$ is another array that can be obtained by removing zero or more elements from $$$a$$$.
The first sample subsets:
1
2
3
1|2 = 3
1|3 = 3
2|3 = 3
1|2|3 = 3
Answer = 1+2+3+3+3+3+3 = 18
Where | is the OR operation.
For more information about the OR operation use this link: https://en.wikipedia.org/wiki/Bitwise_operation#OR
You are given a string consisting of letters 'a', 'b' and 'c', and there are 4 kinds of operations you can do on it:
- Replace a character 'a' in the string with "ab".
- Replace a character 'b' in the string with "bc".
- Replace a character 'c' in the string with "ba".
- Remove a substring(consecutive characters) "abc" from the string.
Let $$$n$$$ be the length of the string, can you remove the whole string using at most $$$3n$$$ operations or state that it's impossible to do so?
The first and only line contains the string $$$s$$$($$$1 \le n \le 2\times 10^5$$$) consisting of characters 'a', 'b' and 'c'.
If it's impossible to remove the whole string print -1, otherwise in the first line print $$$m$$$($$$1 \le m \le 3n$$$), the number of operations you will make.
In each of the next $$$m$$$ lines print an operation of the form $$$type_i,index_i$$$($$$1 \le type_i \le 4, 1 \le index_i \le |s|$$$), the type of the $$$i$$$th operation and the index of the character you want to do the $$$i$$$th operation on, if the operation is of type 4, then $$$index_i$$$ should be the index of the first character of the substring "abc" that you want to remove. $$$Index_i$$$ is $$$1-$$$based and the string is updated after each operation, see example notes for better understanding.
acab
4 1 1 4 1 2 2 4 1
bac
-1
This is how the string changes in the first example: acab$$$\rightarrow$$$abcab$$$\rightarrow$$$ab$$$\rightarrow$$$abc$$$\rightarrow\phi$$$, where $$$\phi$$$ is the empty string.