Gym –
101522A

There are two popular formats for representing a date: day/month/year or month/day/year. For example, today can be
represented as 15/8/2017 or 8/15/2017.

Sometimes (like on today), using one way or another should pose no
confusion — it is immediately understood that the date is the 15th of
August. On other days, however, the two representations may be
interpreted as two different valid dates. For example, the 7th of August
may be misinterpreted as the 8th of July, since both can be represented
as 7/8/2017 (or 8/7/2017).

We say a date (D, M, Y) is ambiguous if D/M/Y and M/D/Y, when both
interpreted in the day/month/year
format, are different valid dates. For example, (7, 8, 2017) and (8, 7,
2017) are ambiguous, while (15, 8, 2017) and (10, 10, 2017) are
not.

The total number of ambiguous dates in the Gregorian calendar system on
any given year is equal to 12 × 11 = 132.

Now, suppose that in a hypothetical calendar system, there are M months, where the i-th
month has D[i] days, numbered from 1 to
D[i]. Assume that there are no leap
years.

``````public T get() {
// 获取当前线程的localmap
ThreadLocalMap map = getMap(t);
if (map != null) {
// 用当前的变量作为key查询对象
ThreadLocalMap.Entry e = map.getEntry(this);
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T)e.value;
return result;
}
}
// 如果不存在的话，初始化变量
return setInitialValue();
}

public void set(T value) {
ThreadLocalMap map = getMap(t);
if (map != null)
map.set(this, value);
else
createMap(t, value);
}
``````

You are to carry out a calendar reform, by shuffling the array D[], and your target is to minimize the total
number of ambiguous dates in a calendar year. Specifically, you want to
find a permutation p, p, …, p[M] of integers 1, 2, …, M, such that the new calendar system,
where the i-th month has D[p[i]] days, has the minimal number of
ambiguous dates. Output that minimal
number.

Input

``````private Entry getEntry(ThreadLocal<?> key) {
// 通过当前key的hashcode与列表的长度做 &操作，判断存储的位置
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
if (e != null && e.get() == key)
return e;
else
// 如果不存在的话，进入getEntryAfterMiss方法
// 这种情况，可能是key被回收掉了；也可能是hash冲突了
return getEntryAfterMiss(key, i, e);
}
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
// 这里是典型的线性地址探测法
while (e != null) {
ThreadLocal<?> k = e.get();
if (k == key)
return e;
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}
``````

The first line of input consists of a single integer M, the number of months in the hypothetical calendar
system. The second line of input consists of M integers
D, D, …, D[M], the original
number of days in the i-th
month.

For all test cases, 1 ≤ M ≤ 105, 1 ≤ D[i] ≤ 105.

``````private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;

// expunge entry at staleSlot
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;

// Rehash until we encounter null
Entry e;
int i;
for (i = nextIndex(staleSlot, len);
(e = tab[i]) != null;
i = nextIndex(i, len)) {
ThreadLocal<?> k = e.get();
if (k == null) {
e.value = null;
tab[i] = null;
size--;
} else {
int h = k.threadLocalHashCode & (len - 1);
if (h != i) {
tab[i] = null;

// Unlike Knuth 6.4 Algorithm R, we must scan until
// null because multiple entries could have been stale.
while (tab[h] != null)
h = nextIndex(h, len);
tab[h] = e;
}
}
}
return i;
}
``````

Output

Output a single integer, the minimal number of ambiguous dates after the
calendar reform.

1. 推荐用private修饰，是勿往外部其他的目标呢能够引用到，防止干扰垃圾回收
2. 推介下static，我个人的知道是以将对象存储到艺术去（static修饰的变量会蕴藏在方法区），这样虽然其中的Entry是死引用，但鉴于变量在方法区，也无见面当gc的时节给回收掉。<—个人掌握哈，如发生畸形，还求指正

Example

# 应用

