Codeforces Round #201 (Div. 2)

A. Difference Row
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You want to arrange n integers a1, a2, ..., an in some order in a row. Let's define the value of an arrangement as the sum of differences between all pairs of adjacent integers.
More formally, let's denote some arrangement as a sequence of integers x1, x2, ..., xn, where sequence x is a permutation of sequencea. The value of such an arrangement is (x1 - x2) + (x2 - x3) + ... + (xn - 1 - xn).
Find the largest possible value of an arrangement. Then, output the lexicographically smallest sequence x that corresponds to an arrangement of the largest possible value.
Input
The first line of the input contains integer n (2 ≤ n ≤ 100). The second line contains n space-separated integers a1, a2, ..., an(|ai| ≤ 1000).
Output
Print the required sequence x1, x2, ..., xn. Sequence x should be the lexicographically smallest permutation of a that corresponds to an arrangement of the largest possible value.
Sample test(s)
input

5
100 -100 50 0 -50

output

100 -50 0 50 -100 

제목의 뜻

 n  ，          ，              

사고의 방향

    sum = (a1-a2)+(a2-a3)+……(an-1 - an)    ，       ，  a1-an     ，           ，        ，        

 
   
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include
#include
#include
#include
#include
#include
#include
#include
#include
  
B. Fixed Points 
time limit per test 
2 seconds 
memory limit per test 
256 megabytes 
input 
standard input 
output 
standard output 
A permutation of length n is an integer sequence such that each integer from 0 to (n - 1) appears exactly once in it. For example, sequence [0, 2, 1] is a permutation of length 3 while both [0, 2, 2] and [1, 2, 3] are not. 
A fixed point of a function is a point that is mapped to itself by the function. A permutation can be regarded as a bijective function. We'll get a definition of a fixed point in a permutation. An integer i is a fixed point of permutation a0, a1, ..., an - 1 if and only if ai = i. For example, permutation [0, 2, 1] has 1 fixed point and permutation [0, 1, 2] has 3 fixed points. 
You are given permutation a. You are allowed to swap two elements of the permutation at most once. Your task is to maximize the number of fixed points in the resulting permutation. Note that you are allowed to make at most one swap operation. 
Input 
The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n integers a0, a1, ..., an - 1 — the given permutation. 
Output 
Print a single integer — the maximum possible number of fixed points in the permutation after at most one swap operation. 
Sample test(s) 
input 
5
0 1 3 4 2
  
output 
3
  
제목의 뜻
 n  ，   0  ， a[i]=i，   +1，       ，         ，        
  
사고의 방향
    3   ，  +2  +1    。+2          ，+1       ，+0          ，                          
  
 
   
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include
#include
#include
#include
#include
#include
#include
#include
#include
  
C. Alice and Bob 
time limit per test 
2 seconds 
memory limit per test 
256 megabytes 
input 
standard input 
output 
standard output 
It is so boring in the summer holiday, isn't it? So Alice and Bob have invented a new game to play. The rules are as follows. First, they get a set of n distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers x and y from the set, such that the set doesn't contain their absolute difference |x - y|. Then this player adds integer |x - y| to the set (so, the size of the set increases by one). 
If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first. 
Input 
The first line contains an integer n (2 ≤ n ≤ 100) — the initial number of elements in the set. The second line contains n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the set. 
Output 
Print a single line with the winner's name. If Alice wins print "Alice", otherwise print "Bob"(without quotes). 
Sample test(s) 
input 
2
2 3
  
output 
Alice
  
제목의 뜻
 n  ，       ，               X,Y             ，         。Alice  
  
사고의 방향
   XY        。                  ，             ，         。       ，              gcd  ，        gcd              ，        MAX  gcd   。
  
 
     
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include
#include
#include
#include
#include
#include
#include
#include
#include
  
D. Lucky Common Subsequence 
time limit per test 
3 seconds 
memory limit per test 
512 megabytes 
input 
standard input 
output 
standard output 
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence BDF is a subsequence of ABCDEF. A substring of a string is a continuous subsequence of the string. For example, BCD is a substring of ABCDEF. 
You are given two strings s1, s2 and another string called virus. Your task is to find the longest common subsequence of s1 and s2, such that it doesn't contain virus as a substring. 
Input 
The input contains three strings in three separate lines: s1, s2 and virus (1 ≤ |s1|, |s2|, |virus| ≤ 100). Each string consists only of uppercase English letters. 
Output 
Output the longest common subsequence of s1 and s2 without virus as a substring. If there are multiple answers, any of them will be accepted. 
If there is no valid common subsequence, output 0. 
Sample test(s) 
input 
AJKEQSLOBSROFGZ
OVGURWZLWVLUXTH
OZ
  
output 
ORZ
  
제목의 뜻
  3    ，              。     s1,s2   virus            。
  
사고의 방향
 3    A、B、C。
  
                                      C，        C           。
  
        SSSDD C SD，       D， SSDDD       S，     SD         。
  
  CACAC C CAC，          CAC，       C    ，            。
  
 
     
                            C        ，     。
  
                ，           
  
A[i]==B[j]   dp[i][j]=dp[i-1][j-1]+1，  dp[i][j]=max(dp[i-1][j],dp[i][j-1])
  
           C     ，       dp[i][j][k]，k     C           
  
      k，   A[i]==B[j]，           ， C[k+1]!=A[i],         ，          C[k+1]!=A[i]，  k==0 
  
C[k+1]!=A[i]   ，   C       。        kmp   ，    C    ，         kmp       。
  
          ，       ，   pre[i][j][k][3] last[i][j][k][3]     ，pre           ，last        ，   dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])                ，        ，pre last        。     3     i,j,k    。           pre    ，     A[i],  i   0
  
  
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include
#include
#include
#include
#include
#include
#include
#include
#include
  
E. Number Transformation II 
time limit per test 
1 second 
memory limit per test 
256 megabytes 
input 
standard input 
output 
standard output 
You are given a sequence of positive integers x1, x2, ..., xn and two non-negative integers a and b. Your task is to transform a into b. To do that, you can perform the following moves: 
subtract 1 from the current a;   
subtract a mod xi (1 ≤ i ≤ n) from the current a.   
Operation a mod xi means taking the remainder after division of number a by number xi. 
Now you want to know the minimum number of moves needed to transform a into b. 
Input 
The first line contains a single integer n (1 ≤  n ≤ 105). The second line contains n space-separated integers x1, x2, ..., xn(2 ≤  xi ≤ 109). The third line contains two integers a and b (0  ≤ b ≤  a ≤ 109, a - b ≤ 106). 
Output 
Print a single integer — the required minimum number of moves needed to transform number a into number b. 
Sample test(s) 
input 
3
3 4 5
30 17
  
output 
6
  
제목의 뜻
  n  ，  a b，      ，  a-1，  a-a%x[i]，    a  b     
  
사고의 방향
         ，           。       ，  a-a%x[i]    b，        a-a%x[i]     b，  x        。       ，   a-1 a-a%x[i]    ，  a==b
  
  
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include
#include
#include
#include
#include
#include
#include
#include
#include