ashyk_yigit's blog

By ashyk_yigit, history, 7 weeks ago, In English,

Hello codeforces community. can you help me problem on the dp.
task in russian

Consider an oriented graph G having n vertices numbered by positive integers from 1 to n. In the graph G, there may be several arcs between the same pair of vertices, as well as arcs leading from the vertex to it. Each arc of the graph is marked by some letter of the Latin alphabet. Each path in graph G can be put in correspondence with a string consisting of letters written on successively paths that pass through this path. This is the pathname of the path. We call the string S the path line of the graph G if there exists a path in it whose path label is S.

Your task is to calculate the remainder of dividing by 1 000 000 the number of waypoints of graph G consisting of exactly L symbols.

**Input**

The first line of the input data contains integers n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100) equal to the number of vertices and edges of the graph G, and also the length of the path lines that need to look for. The next m rows define the arcs of the graph G. Each of these lines contains two natural numbers a, b (1 ≤ a, b ≤ n) and a small Latin letter c, which means the presence of an arc from the vertex a to the vertex b marked with the symbol c. Elements of each line are separated from each other by spaces.

**Output**

The only output line must contain one number equal to the remainder of dividing the number of path lines of length L in column G by 1 000 000.

**Test**

4 4 100
1 2 a
2 3 b
3 4 a
4 1 b
ans : 2

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By ashyk_yigit, history, 3 months ago, In Russian,

Hi CF community. I found problem tag of binary indexed tree. I have not any ideas. Help me!
TASK

(Time: 2 seconds Memory: 16 MB)

The famous company "Gold & Silver Soft" decided to take the leading place in the field of development of relational databases. The management of the company understands that for this it is necessary to surprise consumers with the speed of their software product.

It's no secret that the relational database is based on a table that can be considered as a one-dimensional array of records. It is known that when searching all records of the table are viewed sequentially, starting with the very first and ending with the one found.

The technical department of the company has established that it often happens that the search for the same record in the table is made several times. Based on this, the programmers decided after each new search query to change the order of the records in the table. In other words, after searching, the found entry is moved to the first place in the table. Obviously, the more often a specific record is searched, the closer it will be to the beginning of the table and the faster the search for that record will be.

Your task is to write a program that for each of the M consecutive search queries will determine the number of scanned records when searching for a given one. For the sake of simplicity, we assume that there is a table with N records, where the record is a number from 1 to N. At the beginning, all records in the table are arranged in ascending order, i.e., the i-th place in the table contains the number i. For the example below, for M = 2, N = 6, and requests for the search for the numbers "5" and "3", you will need 5 and 4 viewing the records, respectively.Tests have in task.

Input

The first line of the input file INPUT.TXT contains two integers N and M (1 ≤ N, M ≤ 65535) — the number of records in the table and the number of search requests, respectively. The numbers are separated by a single space.

The second line contains M natural numbers Ai (1 ≤ Ai ≤ N) separated by single spaces, where Ai is a query to find the number Ai in the table. Search requests are executed sequentially in the order in which they are entered.

Output

The only output line OUTPUT.TXT must contain M natural numbers separated by single spaces, the i-th number is the number of scanned records when searching for the number Ai.

Thanks in advance!

Read more »

 
 
 
 
  • Vote: I like it  
  • -11
  • Vote: I do not like it  

By ashyk_yigit, history, 3 months ago, translation, In English,

Hi CF! I find problem sqrt decomposition. Sorry my english isn't well.

Roma and Vitala came up with the following game: add and subtract from the number of power two, and after each operation count the number of units in the binary number of this number. Who is faster and more correct, he won.

You have to help them: write a program with which they could check their calculations. The rules of the game are:

At the beginning of the game, the number P is zero. For the entire game, N operations are performed. Each operation is the addition to the number P or subtraction from the number P of the number 2S. After performing each operation, it is necessary to output the number of units in the binary representation of P. It is guaranteed that at any time the number P can not be negative.


Input

The first line of the input file INPUT.TXT contains an integer N (1 ≤ N ≤ 105) — the number of operations. The following N lines specify operations where each operation is specified by one of two lines: "add S" or "sub S", where S (0 ≤ S ≤ 105) is an integer.

The "add S" operation means that 2 S must be added to the P number.

The operation "sub S" means that the number P should subtract 2 S.


Output

For each of the N requests to the output file OUTPUT.TXT on a separate line, output the number of units in the binary record of the number P after performing this operation.

test

4 add 2 add 8 sub 3 sub 0 output: 1 2 6 7

Read more »

 
 
 
 
  • Vote: I like it  
  • -16
  • Vote: I do not like it  

By ashyk_yigit, history, 4 months ago, In Russian,

Hi codeforces. Please help me. How to solve this problem acmp.ru

Horse riding


It is required to make a round of a rectangular field, moving in it according to the rules of a chess horse. In the labyrinth there are cells that can not be moved. The initial position of the horse is determined. It is necessary to visit all cells (in which the transition is possible) without repeated calls. It is guaranteed that such a bypass exists.

Input


The first line of the input file INPUT.TXT contains two natural numbers N and M — the field sizes (N, M ≤ 100). Next, the map of the field follows: N lines of M characters in each line. The symbol "." (Dot) denotes an empty space. The symbol "X" indicates that movement to this cell is prohibited. The initial position of the knight is given by the unique "K" in the field.

Output


In the output file OUTPUT.TXT output the bypass matrix of the field, in each cell of which the step number of its visit must be entered (starting with one). Cells labeled "X" in the input data should be labeled with a zero value when outputting. Numbers should be separated by spaces, it is allowed to use extra spaces. In the case of an ambiguous solution, you should deduce any.

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it  

By ashyk_yigit, history, 4 months ago, In Russian,

Hi codeforces. Please help me! How to solve problem acmp.ru in O(NM) time.
Sorry me English isn't well.
Thanks in advance!

Read more »

 
 
 
 

By ashyk_yigit, history, 9 months ago, In Russian,

Помагите мне пожалуйста как решить эту задача помощью числа каталана.
Условия задача :
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.

Задача acmp.ru Your text to link here...

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By ashyk_yigit, history, 9 months ago, translation, In English,

Помагите мне пожалуйста как решить эту задача Шары и коробки

Read more »

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By ashyk_yigit, history, 10 months ago, In Russian,
 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By ashyk_yigit, history, 13 months ago, In Russian,

дерева отрезков для поиска суммы — http://ideone.com/7wxCdo дерева отрезков для поиска минимума — http://ideone.com/miZuFJ Деревья отрезков, сохраняющие все элементы — http://ideone.com/7R46pK

Read more »

 
 
 
 
  • Vote: I like it  
  • -23
  • Vote: I do not like it