``````public class DefaultMessageManager extends ContainerHolder implements MessageManager, Initializable, LogEnabled {
// we don't use static modifier since MessageManager is configured as singleton

// 每个线程拥有独立的上下文信息
private Context getContext() {
if (Cat.isInitialized()) {
Context ctx = m_context.get();

if (ctx != null) {
return ctx;
} else {
if (m_domain != null) {
ctx = new Context(m_domain.getId(), m_hostName, m_domain.getIp());
} else {
ctx = new Context("Unknown", m_hostName, "");
}

m_context.set(ctx);
return ctx;
}
}

return null;
}

@Override
public void end(Transaction transaction) {
Context ctx = getContext();

if (ctx != null && transaction.isStandalone()) {
if (ctx.end(this, transaction)) {
m_context.remove();
}
}
}
``````

Input

``````12
31 28 31 30 31 30 31 31 30 31 30 31
``````

Output

``````132
``````

Input

``````3
5 1 1
``````

Output

``````0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))

int main()
{
int n,a[MAXN];
ll ans=0,sum;
scanf("%d",&n);
FOR(i,1,n)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
ans+=2*min(a-1,n-1);
FOR(i,2,n)
{
if(a[i]>i)
ans+=2*min(a[i]-i,n-i);
}
printf("%lld\n",ans);
}
``````

Gym –
101522C

To boost contestants’ performances in the 20th La Salle – Pui Ching Programming Challenge,
the organizers have bought N robots to cheer
for them. Each robot is supposed to display cheering slogans, letter by
letter.

Unfortunately, due to some technical reasons, the display screen of each
robot can only display one fixed character. Therefore, the organizers
decided to arrange the robots in a row, thus forming a string of N letters (What a waste!). All letters are in
uppercase.

The two hosting schools have abbreviated names LSC and PCMS,
as we all know. Which of the two names appear (as a substring) in the
string more often?

Input

The first and only line of input consists of a string with N uppercase letters.

For all test cases, N ≤ 100.

Output

Let A be the number of occurrences of LSC in the given string.

Let B be the number of occurrences of PCMS in the given string.

If A > B, output LSC.

If A < B, output PCMS.

If A = B, output Tie.

签到开，直接暴力就好了，不过我给卡了瞬间，似乎是我的编译系统和评测系统不同。

i=1;i<1;i++)在自顿时不会见展开演算，在测评那里就是导致访问越界了。

``````#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define useit  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))

int main()
{
string s;
cin>>s;
int l1=0,l2=0;
if(s.length()>1)
FOR(i,2,s.length()-1)
{
//cout<<s[i-2]<<s[i-1]<<s[i]<<endl;
if(s[i-2]=='L'&&s[i-1]=='S'&&s[i]=='C')
l1++;
}
if(s.length()>2)
FOR(i,3,s.length()-1)
{
//cout<<s[i-3]<<s[i-2]<<s[i-1]<<s[i]<<endl;
if(s[i-3]=='P'&&s[i-2]=='C'&&s[i-1]=='M'&&s[i]=='S')
l2++;
}
if(l1>l2)
cout<<"LSC"<<endl;
else if(l1<l2)
cout<<"PCMS"<<endl;
else
cout<<"Tie"<<endl;
}
``````

Gym –
101522D

The Gregorian calendar is internationally the most widely used civil
calendar. It is named after Pope Gregory XIII, who introduced it in
October 1582.

In the Gregorian calendar, there are 28 days in
February in a common year and 29 days in February
in a leap year. Year Y is a leap year if and
only if Y is a multiple of 400, or Y is a multiple of
4 and is not a multiple of 100.

Percy is curious about the distribution of days of the week of his
birthday in his life. By checking the calendar, he quickly finds that in
the years between 1999 and 2017 (inclusive), his birthday (in case you do not
know, 27 February) appears only twice on both Tuesday and Thursday,
three times on each of the other days of the week.

Percy finds counting the distribution of some days in some consecutive
years really cool, so he decides to invent a way to quickly count the
distribution.

