sgu 180 – Inversions (离散化+树状数组)

 – Inversions

Time Limit:250MS     Memory Limit:4096KB     64bit IO Format:%I64d & %I64u

Submit Status


180. Inversions

time limit per test: 0.25 sec. 
memory limit per test: 4096 KB
input: standard 
output: standard

There are N integers (1<=N<=65537) A1, A2,.. AN (0<=Ai<=10^9). You need to find amount of such pairs (i, j) that 1<=iA[j].
The first line of the input contains the number N. The second line contains N numbers A1…AN.
Write amount of such pairs.
Sample test(s)

2 3 1 5 4
一直wa 2

sgu 455. Sequence analysis (floyd 判圈算法,O(1)空间复杂度求循环节)

455. Sequence analysis

Time limit per test: 1 second(s)
Memory limit: 4096 kilobytes
input: standard
output: standard

Due to the slow ‘mod’ and ‘div’ operations with int64 type, all Delphi solutions for the problem 455 (Sequence analysis) run much slower than the same code written in C++ or Java. We do not guarantee that Delphi solution exists. 

You are given a sequence of signed 64-bit integers defined as follows:

  • x0 = 1,
  • ,



is a remainder operator. All arithmetic operations are evaluated without overflow checking. Use standard “remainder” operator for programming languages (it differs from the mathematical version; for example  in programming, while  in mathematics).

Let’s call a sequence element xp repeatable if it occurs later in the sequence — meaning that there exists such qq > p, that xq = xp. The first repeatable element M of the sequence is such an element xmthat xm is repeatable, and none of the xp where p < m are repeatable.

Given AB and C, your task is to find the index of the second occurence of the first repeatable element M in the sequence if the index is less or equal to 2 · 106. Per definition, the first element of the sequence has index 0.


The only line of input contains three signed 64-bit integers: AB and C (B > 0, C > 0).


Print a single integer  — the index of the second occurence of the first repeatable member if it is less or equal to 2 · 106. Print -1 if the index is more than 2 · 106.






In the first sample test the sequence starts with the following numbers: 1, 3, 7, 6, 3, 7. The first repeatable element is 3. The second occurence of 3 has index 4.

In the second sample test the sequence starts with the following numbers: 1, 2305843009213693951, -4611686018427387903, 6917529027641081855, 0, 0, 0. The first repeatable element is 0. The second occurence of 0 has index 5.

In the third sample test the sequence starts with the following numbers: 1, -2, 4, -3, 1, -2, 4. The first repeatable element is 1. The second occurence of 1 has index 4.



直接开了个set判重。。。显然MLE 了。。。

然后这道题的正解是 floyd判圈算法(也叫龟兔算法?)

http://www.cnblogs.com/oyking/p/4286916.html  这份题解讲得很详细

sgu 463 – Walking around Berhattan

K – Walking around Berhattan

Time Limit:250MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u


As you probably know, Berhattan is a district of Berland’s largest city and it consists of equal square blocks. There are n block lines in the east-west direction and m block lines in the south-north direction. The map shows Berhattan as a rectangle with n rows and mcolumns, so there are nm blocks in total.

There are n+1 streets running parallel in the east-west direction (horizontally), and there are m+1 avenues running parallel in the south-north direction (vertically). Streets and avenues split the district into blocks and separate Berhattan from other districts of Berland. Each block in Berhattan is characterized by its beauty bij.

A pedestrian can walk only along streets and avenues. When the pedestrian walks along any of four sides of a block, we say he passes the block. Every time the pedestrian passes a block his satisfaction is increased by bij. If the pedestrian has already passed the block one or more times his satisfaction is increased only by bij/2 rounded down when he passes the block again.

You are given the map of Berhattan with the information about the blocks’ beauty and the pedestrian’s path along the streets and avenues. The path is given as a string containing letters ‘

‘, ‘

‘ and ‘

‘, where ‘

‘ means a 90 degree left turn, ‘

‘ means a 90 degree right turn, and ‘

‘ means walking one block forward by a street or avenue. Facing the east, the pedestrian starts his path in the north-west corner of Berhattan having zero satisfaction level. His path can cross itself and go along the same streets or avenues several times. Pedestrian’s satisfaction is increased every time he moves according to the rules described above.

Your task is to calculate the total satisfaction the pedestrian will get after finishing his route.

Picture of the sample test


The first line of input contains two integers n and m (1 ≤ nm ≤ 100), where n is a number of block lines in Berhattan running in the east-west direction, and m is a number of block lines in Berhattan running in the south-north direction. The following n lines contain m digits each. The j-th digit of the i-th line represents bij (0 ≤ bij ≤ 9) — the beauty of the corresponding block. The last line of input contains a path in the format specified above. The path consists of 1 up to 500 characters, inclusively. It is guaranteed that the given path doesn’t go outside Berhattan.


Print a single integer to the output — the total pedestrian’s satisfaction.

Sample Input



简单模拟,n,m貌似给反了(两个地方给的不一致 )  害我wa了两发

SGU 456 Annuity Payment Scheme

D – Annuity Payment Scheme

Time Limit:500MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u


At the peak of the Global Economic Crisis BerBank offered an unprecedented credit program. The offering was so attractive that Vitaly decided to try it. He took a loan of s burles for m months with the interest rate of p percent. 

Vitaly has to follow the scheme of annuity payments, meaning that he should make fixed monthly payments — x burles per month. Obviously, at the end of the period he will pay m · x burles to the bank in total. 

Each of the monthly payments is divided by BerBank into two parts as follows:

  • The first part ai is used to pay off the percent p of the current debt. It’s clear that ai=s’ · p / 100 where s‘=s for the first month and equals to the remaining debt for each of the subsequent months.
  • The second part bi is used to pay off the current debt. The sum of all bi over the payment period is equal to s, meaning that the borrower needs to pay off the debt completely by decreasing it from s to 0 in m months.

BerBank uses calculations with floating-point numbers, and the value of x is uniquely determined by sm and p

For example, if s=100, m=2, p=50 then x=90. For the first month a1 = s‘ · p / 100 = s · p / 100 = 50 and b1 = 90 – 50 = 40. For the second month a2 = (100-40) · 50 / 100 = 30, so b2 = 90 – 30 = 60 and the debt is paid off completely. 

Your task is to help Vitaly and write a program that computes x given the values of sm and p.


The single line of the input contains three integers sm and p (1 ≤ s ≤ 10 6, 1 ≤ m ≤ 120, 0 ≤ p ≤ 100).


Output the single value of monthly payment x in burles. An absolute error of up to 10 -5 is allowed.

Sample Input




SPOJ AMR10F Cookies Piles

AMR10F – Cookies Piles

no tags 


The kids in my son’s kindergarten made Christmas cookies with their teacher, and piled them up in columns.  They then arranged the columns so that the tops of the columns, going from shortest to tallest, were in a nice straight ramp.  The cookies were all of uniform size.  Given that there were A cookies in the shortest pile, that the difference in height between any two adjacent piles was D cookies, and that there were N piles, can you write a program to figure out how many cookies there were in total? 
The first line contains the number of test cases T. T lines follow, one corresponding to each test case, containing 3 integers : N, A and D. 
Output T lines, each line containing the required answer for the corresponding test case. 
T <= 100 
1 <= N, A, D <=100 

1 1 1 
3 5 6 
2 1 2 


In the second test case the sequence is: 5, 11, 17 whose sum is 33.