Codeforces 688B Lovely Palindromes

http://codeforces.com/contest/688/problem/B

B. Lovely Palindromes
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pari has a friend who loves palindrome numbers. A palindrome number is a number that reads the same forward or backward. For example 12321, 100001 and 1 are palindrome numbers, while 112 and 1021 are not.

Pari is trying to love them too, but only very special and gifted people can understand the beauty behind palindrome numbers. Pari loves integers with even length (i.e. the numbers with even number of digits), so she tries to see a lot of big palindrome numbers with even length (like a 2-digit 11 or 6-digit 122221), so maybe she could see something in them.

Now Pari asks you to write a program that gets a huge integer n from the input and tells what is the n-th even-length positive palindrome number?

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 10100 000).

Output

Print the n-th even-length palindrome number.

Examples
input

output

input

output

Note

The first 10 even-length palindrome numbers are 11, 22, 33, ... , 88, 99 and 1001.

题意:求第n (1 ≤ n ≤ 10100 000)大的长度为偶数的回文数。

思路:反正是回文,还是偶数的,考虑前半部份就好了。前半部分第n大?不就是n吗?那么把n正着输出一次再倒着输出一次就可以了

 

Codeforces 688A Opponents

http://codeforces.com/contest/688/problem/A

A. Opponents
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Arya has n opponents in the school. Each day he will fight with all opponents who are present this day. His opponents have some fighting plan that guarantees they will win, but implementing this plan requires presence of them all. That means if one day at least one of Arya's opponents is absent at the school, then Arya will beat all present opponents. Otherwise, if all opponents are present, then they will beat Arya.

For each opponent Arya knows his schedule — whether or not he is going to present on each particular day. Tell him the maximum number of consecutive days that he will beat all present opponents.

Note, that if some day there are no opponents present, Arya still considers he beats all the present opponents.

Input

The first line of the input contains two integers n and d (1 ≤ n, d ≤ 100) — the number of opponents and the number of days, respectively.

The i-th of the following d lines contains a string of length n consisting of characters '0' and '1'. The j-th character of this string is '0' if the j-th opponent is going to be absent on the i-th day.

Output

Print the only integer — the maximum number of consecutive days that Arya will beat all present opponents.

Examples
input

output

input

output

input

output

Note

In the first and the second samples, Arya will beat all present opponents each of the d days.

In the third sample, Arya will beat his opponents on days 1, 3 and 4 and his opponents will beat him on days 2 and 5. Thus, the maximum number of consecutive winning days is 2, which happens on days 3 and 4.

题意:Arya要去学校打架,一共有n个人,d天,第i用一个01串表示第i天第j个人是否到学校。当这n个人没有全部同时到学校的时候Arya就可以打赢他们,问最多Arya能连续几天都打赢。

思路:其实就是求一个最长连续子段长度而已……

 

信息学院第十届ACM程序设计竞赛题解

PowerOJ 2541 追风少年

PowerOJ 2544 追风少年的坐骑

PowerOJ 2542 计数少女

PowerOJ 2539 少女输出问题(I)

PowerOJ 2540 少女输出问题(II)

PowerOJ 2545 Lovestring

PowerOJ 2547 逃跑计划

PowerOJ 2546 fork

PowerOJ 2543 赛场布置

PowerOJ 2548 十万火急

PowerOJ 2538 寻找字符串

PowerOJ 2538 寻找字符串

2538: 寻找字符串

Time Limit:1000MS Memory Limit:131072KB

  某天,治愈小妹 和 立体四边形脑袋 在公园里散步,走着走着,我的天!他们各自都捡到了一串漂亮的字符串,然而 脑袋 好奇心比较重,他想知道在 小妹 的字符串中能找出多少自己的字符串,例如 小妹 的字符串为abababa,脑袋 的字符串为aba,那么 脑袋 的字符串在 小妹 的字符串能找到3个。脑袋 一向比较傲娇,于是向在座的各位请教~

PowerOJ 2548 十万火急

2548: 十万火急

Time Limit:1000MS Memory Limit:65536KB

    从前有一个环,环上有N个数,按顺序编号为1到N,每个数都有一个值A[i],现在要你从中选出M个数,使得这M个数的总和最大,注意:选出的M个数中任意两个数都不能在环上相邻(第i个数和第i+1个数相邻,第1个数和第N个数相邻),而且保证输入的M能找出答案。

 

PowerOJ 2543 赛场布置

2543: 赛场布置

Time Limit:5000MS Memory Limit:131072KB

    上决╇ф成功地阻止了大魔王的复活,于是西南科技大学信息工程学院又举行了一年一度的院赛。为了让比赛能够顺利进行,上决╇ф让FM负责布置比赛的其中一个赛场,上决╇ф告诉FM报名参加的只有男生队和女生队两种,赛场可以看做一个N行M列的矩阵教室,每个位置上只可以容纳一支队伍(男生队或者女生队),现在上决╇ф通过某种交易得到了一些数据,这些数据包含的信息如下:

1.如果第i行第j列的位置坐的是男生队,那么此队将得到A[i][j]的战斗力。

2.如果第i行第j列的位置坐的是女生队,那么此队将得到B[i][j]的战斗力。

3.如果第i行第j列的队伍在相邻的位置中有x支异性队伍(相邻指的是两位置有公共边,显然x<=4),那么这个队伍能得到x*C[i][j]的额外战斗力加成,咦哟~