Within 15 minutes, he successfully invented a fast program to do the
calculation for years between 1583 and 2 × 109, inclusive. His program can
answer 5000 queries in 1
second. However, he is not sure if the program works correctly, so he
needs your help. Your task is simple, write your own program to do the
calculation, so that Percy can check his program’s correctness by
comparing the outputs of different queries with your
program.

In this problem, please assume the definition of leap years mentioned
above is true for all years between 1583 and
2 × 109, inclusive.

Input

The first line consists of a single integer, Q,
denotes the number of queries. (1 ≤ Q ≤ 5000)

In the next Q lines, each describes a single
query. The queries are in the format S E
M D, which means you have to calculate the distribution of days of the
week for the D-th day of the M-th month for all years between S and E, inclusive. (1583 ≤ S ≤ E ≤ 2 × 109, the days given are one of the
366 valid
days)

Output

Output Q lines, each answers a query
given.

In each line output 7 integers, the frequencies of days of the weeks in
this order: Sunday, Monday, Tuesday, Wednesday, Thursday, Friday,
Saturday.

The order of answers should follow the order of queries given.

Example

Input

``````1
1999 2017 2 27
``````

Output

``````3 3 2 3 2 3 3
``````

Input

``````2
2017 2017 8 15
2017 2021 2 29
``````

Output

``````0 0 1 0 0 0 0
0 0 0 0 0 0 1
``````

Input

``````4
3141 5926 5 3
5897 9323 8 4
2718 2818 2 8
2222 2222 2 22
``````

Output

``````404 391 403 390 404 396 398
488 488 497 481 497 480 496
15 14 14 15 14 15 14
0 0 0 0 0 1 0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
int isr(int n)
{
if(n%4==0&&n%100!=0||n%400==0)return 1;
else return 0;
}
int da;
//20871
void init()
{
int k,l=6;
k=31,k=28,k=31,k=30,k=31,k=30;
k=31,k=31,k=30,k=31,k=30,k=31;
mst(da);
FOR(i,0,399)
{
FOR(j,1,12)
{
if(j==2)
FOR(t,1,k[j]+isr(i))
{
if(l+1==8)l=0;
da[i][j][t]=++l,da[i+400][j][t]=l;
}
else
FOR(t,1,k[j])
{
if(l+1==8)l=0;
da[i][j][t]=++l,da[i+400][j][t]=l;
}
}
}
}

int main()
{
int q,y1,y2,m,d,t;
ll s;
cin>>q;
init();
while(q--)
{
mst(s);
scanf("%d%d%d%d",&y1,&y2,&m,&d);
if(y2-y1>=400)
{
t=(y2-y1)/400;
FOR(i,y1%400,y1%400+399)
s[da[i][m][d]]+=t;
}
y1%=400,y2%=400;
if(y1>y2) y2+=400;
FOR(i,y1,y2)
{
s[da[i][m][d]]++;
}
FOR(i,1,7)
cout<<s[i]<<" ";
edl;
}
}
``````

Gym –
101522H

“Hit!” is a popular game in ancient Byteland.

The very first version of the game is quite simple: each player picks up
a stone and throws it at a circle drawn on the ground. A player wins if
his/her stone lands inside the circle.

After 20 years of practice, Bitman, a young man living in ancient
Byteland, has mastered the skill of throwing stones – he can throw a
stone at any specific place he wants. With such skill, Bitman plays
“Hit!” without losing a single game. He simply targets every stone at
the center of the circle!

The King of Hackerland hears the story of Bitman and wants to challenge
him with a harder, though still very simple, version of “Hit!”.

In each game, two circles which share a positive common area are drawn
on the ground. In order to win, the player must throw a stone at the
common area of the two circles.

As Bitman had no idea how to target his stone at the common area, he
asks for your help. Given the coordinates of the centers and radii of
the two circles, please tell Bitman the coordinates of any point he can
target at such that he can win the game.

For simplicity, you can consider the landing position of the stone as a
single point.

Input

The input consists of two lines, each describes one circle drawn on the
ground. Each line contains three integers x, y and r, denoting
respectively the x-coordinate, y-coordinate, and the radius of a circle.

