dungqt3's blog

By dungqt3, 11 years ago, In English

A hard problem again (at least with me -.-)
PSW is a interesting game. When starting a game, you: a have 5 integers,b,x,y,m. Each step, you can use one of three below operations to convert the pair (a,b) to the pair (x,y). Each operations is one of the following:
1. Addition (P). It can occur if a + b <= m and convert (a,b) to (a+b,b).
2. Subtraction (S). It can occur if a>b and convert (a,b) to (a-b,b).
3. Swap (W). Convert (a,b) to (b,a).
A way to convert the pair (a,b) to the pair (x,y) is described by a string that consists of 3 characters: ‘P’, ‘S’ and ‘W’. For example, converting (3,10) to (3,1) can be done in the following steps: (3,10) -> (10,3) -> (7,3) -> (4,3) ->(1,3) -> (3,1) and the way to play is expressed by string WSSSW.
Described string can compress by replacing all of repeatedly consecutively characters by repeated character and number of iterations (in the case that repeating a character is greater than 1 time) . For example, the string WSSSW can compress to WS3W.
It is guaranteed that string “PP”, “SS”, “WW” don’t appear in the compressed string, the length of answer string is less than or equal to 10000 and the answer is always exist.
Condition: a,b,x,y <= m and m <= 10^9.
Giving 5 numbers a, b, x, y, m, your task is to find the string that describes the way to play.

Example:
INPUT:
3 10 3 1 100
OUTPUT:
WS3W

INPUT:
1 1 1000 1 1000
OUTPUT:
P999

Any ideal to solve it?
Thanks in advance.

Full text and comments »

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

By dungqt3, 11 years ago, In English

I have a problem and do not know how to solve it. that is:

Give a matrix A size of nxn. The task is computing sum of A + A^2 + ... + A^k.

INPUT:
— First line: n, k
— Following n lines, each give n integer
OUTPUT:
— Result matrix with element is remain of module 10

Constraint:
n <= 20
Aij, k <= 10^9

Example:
INPUT:
2 3
0 1
1 1
OUTPUT:
2 4
4 6

This just my homework and i do not have any more test.
Can someone give me some ideal to solve this?
Thanks in advance.
(sorry if my English bad)

Full text and comments »

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