4.如果第i行第j列的队伍在相邻的位置中有x支同性队伍(相邻指的是两位置有公共边,显然x<=4),那么这个队伍的战斗力会减少x*D[i][j]。

上决╇ф要求FM根据上面的数据,合理安排每个位置,使得整个赛场所有队伍的战斗力总和最大。上决╇ф只是让FM布置这一个赛场,所以保证了男生队和女生队数量足够。你能帮FM求出最大的战斗力总和吗?

PowerOJ 2546 fork

2546: fork

Time Limit:2000MS Memory Limit:65536KB

    为了防止大魔王的复活,万能的上决╇ф需要组建一只强大的军队。现在,上决╇ф只有一个小兵,这个兵的编号为1,只会技能0。对于每一个兵,有如下操作:

learn ci pi 让编号为ci的小兵学习pi技能

rollback ci 让编号为ci的小兵遗忘当前学习的那个技能,回滚到上一次学习的技能。

relearn ci  让编号为ci的小兵重新学习上一次遗忘的那个技能。

check ci   检查编号为ci的小兵,刚刚学会的那个技能的编号并输出。

fork ci    将ci小兵复制一个,新的小兵的编号k,k代表第k-1次执行fork操作。

需要注意的是,learn操作,会造成该小兵以前遗忘的技能不可恢复。rollback相当于撤销一次relearn或者learn操作。relearn相当于撤销一次rollback操作。所以relearn和rollback都可以连续执行。进行fork操作是,新的小兵将和原来的小兵完全一模一样,包括以前学习的那些技能和遗忘的那些技能。

一道很容易想到的可持久化数据结构。

由于存在复制操作,对于所有的修改操作,只能修改本体,而不能修改到别的对象。

可持久化的思想就是:修改就新建。

建立节点结构体,包含刚刚学会的技能的id,指向回滚节点的指针和指向重新学习节点的指针。

建立一个映射表M,M[i]指向第i号小兵目前处于哪个节点上(这个节点包含的技能id就是这个小兵刚刚学会的技能)

对于每一次learn c p操作,新建一个节点,填入学习的技能p,这个节点的回滚指向M[c]。这个节点的重新学习不存在,那么指向空即可。这时候,再M[c]=这个节点的地址即可。

对于每一次rollback c操作,新建一个节点,和M[c]的回滚指针指向的节点的内容完全一样,但是要修改这个新建节点的重新学习指针为M[c],这事再M[c]=这个新建的节点。

同理,可以得出relearn c的操作方法。

对于fork c操作,可以不新建,直接令M[new]=M[c]即可。

对于check c操作,输出M[c]指向的节点的技能的ID。

PowerOJ 2547 逃跑计划

2547: 逃跑计划

Time Limit:2000MS Memory Limit:65536KB

在东柳碧芜岭绮,还住着喜欢养狗的FM。起初,FM有N群狗,这些狗群成一排,从东到西,编号分别为1-N。某天,由于大魔王即将复活,FM必须带着他的狗群逃跑来躲避大魔王的统治。为了逃得更快,FM只能带走一群狗,所以FM必须做出艰难的选择。

每一群狗在FM心中都有一个心痛值,FM会在相邻的两群狗中选择出心痛值较高的那一群狗留下来,赶走心痛值较低的那一群,同时受到伤害为心痛值较高的那一群狗的心痛值伤害,然后又在剩下的狗群中执行相同的操作,直到最后只剩下一群狗,因为FM怕痛,所以他希望受到的伤害总和最小。

PowerOJ 2545 Lovestring

2545: Lovestring

Time Limit:1000MS Memory Limit:131072KB

在山的那边海的那边追风少年被浩姐斩杀古刑岳大魔王的英姿迷住了,决定为了浩姐而停下追风的脚步,挑一个良辰吉日表白。

相传有一个叫作东柳碧芜岭绮的地方,那里山清水秀,人杰地灵,还有一个住着爱神上决╇ф的小屋。只要能通过爱神的考验,爱神就会保佑Ta表白成功,幸福美满,子孙满堂,红杏出墙。

在爱神的小屋里,小屋由 N*M 块方形地板组成,每一块地板上都有一个字符,字符只可能是26个大写字母之一或者‘#’。爱神规定少年只能向上下左右四个方向移动,一次只能移动到相邻的地板上,当然不能走出小屋,如果地板上的字符是‘#’,那么这块地板不能走!少年进入小屋之后,他的起点在左上角的地板上,即坐标为(1,1)的地板,而他的终点是房间的右下角,即坐标为(N,M)的地板。由于追风少年每踏上一块地板,都会得到这块地板上的字符(如果追风少年一直站在一块地板上犹豫不决而没有移动,他也只能得到一次这块地板上的字符,只有当追风少年重新踏上这块地板时,才可以再次得到这块地板的字符),那么从起点到终点的路线上获得的字符可以组成一个字符串。为了考验追风少年的诚意,爱神精心打造了一个长度为K的字符串,称之为lovestring,爱神要求少年得到的那个字符串中至少有一个子串为lovestring,而且在这个前提下所走的步数最少!

提示:串中任意个连续的字符组成的子序列称为该串的子串

PowerOJ 2540 少女输出问题(II)

2540: 少女输出问题(II)

Time Limit:5000MS Memory Limit:65536KB

   浩姐发现大魔王居然没被砍死,于是换了把更长的剑和更长的剑法,再看看输出效果吧……