All coordinates have their absolute value no more than 100, and 1 ≤ r ≤ 100 for both
circles.

Output

Output two numbers, the x-coordinate and y-coordinate of a point where Bitman can throw his
stone at to win the game.

Your answer will be accepted if for each of the two circles, the point
lies inside the circle or that the distance between the point and the
circle is not greater than 10 - 5.

Example

Input

``````0 0 3
3 4 3
``````

Output

``````1.5 2.5
``````

Input

``````-7 -9 3
-4 -4 5
``````

Output

``````-6 -7
``````

Note

In the first sample, (1.5, 2.5) is a possible
answer as it lies inside the common area of two circles drawn. Please
note that there exists more than one possible answer in this case. For
example, (2, 2), (1, 2)
and (2.1, 1.87) are also possible

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double eps=1e-6;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
struct point
{
double x,y;
point() {}
point(double _a,double _b)
{
x=_a;
y=_b;
}
};

double distan(point p1,point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

double dist(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}

int main()
{
point a,b,c,d,e;
double r1,r2,l,s;
cin>>a.x>>a.y>>r1>>b.x>>b.y>>r2;
l=distan(a,b);
if(l<r1||l<r2)
{
if(l<r1)
cout<<b.x<<" "<<b.y<<endl;
else if(l<r2)
cout<<a.x<<" "<<a.y<<endl;
}
else
{
s=l-r2;
c.x=a.x*l-(a.x-b.x)*s;
c.y=a.y*l-(a.y-b.y)*s;
s=l-r1;
d.x=b.x*l-(b.x-a.x)*s;
d.y=b.y*l-(b.y-a.y)*s;
e.x=(c.x+d.x)/2/l;
e.y=(c.y+d.y)/2/l;
/*while(dist(a,e)>r1*r1)
{
e.x+=(b.x-a.x)*eps;
}
while(dist(b,e)>r2*r2)
{
e.x-=(b.x-a.x)*eps;
}*/
cout<<e.x<<" "<<e.y<<endl;
}
``````

Gym –
101522I

Arya lives in a magical world. You can view it as a number line.

There are N citizens in total. The i-th citizen have his own house in position i with height H*i*, Noted that H*i* could be non positive, which
means their house is actually built beneath the
horizon.

Arya is the hand of the king and she thinks that the buildings are a bit
out of order. She denote the chaos index of the world as .

Noted that h*i* could be equal to zero as the
world is magical.

She feels that the current chaos index of the world is too high. So she
designs to change the world a bit by using her super power.

She could flip a continuous sequence of building, i.e., she could choose
two arbitrary integer L and R, where 1 ≤ L ≤ R ≤ N,
and invert the signs of H*i* for all L ≤ i ≤ R (positive to negative and vice
versa).

As Arya is weak, she would only do this operation exactly once. Arya
wants to minimize the chaos index after the operation. Being a good guy,
help Arya to find the lowest possible chaos index after exactly flipping
one continuous sequence of building.

Input

The first line contains an integer N. (1 ≤ N ≤ 106)

The second line consist of N integers, the
i-th integer is H*i*. ( - 109 ≤ H*i* ≤ 109)

Output

Output consist only one integer in a single line, the lowest possible
chaos index after exactly flipping one continuous sequence of building.

Example

Input

``````4
1 -2 -3 4
``````

Output

``````3
``````

Input

``````5
-3 -2 0 -5 3
``````

Output

``````10
``````

Note

In the first sample, Arya should flip house 2 to 3, so that the heights
become 1, 2, 3, 4 and the chaos index would be
|2 - 1| + |3 - 2| + |4 - 3| = 3.

|x - y| is the absolute difference between
x and y.

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e6+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
int n,a[MAXN],l1=0,l2=0,s1=0,s2=0,k;
int main()
{
ll ans=0;
scanf("%d%d",&n,&a);
FOR(i,2,n)
{
scanf("%d",&a[i]);
ans+=abs(a[i]-a[i-1]);
if(a[i]>0&&a[i-1]<0||a[i]<0&&a[i-1]>0)
{
if(l1==0)
{
l1=i;
s1=2*min(abs(a[i]),abs(a[i-1]));
}
else
{
if(l2==0)
{
l2=i;
s2=2*min(abs(a[i]),abs(a[i-1]));
if(s2>s1)
swap(l1,l2),swap(s1,s2);
}
else
{
k=2*min(abs(a[i]),abs(a[i-1]));
if(k>s1)
l2=l1,s2=s1,l1=i,s1=k;
else if(k>s2)
l2=i,s2=k;
}
}
}
}
printf("%lld\n",ans-s1-s2);
}
``````

Gym –
101522K

The King of Byteland owns an army of well-trained knights. One day, he
decides to attack Hackerland. Hackerland can be described as a grid with
N rows and M columns.
The cell on the i-th row, j-th column is called cell (i, j) for convenience. The north-west corner is
(1, 1) while the south-east corner is (N, M).

In order to win, the Byteland army must occupy all cells with knights.
Now, the King of Byteland has carefully planned the attack. The attack
can be divided into two phases.

In the first phase, a number of knights are sent to some specific cells
of Hackerland.

After the first phase has ended, the second phase begins. In the second
phase, The knights will start attacking the land of Hackerland. Their
only way to attack is as follows: If at any moment, there are two
knights on the same row or the same column, then all unoccupied cells
between the two knights will be under attack, and more knights will be
immediately sent to occupy these cells. This phase will end when no more
cells can be occupied.

Please note that the knights are not allowed to move once they are sent
to Hackerland.

In the following graph, the cells (2, 7), (4, 3), (5, 7) and (8, 3) are occupied in the first phase. When the second phase starts, the cells between (4, 3) and (8, 3), (2, 7) and (5, 7) are under
attack, and then occupied by other knights. Afterwards, the cells
between (4, 3) and (4, 7),
(5, 3) and (5, 7) will
also be occupied. The second phase will end after this as no more cells
can be occupied.

The attack is currently in the first phase. K
cells of Hackerland are already occupied under the command of the King.
You, the leader of the knights, are going to send some more knights
(possibly none) to some cells of Hackerland of your choice before the
second phase starts.

On one hand, you have to send enough knights to ensure that at the end
of the war, all cells are occupied. On the other hand, you have to send
as few knights as possible to minimize the chance of being discovered by
the army of Hackerland. Your task is to find out the minimum number of
knights to be sent.

Input

The first line contains three integers: N,
M and K. (1 ≤ N, M ≤ 100, 0 ≤ K ≤ N·M)

The next K lines each contains two integers:
x and y, which means a
knight was sent by the King to occupy cell (x, y). (1 ≤ x ≤ N, 1 ≤ y ≤ M)

No any two knights are sent to the same cell.

Output

Output an integer, the minimum number of extra knights to be sent, on a
single line.

Example

Input

``````1 1 0
``````

Output

``````1
``````

Input

``````2 2 0
``````

Output

``````4
``````

Input

``````3 3 8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
``````

Output

``````0

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int MAXN=1e5+10;
const double mod=1e16+7;
#define INF 0x7fffffff
#define ll long long
#define edl putchar('\n')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))

int main()
{
int n,m,k,ans,a,b;
scanf("%d%d%d",&n,&m,&k);
if(n==1||m==1)
{
if(n==m)ans=1;
else ans=2;
if(n==1)
FOR(i,1,k)
{
scanf("%d%d",&a,&b);
if(b==1||b==m)ans--;
}
else if(m==1)
FOR(i,1,k)
{
scanf("%d%d",&a,&b);
if(a==1||a==n)ans--;
}
}
else
{
ans=4;
FOR(i,1,k)
{
scanf("%d%d",&a,&b);
if(a==1&&b==m||a==1&&b==1||a==n&&b==1||a==n&&b==m)ans--;
}

}
printf("%d\n",ans);

}
``````