蓝桥杯Python算法训练

蓝桥杯Python组算法训练

1

题目 1017: [编程入门]完数的判断

时间限制: 1Sec 内存限制: 128MB 提交: 23074 解决: 10991

题目描述

一个数如果恰好等于不包含它本身所有因子之和，这个数就称为”完数”。 例如，6的因子为1、2、3，而6=1+2+3，因此6是”完数”。 编程序找出N之内的所有完数，并按下面格式输出其因子

输入

N

输出

? its factors are ? ? ?

样例输入

1000

样例输出

6 its factors are 1 2 3 
28 its factors are 1 2 4 7 14 
496 its factors are 1 2 4 8 16 31 62 124 248 

n=int(input())
list=[]
for i in range(1,n+1):
    sum=0
    for j in range(1,i):
        if(i%j==0):
            sum+=j
            list.append(j)
    if sum==i:
        print(sum,end=' ')
        print('its factors are',end=' ')
        for k in list:
            print(k,end=' ')
        print()
    list=[]

时间超限50%

以下是不超限的题解

a=int(input())
for i in range(2,a):
    b=[1]
    sums=1
    c=int(pow(i,0.5))+1
    for j in range(2,c):
        if i%j==0:
            b.append(j)
            b.append(int(i/j))
            sums+=j+int(i/j)
    if sums==i:
        b.sort()
        print(i,'its factors are ',end='')
        for j in range (len(b)):
            print(b[j],end=' ')
        print()

2

题目 1021: [编程入门]迭代法求平方根

时间限制: 1Sec 内存限制: 128MB 提交: 14256 解决: 7563

题目描述

用迭代法求 平方根

公式：求a的平方根的迭代公式为： X[n+1]=(X[n]+a/X[n])/2 要求前后两次求出的差的绝对值少于0.00001。 输出保留3位小数

输入

X

输出

X的平方根

样例输入

4

样例输出

2.000

from math import *
a=int(input())
b=a/2#从1开始迭代
c=(b+a/b)/2
while abs(c-b)>=0.00001:
    b=c
    c=(b+a/b)/2
print("%.3f"%c)

3

题目 1023: [编程入门]选择排序

时间限制: 1Sec 内存限制: 128MB 提交: 22695 解决: 10654

题目描述

用选择法对10个整数从小到大排序。

输入

输入10个无序的数字

输出

排序好的10个整数

样例输入

4 85  3 234 45 345 345 122 30 12

m=list(map(int,input().split()))
m.sort()
for i in m:
    print(i)

4

题目 1011: [编程入门]最大公约数与最小公倍数

时间限制: 1Sec 内存限制: 128MB 提交: 29761 解决: 16522

题目描述

输入两个正整数m和n，求其最大公约数和最小公倍数。

输入

两个整数

输出

最大公约数，最小公倍数

样例输入

5 7

样例输出

1 35

def gcd(a, b):
    if a%b == 0:
        return b
    else: 
        return gcd(b, a%b)
a, b = map(int, input().split())
if a<b:
    c=a
    a=b
    b=c
s = gcd(a, b)
print("&#123;&#125; &#123;:.0f&#125;".format(s, (a*b)/s))

5

题目 1044: [编程入门]三个字符串的排序

时间限制: 1Sec 内存限制: 128MB 提交: 11726 解决: 5993

题目描述

输入三个字符串，按由小到大的顺序输出

输入

3行字符串

输出

按照从小到大输出成3行

样例输入

cde
afg
abc

样例输出

abc
afg
cde

a=input();b=input();c=input()
x=[a,b,c]
x.sort()
for i in x:
    print(i)

6

题目 1047: [编程入门]报数问题

时间限制: 1Sec 内存限制: 128MB 提交: 8494 解决: 4512

题目描述

有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。

输入

初始人数n

输出

最后一人的初始编号

样例输入

3

样例输出

2

n = int(input())
s = [i for i in range(1,n+1)]
i = 1    # 当前报的数
index = 0    # 当前的位置
while len(s) != 1:    # 当只剩一人的时候退出
    if i == 3:
        del s[index]    # 当前的人报数为3的时候删除，因为当前人的推出index不必+1即代表下一个人
        i = 1    # 从新从1开始报数
    else:
        index += 1
        i += 1
    if index == len(s):    # 报到最后一位时，重新开始从第一个人开始报数
        index = 0
print(s[0])

如果每次len(数组)，会超时

7

题目 1084: 用筛法求之N内的素数。

时间限制: 1Sec 内存限制: 64MB 提交: 16162 解决: 9636

题目描述

用筛法求之N内的素数。

输入

N

输出

0～N的素数

样例输入

100

样例输出

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

a=int(input())
l=[2]
for i in range(2,a+1):
    if i<=2:
        continue
    for m in range(2,i):
        if i%m==0:
            break
    else:
        l.append(i)
it = iter(l)
for x in it:
    print (x, end="\n")

以上有误

8

题目描述

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

输出

对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入

2
4
5
0

样例输出

2
4
6

#递归表达式写出来是n=n-1+n-3

n=int(input())

while n:
    n1, n2, n3 = 4, 3, 2
    k=0
    if n<5:
        print(n)
    else:
        n=n-4
        while n:
            k=n1 +n3
            n3=n2
            n2=n1
            n1=k
            n=n-1
        print(k)
    n=int(input())

9

题目 1093: 字符逆序

时间限制: 1Sec 内存限制: 64MB 提交: 20847 解决: 10636

题目描述

将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。

输入

输入包括一行。 第一行输入的字符串。

输出

输出转换好的逆序字符串。

样例输入

I am a student

样例输出

tneduts a ma I

m=input().split()
m.reverse()
for i in m:
    print(i,end=" ")
#这是按单词逆序

x=input("")
x=x[::-1] #列表切片，逆序输出
print(x)
#按字母输出

10

题目 1094: 字符串的输入输出处理

时间限制: 1Sec 内存限制: 64MB 提交: 19709 解决: 7115

题目描述

字符串的输入输出处理。

输入

第一行是一个正整数N，最大为100。之后是多行字符串（行数大于N）， 每一行字符串可能含有空格，字符数不超过1000。

输出

先将输入中的前N行字符串（可能含有空格）原样输出，再将余下的字符串（不含有空格）以空格或回车分割依次按行输出。每行输出之间输出一个空行。

样例输入

2
www.dotcpp.com DOTCPP
A C M
D O T CPP

样例输出

www.dotcpp.com DOTCPP

A C M

D

O

T

CPP

n=int(input())
for i in range(n):
    str=input()
    print(str)
    print()
while True:#注意这里，保持后续的输入
    str=input().split(' ')
    for i in str :
        print(i)
        print()

11

题目 1097: 蛇行矩阵

时间限制: 1Sec 内存限制: 64MB 提交: 10033 解决: 6737

题目描述

蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

输入

本题有多组数据，每组数据由一个正整数N组成。（N不大于100）

输出

对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。

样例输入

5

样例输出

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

n=int(input())
list1=[ ]
list1.append(1)
for j in range(2,n+1):
    list1.append(list1[-1]+j)
for i in list1:
    print(i,end=' ')
n=n-1
print()
j=1
while n:
    for i in range(n):
        list1[i] = list1[i] + j + i#对这个链表进行更新，保证从上一列取输出
        print(list1[i],end=' ')
    print()
    n=n-1
    j=j+1

12

题目 1110: 2^k进制数

时间限制: 1Sec 内存限制: 128MB 提交: 1953 解决: 966

题目描述

设r是个2^k 进制数，并满足以下条件：
（1）r至少是个2位的2^k 进制数。
（2）作为2^k 进制数，除最后一位外，r的每一位严格小于它右边相邻的那一位。
（3）将r转换为2进制数q后，则q的总位数不超过w。
在这里，正整数k（1≤k≤9）和w（k〈w≤30000）是事先给定的。

问：满足上述条件的不同的r共有多少个？
我们再从另一角度作些解释：设S是长度为w 的01字符串（即字符串S由w个“0”或“1”组成），S对应于上述条件（3）中的q。将S从右起划分为若干个长度为k 的段，每段对应一位2^k进制的数，如果S至少可分成2段，则S所对应的二进制数又可以转换为上述的2^k 进制数r。
例：设k=3，w=7。则r是个八进制数（2^3=8）。由于w=7，长度为7的01字符串按3位一段分，可分为3段（即1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有：
2位数：高位为1：6个（即12，13，14，15，16，17），高位为2：5个，…，高位为6：1个（即67）。共6+5+…+1=21个。
3位数：高位只能是1，第2位为2：5个（即123，124，125，126，127），第2位为3：4个，…，第2位为6：1个（即167）。共5+4+…+1=15个。
所以，满足要求的r共有36个。

输入

只有1行，为两个正整数，用一个空格隔开：
k w

输出

1行，是一个正整数，为所求的计算结果，即满足条件的不同的r的个数（用十进制数表示），要求最高位不得为0，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。
（提示：作为结果的正整数可能很大，但不会超过200位）

样例输入

3  7

样例输出

36

#一开始我想用dfs写，但是看了下题解好像有更简单的方法，把过程类比成二项式求解
n, m = map(int, input().split())
shang, yu = divmod(m, n)


def zuheshu(j, i):
    # 求组合数用
    if i > j:
        return 0
    if j < 0:
        return 0
    sum = 1
    for t in range(i):
        sum = sum * (j - t) //(t + 1)
    return sum


s0 = sum([zuheshu(2 ** n-1, i) for i in range(2, shang + 1)])  # 当没有达到高位，只用非高位求组合数，结果同排序后的结果
s1 = sum([zuheshu(2 ** n - 1 - x0, shang) for x0 in range(1, 2 ** yu)])  # 在全范围内减去高位范围的组合数
print(s1 + s0)

原题链接：2^k进制数

解题思路:

因为只要保证每个位置上的数不相同，自然可以把它们从小到大排列

所以只需从第二个数（从右往左）一直计算当前位置的排列数最后加起来就行

因为除最高位以外，别的位置的范围都是从 1 到 进制数减去当前位置
所以先计算除最高位以外的排列数，再计算最高位的排列数

注意事项:

最高位的排列数应该用减法思维，即拿k=3,w=8来说，最高位只能取1-3，实际计算的时候应该拿最高位可以取1-7的情况减去最高位可以取4-7的情况，因为假设最高位取了2，后面只能比前面大，所以此时要排除后面取1和2的情况，计算量大。如果计算4-7，则最高位和后面都只能取4-7，不存在最高位能取后面不能取的情况，即最高位和后面都只能取4-7等于从4张牌里挑3张，共4种，最高位可以取1-7即7张牌里挑3张，共35种，35减4=31

当然加法也可以做，即最高位取1加最高位取2加最高位取3，即最高位取1，后面6张挑2张，等于15，最高位取2，后面取不了1了，5张挑2张，等于10，最高位取3，后面取不了1和2了，4张挑2张，等于6，15+10+6=31

最终答案用最高位排列数加上最高位以外的排列数即 31+21=52

13

题目 1115: DNA

时间限制: 1Sec 内存限制: 128MB 提交: 9689 解决: 3342

题目描述

小强从小就喜欢生命科学，他总是好奇花草鸟兽从哪里来的。终于， 小强上中学了，接触到了神圣的名词–DNA.它有一个双螺旋的结构。这让一根筋的小强抓破头皮，“要是能画出来就好了” 小强喊道。现在就请你帮助他吧

输入

输入包含多组测试数据。第一个整数N（N<=15）,N表示组数，每组数据包含两个整数a,b。a表示一个单位的DNA串的行数，a为奇数且 3<=a<=39。b表示重复度(1<=b<=20)。

输出

输出DNA的形状，每组输出间有一空行。

样例输入

2
3 1
5 4

样例输出

X X
 X
X X

X   X
 X X
  X
 X X
X   X
 X X
  X
 X X
X   X
 X X
  X
 X X
X   X
 X X
  X
 X X
X   X

n=int(input())
for i in range(n):
    col,num=map(int ,input().split())
    list_=[[' ' for i in range(col)] for i in range(col)]#创建一个二维矩阵
    for j in range(col):
        for k in range(col):
            if j==k or (j+k)==col-1:
                list_[k][j]='X'
    for j in range(1,num+1):
        if j%2:
            for l in range(col):
                for t in range(col):
                    print(list_[l][t], end='')
                print()
        else:
            for l in range(1,col-1):
                for t in range(col):
                    print(list_[l][t],end='')
                print()
            if j==num:
                for l in range(1):
                    for t in range(col):
                        print(list_[l][t], end='')
                    print()
        print()

14

题目 1116: IP判断

时间限制: 1Sec 内存限制: 128MB 提交: 8310 解决: 3380

题目描述

在基于Internet的程序中，我们常常需要判断一个IP字符串的合法性。
合法的IP是这样的形式：
A.B.C.D
其中A、B、C、D均为位于[0, 255]中的整数。为了简单起见，我们规定这四个整数中不允许有前导零存在，如001这种情况。
现在，请你来完成这个判断程序吧^_^

输入

输入由多行组成，每行是一个字符串，输入由“End of file”结束。
字符串长度最大为30，且不含空格和不可见字符

输出

对于每一个输入，单独输出一行
如果该字符串是合法的IP，输出Y，否则，输出N

样例输入

1.2.3.4
a.b.c.d
267.43.64.12
12.34.56.bb
210.43.64.129
-123.4.5.6

样例输出

Y
N
N
N
Y
N

#这个题C做绝对没有python舒服

15

题目 1117: K-进制数

时间限制: 1Sec 内存限制: 128MB 提交: 3161 解决: 1247

题目描述

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.

给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.

假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.

输入

两个十进制整数N和K

输出

十进制表示的结果

样例输入

2
10

样例输出

90

# 写下思路：
#   （1）dp
#     这题是可以看成是一道dp题
#     首先首位必须是除了0以外的数
#     首位的可能性是确定为K-1:如果是十进制那么只有9个数在首位
#     然后后面的每一列可以取0 或非0
#     那么对于10进制dp表达式是：
#     dp[i]=10*dp[i-1](如果前面串是非0那么此处10种取法)+9*dp[i-2](如果前面是0，那么有9种取法)
#     dfs同理
n=int(input())
k=int(input())
re=0
def loop(c,m):
    global n,k,re#全局变量应用
    if c==1:#对于每个分支到尽头了
        if m==0:
            re+=k-1#这一分支最后有k-1种选择
        else:
            re+=k#这一分支最后有
    elif c==n:
        for i in range(1,k):#直接开启k-1个分支
            loop(c-1,i)
    else:
        if m==0:#如果前面是0,那么开启k-1分支
            for i in range(1,k):
                loop(c-1,i)
        else:#如果前面
            for i in range(0,k):#如果前面不是0,那么开启k分支
                loop(c-1,i)
loop(n,1)
print(re)

16

题目 1118: Tom数

时间限制: 1Sec 内存限制: 128MB 提交: 10594 解决: 4180

题目描述

正整数的各位数字之和被Tom称为Tom数。求输入数（<2^32）的Tom数!

输入

每行一个整数(<2^32).

输出

每行一个输出,对应该数的各位数之和.

样例输入

12345
56123
82

样例输出

15
17
10

x=input()
while x:
    print(sum([int(i) for i in x]))
    x=input()
   #python就是这么优雅

17

题目 1255: [蓝桥杯][算法提高]能量项链

时间限制: 1Sec 内存限制: 128MB 提交: 3366 解决: 1094

题目描述

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有 N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标 记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗 能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn（Mars单位），新产生的珠子的头标记为m， 尾标记为n。
需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号◎表示两颗珠子的聚合操作，(j◎k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：
(4◎1)=1023=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4◎1)◎2)◎3）=1023+1035+10510=710。

输入

第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行 是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i〈N时，第i颗珠子的尾标记应该等于第i+1颗 珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出

只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量

样例输入

4
2 3 5 10

样例输出

710

# 看了c++的题解，可以每次消掉最小的那一个进行排序
#自己写的
n = int(input())
l = list(map(int, input().split()))
l1 = l[:]
# 作为副本
l.sort()
sum = 0


def caculate(l):
    global sum
    if len(l) == 1:
        pass
    else:
        i = l.pop(0)  # 每次弹出最小的
        index_i = l1.index(i)
        index_i_=(index_i + len(l1) + 1) % len(l1)
        index_i__=(index_i + len(l1) - 1) % len(l1)
        sum += i * l1[index_i_] * l1[index_i__]
        l1.pop(index_i)
        caculate(l)
caculate(l)
print(sum)

看过的一种简洁的题解

num = int(input())
lst = list(map(int,input().strip().split()))
rst = 0
for i in range(num-1):
    a=lst.index(min(lst))
    rst+=lst[a]*lst[a-1]*lst[(a+1)%(num-i)]
    del lst[a]
print(rst)

18

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入

输入第一行包含九宫的初态，第二行包含九宫的终态。

输出

输出最少的步数，如果不存在方案，则输出-1。

样例输入

12345678. 
123.46758 

样例输出

3

这道题主要考察双向BFs

19

题目 1427: [蓝桥杯][2013年第四届真题]买不到的数目

时间限制: 1Sec 内存限制: 128MB 提交: 5850 解决: 2963

题目描述

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入

两个正整数，表示每种包装中糖的颗数(都不多于1000)

输出

一个正整数，表示最大不能买到的糖数

样例输入

4 7 

样例输出

17

L=[int(i) for i in input().split()]
re=(min(L)-1)*(max(L))-min(L)
if min(L)==1:
    print(0)
else:
    print(re)

自己写了下感觉 没有这个题解好

[蓝桥杯][2013年第四届真题]买不到的数目-题解(Python代码) 一个公式而已

20

题目 1429: [蓝桥杯][2014年第五届真题]兰顿蚂蚁

时间限制: 1Sec 内存限制: 128MB 提交: 3930 解决: 1772

题目描述

兰顿蚂蚁，是于1986年，由克里斯·兰顿提出来的，属于细胞自动机的一种。

平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。
蚂蚁的头部朝向为：上下左右其中一方。

蚂蚁的移动规则十分简单：
若蚂蚁在黑格，右转90度，将该格改为白格，并向前移一格；
若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。

规则虽然简单，蚂蚁的行为却十分复杂。刚刚开始时留下的路线都会有接近对称，像是会重复，但不论起始状态如何，蚂蚁经过漫长的混乱活动后，会开辟出一条规则的“高速公路”。

蚂蚁的路线是很难事先预测的。

你的任务是根据初始状态，用计算机模拟兰顿蚂蚁在第n步行走后所处的位置。

输入

输入数据的第一行是 m n 两个整数（3 < m, n < 100），表示正方形格子的行数和列数。
接下来是 m 行数据。
每行数据为 n 个被空格分开的数字。0 表示白格，1 表示黑格。

接下来是一行数据：x y s k, 其中x y为整数，表示蚂蚁所在行号和列号（行号从上到下增长，列号从左到右增长，都是从0开始编号）。s 是一个大写字母，表示蚂蚁头的朝向，我们约定：上下左右分别用：UDLR表示。k 表示蚂蚁走的步数。

输出

输出数据为一个空格分开的整数 p q, 分别表示蚂蚁在k步后，所处格子的行号和列号。

样例输入

5 6 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
2 3 L 5

样例输出

1 3

m,n=map(int,input().split())#m行数和n列数
Gra=[]
dir="URDL"#右手方向
xx=[0,-1,0,1]
yy=[-1,0,1,0]
for i in range(m):
    gra=list(map(int,input().split()))
    Gra.append(gra)
x,y,d,num=input().split()
x,y,num=map(lambda i:int(i),[x,y,num])
x,y=x-1,y-1
def move_ant(x,y,d,n):
    d=dir.index(d)
    for i in range(n):
        if(Gra[x][y]):#如果是黑色的格子
            d=((d+4)+1)%4
            x+=xx[d]
            y+=yy[d]
        else:
            d=d=((d+4)-1)%4
            x += xx[d]
            y += yy[d]
    return x,y
x,y=move_ant(x,y,d,num)
print(x,y)

21

题目 1432: [蓝桥杯][2013年第四届真题]剪格子

时间限制: 1Sec 内存限制: 128MB 提交: 3361 解决: 1161

题目描述

历届试题 剪格子
时间限制：1.0s 内存限制：256.0MB

问题描述
如下图所示，3 x 3 的格子中填写了一些整数。
+––+–+
|10 1|52|
+––+
|20|30* 1|
***–+
| 1| 2| 3|
+–+–+–+
我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。

输入

程序先读入两个整数 m n 用空格分割 (m,n< 10)。
表示表格的宽度和高度。
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

输出

输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。

样例输入

3 3
10 1 52
20 30 1
1 2 3

样例输出

3

def dfs(x,y,ant,cur):
    global sum_,count,vis,n,m
    xx = [0, 1, 0, -1]
    yy = [1, 0, -1, 0]
    if cur==sum_ and ant<count:
        count=ant#当达到结尾的时候
    else:
        #四个方向寻找
        for j in range(4):
            x+=xx[j]
            y+=yy[j]
            if(x>=0 and x<m and y>=0 and y<n and vis[x][y]):#注意取反
                #如果没有没出界而且没有访问
                vis[x][y]=False
                dfs(x,y,ant+1,cur+Gra[x][y])
                vis[x][y]=True
            else:
                continue

Gra=[]
sum_=0
count=1000
n,m=map(int,input().split())#m列n行
for i in range(n):
    list_=list(map(int,input().split()))
    sum_=sum_+sum(list_)
    Gra.append(list_)
vis=[[True for i in range(m)] for j in range(n)]
vis[0][0]=False
if sum_%2:#如果是基数那么结束
    print(0)
    exit()
else:
    sum_//=2
dfs(0,0,1,Gra[0][0])
if (count==1000):
    print(0)
else:
    print(count)

22

题目 1433: [蓝桥杯][2013年第四届真题]危险系数

时间限制: 1Sec 内存限制: 128MB 提交: 2897 解决: 1075

题目描述

问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。

输入

输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数，通道数；
接下来m行，每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道；
最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

输出

一个整数，如果询问的两点不连通则输出-1.

样例输入

7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6

样例输出

2

n,m=map(int,input().split())#n个点m个通道
Gra=[[False for i in range(n+1)]  for i in range(n+1)]
Vis=[True for i in range(n+1)]
path=[0 for i in range(n+1)]
for i in range(m):
    x,y=map(int,input().split())
    Gra[x][y]=True
    Gra[y][x]=True

start,end=map(int,input().split())

def dfs(s,e):
    global Gra,Vis,path
    if(s==e):
        for i in range(n):
            if not Vis[i]:
                path[i]+=1#注意在最后数数和访问就数数不一样
        return
    else:
        for i in range(1,n+1):
            if Gra[s][i] and Vis[i]:
                Vis[i]=False
                dfs(i,e)
                Vis[i]=True
dfs(start,end)
print(path.count(path[end])-1)#没有全对

23

题目 1434: [蓝桥杯][历届试题]回文数字

时间限制: 1Sec 内存限制: 128MB 提交: 10531 解决: 4347

题目描述

观察数字：12321，123321 都有一个共同的特征，无论从左到右读还是从右向左读，都是相同的。这样的数字叫做：回文数字。

本题要求你找到一些5位或6位的十进制数字。满足如下要求：
该数字的各个数位之和等于输入的整数。

输入

一个正整数 n (10< n< 100), 表示要求满足的数位和。

输出

若干行，每行包含一个满足要求的5位或6位整数。
数字按从小到大的顺序排列。
如果没有满足条件的，输出：-1

样例输入

44 

样例输出

99899
499994
589985
598895
679976
688886
697796
769967
778877
787787
796697
859958
868868
877778
886688
895598
949949
958859
967769
976679
985589
994499

count=0
goal=int(input())
flag=True
for i in range(100,1000):
    j=str(i)
    j=[int(i) for i in j]
    if(sum(j[:-1])*2+j[-1]==goal):
        j=str(i)
        print(j[:-1]+j[::-1])
        flag=False

for i in range(100,1000):
    j=str(i)
    j=[int(i) for i in j]
    if(sum(j)*2==goal):
        j=str(i)
        print(j+j[::-1])
        flag = False
if  flag:
    print(-1)

24

题目 1435: [蓝桥杯][历届试题]国王的烦恼

时间限制: 1Sec 内存限制: 128MB 提交: 1607 解决: 459

题目描述

C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。

如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。

现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

下文中的样例说明
第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后3和4之间的桥不能使用，居民们会抗议。
数据规模和约定
对于100%的数据，1< =n< =10000，1< =m< =100000，1< =a, b< =n， 1< =t< =100000。

输入

输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。

输出

输出一个整数，表示居民们会抗议的天数。

样例输入

4 4
1 2 2
1 3 2
2 3 1
3 4 3

样例输出

2

并查集

思路：天数从大到小排序，如果有一个桥生成，那么居民抗议一天

n,m=map(int,input().split())#n点个数m,桥个数
Gra=[]
fa=[0 for i in range(1000)]
for i in range(m):
    L=list(map(int ,input().split()))
    Gra.append(L)
def init():
    global fa
    for i in range(1,n+1):
        fa[i]=i

def find_(x):

    if( x==fa[x]):
        return x
    else:
        fa[x]=find_(fa[x])
        return fa[x]
def kruskal():
    global fa ,n
    init();#初始化并查集
    Gra.sort(key=lambda x:x[2])
    res=0;Time=-1
    for i in range(m):
        p1=find_(Gra[i][0])
        p2=find_(Gra[i][1])
        if (p1!=p2):#如果不是一个集合
            fa[p2]=p1#连上，表示同一集合
            if(Gra[i][2]!=Time):#开始断桥
                res+=1
                Time=Gra[i][2]
            n-=1
        if n ==1:
            break
    return res
print(kruskal()-1)

25

题目 1436: [蓝桥杯][2014年第五届真题]地宫取宝

时间限制: 1Sec 内存限制: 128MB 提交: 3733 解决: 1060

题目描述

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

输入

输入一行3个整数，用空格分开：n m k (1< =n,m< =50, 1< =k< =12)

接下来有 n 行数据，每行有 m 个整数 Ci (0< =Ci< =12)代表这个格子上的宝物的价值

输出

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

样例输入

2 3 2
1 2 3
2 1 5

样例输出

14

n,m,k=map(int,input().split())
# 记录迷宫的宝贝价值
table=[]
for _ in range(n):
    table.append(list(map(int,input().split())))
# 状态列表dp[1][2][3][4]=5 表示坐标（1,2)这个点物品数量为3最大价值为4的方案有5种
dp=[[[[-1]*15 for _ in range(15)] for _ in range(51)]for _ in range(51)]
#深度遍历
def dfs(x,y,sum,max):
    #因为如果这个方案先前采用了，就会有一个值而不是初始值-1
    if dp[x][y][sum][max+1]!=-1:
        #直接将记录过的状态返回
        return dp[x][y][sum][max+1]
    #方案数
    t=0
    #到达终点
    if x==n-1 and y==m-1:
        #最后一个格子能选
        if table[x][y]>max:
            #可选可不选，若选那么只能再选最后一个（先前有k-1个)
            if sum==k or sum==k-1:
                t+=1
        elif k==sum:
            #不能选也算一种方案
            t+=1
        dp[x][y][sum][max+1]=t
        #返回终点的方案数
        return dp[x][y][sum][max+1]
    #向下走
    if x+1<n:
        #可选
        if table[x][y]>max:
            t+=dfs(x+1,y,sum+1,table[x][y])
            t%=1000000007
        #不选
        t+=dfs(x+1,y,sum,max)
        t%=1000000007
        #向右走
    if y+1<m:
        #可选
        if table[x][y]>max:
            t+=dfs(x,y+1,sum+1,table[x][y])
            t%=1000000007
        #不选
        t+=dfs(x,y+1,sum,max)
        t%=1000000007
    dp[x][y][sum][max+1]=t
    return dp[x][y][sum][max+1]
dp[0][0][0][0]=dfs(0,0,0,-1)
print(dp[0][0][0][0])

26

目 1439: [蓝桥杯][历届试题]小朋友排队

时间限制: 1Sec 内存限制: 128MB 提交: 2447 解决: 434

题目描述

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

样例说明
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
数据规模和约定
对于100%的数据，1< =n< =100000，0< =Hi< =1000000。

输入

输入的第一行包含一个整数n，表示小朋友的个数。
第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。

输出

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3
3 2 1

样例输出

9

27

题目 1440: [蓝桥杯][2013年第四届真题]带分数

时间限制: 1Sec 内存限制: 128MB 提交: 1390 解决: 796

题目描述

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。

输入

从标准输入读入一个正整数N (N< 1000*1000)

输出

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！

样例输入

100  

样例输出

11

28

题目 1441: [蓝桥杯][2013年第四届真题]幸运数

时间限制: 1Sec 内存限制: 128MB 提交: 1479 解决: 642

题目描述

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成
。
首先从1开始写出自然数1,2,3,4,5,6,….
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 ….
把它们缩紧，重新记序，为：
1 3 5 7 9 …. 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …

输入

输入两个正整数m n, 用空格分开 (m < n < 1000*1000)

输出

程序输出 位于m和n之间的幸运数的个数（不包含m和n）。

样例输入

30 69  

样例输出

8

s=[int(i) for i in input().split()]
m=s[0]
n=s[1]
L=[i for i in range(n)]
def check(i):
    global L
    k=L[i]
    for j in range(len(L)-1,i-1,-1):
        if j%L[i]==0:
            L[j]=-1
    while -1 in L:
        L.remove(-1)
    for j in L:
        if j>k:
            if int((len(L)-1)/j)==0:
                break
            check(L.index(j))
            break
check(2)
re=0
for i in L:
    if m<i:
        re+=1
print(re)

29

题目 1442: [蓝桥杯][2013年第四届真题]打印十字图

时间限制: 1Sec 内存限制: 128MB 提交: 1056 解决: 739

题目描述

历届试题 打印十字图
时间限制：1.0s 内存限制：256.0MB

问题描述
小明为某机构设计了一个十字型的徽标（并非红十字会啊），如下所示：

..$$$$$$$$$$$$$..
..$...........$..
$$$.$$$$$$$$$.$$$
$...$.......$...$
$.$$$.$$$$$.$$$.$
$.$...$...$...$.$
$.$.$$$.$.$$$.$.$
$.$.$...$...$.$.$
$.$.$.$$$$$.$.$.$
$.$.$...$...$.$.$
$.$.$$$.$.$$$.$.$
$.$...$...$...$.$
$.$$$.$$$$$.$$$.$
$...$.......$...$
$$$.$$$$$$$$$.$$$
..$...........$..
..$$$$$$$$$$$$$..

对方同时也需要在电脑dos窗口中以字符的形式输出该标志，并能任意控制层数。

提示
请仔细观察样例，尤其要注意句点的数量和输出位置。

输入

一个正整数 n (n< 30) 表示要求打印图形的层数。

输出

对应包围层数的该标志。

样例输入

3  

30

题目 1443: [蓝桥杯][历届试题]数字游戏

时间限制: 1Sec 内存限制: 128MB 提交: 9976 解决: 1656

题目描述

栋栋正在和同学们玩一个数字游戏。

游戏的规则是这样的：栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来，坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来，也就是说4。下一个同学要往下数三个数，说7。依次类推。

为了使数字不至于太大，栋栋和同学们约定，当在心中数到 k-1 时，下一个数字从0开始数。例如，当k=13时，栋栋和同学们报出的前几个数依次为：
1, 2, 4, 7, 11, 3, 9, 3, 11, 7。

游戏进行了一会儿，栋栋想知道，到目前为止，他所有说出的数字的总和是多少。

样例说明
栋栋说出的数依次为1, 7, 9，和为17。
数据规模和约定
1 < n,k,T < 1,000,000；

输入

输入的第一行包含三个整数 n,k,T，其中 n 和 k 的意义如上面所述，T 表示到目前为止栋栋一共说出的数字个数。

输出

输出一行，包含一个整数，表示栋栋说出所有数的和。

样例输入

3 13 3

样例输出

17

#自己写的错误的
n,k,T=map(int,input().split())
L=[[] for i in range(n)]#存储数组的数组
count=0
i=0
sum_=1
while len(L[0])<T:
    L[i].append(sum_)
    count+=1
    sum_=(sum_+count)%k
    i=(i+1)%3
print(sum(L[0]))

#别人写的，找规律
n,k,T=map(int,input().split())
s=0
p=1
sum=0
for i in range(T):
    sum=sum+p
    s=s+n
    p=(p+s*n-(n-1)*n//2)%k
print(sum)

31

题目 1462: [蓝桥杯][基础练习VIP]Huffuman树

时间限制: 1Sec 内存限制: 128MB 提交: 2005 解决: 1326

题目描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：

\1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

\2. 重复步骤1，直到{pi}中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

\1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。

\2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。

\3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。

\4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。

\5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入

输入的第一行包含一个正整数n（n< =100）。

接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

输出

输出用这些数构造Huffman树的总费用。

样例输入

5 
5 3 8 2 9

样例输出

59

n=int(input())
L=list(map(int,input().split()))
sum=0
while len(L)!=1:
    a1=min(L)
    L.remove(a1)
    a2=min(L)
    sum+=(a1+a2)
    L[L.index(a2)]=a1+a2

print(sum)

32

题目 1463: [蓝桥杯][基础练习VIP]Sine之舞

时间限制: 1Sec 内存限制: 128MB 提交: 2261 解决: 1374

题目描述

最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
不妨设
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。

输入

仅有一个数：N<201。

输出

请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

3

样例输出

((sin(1)+3)sin(1-sin(2))+2)sin(1-sin(2+sin(3)))+1

n=int(input())

def an(n):
    for i in range(1,n+1):
        print('sin',end='')
        print('(',end='')
        print(i,end='')
        if i !=n:#注意这里
            if i%2:
                print('-',end='')
            else:
                print('+',end='')
    for i in range(n):
        print(')',end='')
    return ''

def sn(n):
    for i in range(n-1):
        print('(',end='')
    for i in range(1,n+1):
        print(an(i),end='')
        print('+',end='')
        print(n-i+1,end='')
        if i!=n:
            print(')',end='')



sn(n)

33

题目 1464: [蓝桥杯][基础练习VIP]分解质因数

时间限制: 1Sec 内存限制: 128MB 提交: 3039 解决: 1819

题目描述

求出区间[a,b]中所有整数的质因数分解。

提示

先筛出所有素数，然后再分解。

数据规模和约定

输入

输入两个整数a，b。

2< =a< =b< =10000

输出

每行输出一个数的分解，形如k=a1a2a3…(a1< =a2< =a3…，k也是从小到大的)(具体可看样例)

样例输入

3 10

样例输出

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

def fun2(i):
    l1=[]
    while True:
        for j in range(2,i+1):
            flag=True
            if i%j==0:
                l1.append(str(j))
                i=i//j
                break
        if i==1:
            break
    s='*'.join(l1)#注意这种用法
    return s

def fun(i):
    if i in l:
        return i
    else:
        return fun2(i)

n,m=map(int,input().split())
l=[]
for i in range(n ,m+1):
    flag=True
    for j in range(2,i):
        if i%j!=0:
            flag=False
            break
    if flag:
        l.append(i)
for i in range(n,m+1):
    print("{}={}".format(i,fun(i)))

注意join的使用

注意先排除之间的指数

注意数的变化

34

题目 1465: [蓝桥杯][基础练习VIP]回形取数

时间限制: 1Sec 内存限制: 128MB 提交: 2916 解决: 939

题目描述

回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。

输入

输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。

输出

输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。

样例输入

3 3
1 2 3
4 5 6
7 8 9

样例输出

1 4 7 8 9 6 3 2 5

#这时间超限了
n,m=map(int,input().split())
#m行，n列
L=[]
for i in range(m):
    l=list(map(int ,input().split()))
    L.append(l)
count=0
x=0
while count!=n*m:
    for i in range(x,m-x):
        if L[i][x]:
            print(L[i][x],end=' ')
            L[i][x]=0
            count+=1
        else:
            break
    for j in range(x+1,n-x):
        if L[m-x-1][j]:
            print(L[m-x-1][j],end=' ')
            L[m-x-1][j]=0
            count+=1
        else:
            break
    for k in range(m-x-2,x-1,-1):
        if L[k][n-x-1]:
            print(L[k][n-x-1],end=' ')
            L[k][n - x - 1]=0
            count+=1
        else:
            break
    for t in range(n-x-2,x,-1):
        if L[x][t]:
            print(L[x][t],end=' ')
            L[x][t]=0
            count+=1
        else:
            break
    x+=1

以下是完美的题解

m,n = map(int,input().split())
mapL = [list(map(int,input().split())) for _ in range(m)]
i,j = 0,0    #i表示行，j表示列
flag = "D"    #从向下走开始
result = []    #存结果
while True:
    if i<0 or j<0 or i>=m or j>=n or mapL[i][j] == -1:    #“i<0 or j<0 or i>=m or j>=n”这一段要加，不然一些单行，单列（n=1 or m=1）的用例通不过
        break
    result.append(mapL[i][j])
    mapL[i][j] = -1
    if flag == "D":
        i += 1
    elif flag == "R":
        j += 1
    elif flag == "U":
        i -= 1
    elif flag == "L":
        j -= 1
    if flag == "D" and (i>=m or mapL[i][j]==-1):
        flag = "R"
        i -= 1
        j += 1
    elif flag == "R" and (j>=n or mapL[i][j]==-1):
        flag = "U"
        j -= 1
        i -= 1
    elif flag == "U" and (i<0 or mapL[i][j] == -1):
        flag = "L"
        i += 1
        j -= 1
    elif flag == "L" and (j<0 or mapL[i][j] == -1):
        flag = "D"
        j += 1
        i += 1

for i in range(len(result)):
    if i == len(result) -1:
        print(result[i])
    else:
        print(result[i],end=" ")

35

题目 1466: [蓝桥杯][基础练习VIP]字符串对比

时间限制: 1Sec 内存限制: 512MB 提交: 5542 解决: 3212

题目描述

给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：

1：两个字符串长度不等。比如 Beijing 和 Hebei

2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing

3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing

4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing

编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。

输入

包括两行，每行都是一个字符串

输出

仅有一个数字，表明这两个字符串的关系编号

样例输入

BEIjing
beiJing

样例输出

3

s1=input()
s2=input()
if len(s1)!=len(s2):
    print(1)
elif s1!=s2:
    if s1.lower()==s2.lower():
        print(3)
    else:
        print(4)
elif s1==s2:
    print(2)

36

题目 1467: [蓝桥杯][基础练习VIP]完美的代价

时间限制: 1Sec 内存限制: 128MB 提交: 2465 解决: 748

题目描述

回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 md : madma

第三次交换 ma : madam (回文！完美！)

输入

第一行是一个整数N，表示接下来的字符串的长度(N < = 8000)

第二行是一个字符串，长度为N.只包含小写字母

输出

如果可能，输出最少的交换次数。

否则输出Impossible

样例输入

5 
mamad 

样例输出

3

n=int(input())
s=input()
L=len(s)
s=list(s)
alpha=[0 for i in range(26)]
#判断是否能成为回文
for i in range(5):
    alpha[ord(s[i])-ord('a')]+=1#转换ascii马
count=0
for i in alpha:
    if i%2:
        count+=1
if count>1:
    print("Impossible")
else:
    number=0
    for i in range(L//2):
        for j in range(L-(i+1),i,-1):
            if(s[i]==s[j]):
                for j2 in range (j,L-(i+1)):
                    character=s[j2]
                    s[j2]=s[j2+1]
                    s[j2+1]=character
                number+=L-(i+1)-j
            if(s[L-(i+1)]==s[L-(j+1)]):
                for j2 in range(L-(j+1),i,-1):
                    a=s[j2]
                    s[j2]=s[j2-1]
                    s[j2-1]=a
                number+=L-(j+1)-i
    print(number)
    #自己写的有问题的

37

题目 1468: [蓝桥杯][基础练习VIP]报时助手

时间限制: 1Sec 内存限制: 128MB 提交: 3230 解决: 1229

题目描述

给定当前的时间，请用英文的读法将它读出来。

时间用时h和分m表示，在英文的读法中，读一个时间的方法是：

如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“three o’clock”。

如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。

时和分的读法使用的是英文数字的读法，其中0~20读作：

0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。

30读作thirty，40读作forty，50读作fifty。

对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30再加1的读法，读作“thirty one”。

按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15读作“zero fifteen”。

输入

输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。

输出

输出时间时刻的英文。

样例输入

0 15 

样例输出

zero fifteen

38

题目 1471: [蓝桥杯][基础练习VIP]矩形面积交

时间限制: 1Sec 内存限制: 128MB 提交: 5912 解决: 1717

题目描述

平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。

输入

输入仅包含两行，每行描述一个矩形。

在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。

输出

输出仅包含一个实数，为交的面积，保留到小数后两位。

样例输入

1 1 3 3 
2 2 4 4 

样例输出

1.00

#38的错误答案
L1=list(map(float,input().split()))
L2=list(map(float,input().split()))
x1,y1=(L1[0]+L1[2])/2,(L1[1]+L1[3])/2
x2,y2=(L2[0]+L2[2])/2,(L2[1]+L2[3])/2
w1,h1=x1-L1[0],y1-L1[1]
w2,h2=x2-L2[0],y2-L2[1]
if w1+w2>abs(x1-x2) and h1+h2>abs(y1-y2):
    w=(w1+w2)-abs(x1-x2)
    h=(h1+h2)-abs(y1-y2)
    print("%.2f"%(w*h))
else:print(0)

xy1 = list(map(float,input().split()))
xy2 = list(map(float,input().split()))
rx = min(max(xy1[0],xy1[2]),max(xy2[0],xy2[2]))
lx = max(min(xy1[0],xy1[2]),min(xy2[0],xy2[2]))
uy = min(max(xy1[1],xy1[3]),max(xy2[1],xy2[3]))
dy = max(min(xy1[1],xy1[3]),min(xy2[1],xy2[3]))
w,h = rx-lx,uy-dy
if w<=0.0 or h<=0.00:
    print("0.00")
else:
    #print((str(w*h)+"00").split(".")[0]+"."+(str(w*h)+"00").split(".")[1][:2:])    不进位输出小数点后两位
    print("%.2f"%(w*h))

39

题目 1472: [蓝桥杯][基础练习VIP]矩阵乘法

时间限制: 1Sec 内存限制: 128MB 提交: 2655 解决: 791

题目描述

给定一个N阶矩阵A，输出A的M次幂（M是非负整数）

例如：

A =

1 2

3 4

A的2次幂

7 10

15 22

输入

第一行是一个正整数N、M（1< =N< =30, 0< =M< =5），表示矩阵A的阶数和要求的幂数

接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

输出

输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开

样例输入

2 2 
1 2 
3 4 

样例输出

7 10
15 22

#输入方阵的大小(n*n) 和幂m
n,m=map(int,input().split())
# 输入数据生成矩阵
matrix=[]
for _ in range(n):
    matrix.append(list(map(int,input().split())))
#矩阵matrix_a和矩阵matrix_b相乘得到matrix_result
def multi(matrix_a,matrix_b):
    #对于a*b和b*c的矩阵,得到的规模是a*c
    matrix_result=[[0 for _ in range(len(matrix_b[0]))] for _ in range(len(matrix_a))]
    for i in range(len(matrix_a)):
        for j in range(len(matrix_b[0])):
            #这里len(matrix_b)也可以换成len(matrix_a[0])
            for k in range(len(matrix_b)):
                matrix_result[i][j]+=matrix_a[i][k]*matrix_b[k][j]
    return matrix_result
# 求和matrix规模相同的单位矩阵E
def unit_1(n):
    #print('unit进来了')
    #初始化为0
    E=[[0 for _  in range(n)]for _ in range(n)]
    #对角线为1
    for i in range(n):
        E[i][i]=1
    #print(E)
    return E
#矩阵快速幂
def quick_multi(matrix,m):
    #print('quick进来')
    res=unit_1(len(matrix))
    while m:
        if m&1:
            res=multi(res,matrix)
        matrix=multi(matrix,matrix)
        m=m>>1
    #print('quick结束')
    return res
#输出
for r in quick_multi(matrix,m):
    print(' '.join([str(i) for i in r]))

抄的题解的出处

40

题目 1447: [蓝桥杯][2013年第四届真题]格子刷油漆

时间限制: 1Sec 内存限制: 128MB 提交: 684 解决: 174

题目描述

X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。

你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）
比如：a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。

输入

输入数据为一个正整数（不大于1000）

输出

输出数据为一个正整数。

样例输入

3 

样例输出

96

41

观察这个数列：
1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3。

栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？

样例说明
这两个数列分别是2 4 1 3和7 4 1 -2。

输入

输入的第一行包含四个整数 n s a b，含义如前面说述。

数据规模和约定
对于100%的数据，1< =n< =1000，-1,000,000,000< =s< =1,000,000,000，1< =a, b< =1,000,000。

输出

输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。

样例输入

4 10 2 3

样例输出

2

42

题目 1452: [蓝桥杯][历届试题]网络寻路

时间限制: 1Sec 内存限制: 128MB 提交: 610 解决: 248

题目描述

X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。

1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。

输入

输入数据的第一行为两个整数N M，分别表示节点个数和连接线路的条数(1< =N< =10000; 0< =M< =100000)。
接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v 联通(1< =u,v< =N , u!=v)。
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。

输出

输出一个整数，表示满足要求的路径条数。

样例输入

4 4
1 2
2 3
3 1
1 4

样例输出

10

43

题目 1450: [蓝桥杯][2014年第五届真题]矩阵翻硬币

时间限制: 1Sec 内存限制: 128MB 提交: 328 解决: 74

题目描述

小明先把硬币摆成了一个 n 行 m 列的矩阵。

随后，小明对每一个硬币分别进行一次 Q 操作。

对第x行第y列的硬币进行 Q 操作的定义：将所有第 ix 行，第 jy 列的硬币进行翻转。

其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。

当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。

小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。

聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。

输入

输入数据包含一行，两个正整数 n m，含义见题目描述。

数据规模和约定
对于100%的数据，n、m < = 10^1000（10的1000次方）。

输出

输出一个正整数，表示最开始有多少枚硬币是反面朝上的。

样例输入

2 3

样例输出

1

44

题目 1453: [蓝桥杯][历届试题]翻硬币

时间限制: 1Sec 内存限制: 128MB 提交: 2301 解决: 1242

题目描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：*oo**oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入

两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度< 1000

输出

一个整数，表示最小操作步数。

样例输入

*o**o***o*** 
*o***o**o*** 

样例输出

1

45

题目 1454: [蓝桥杯][历届试题]蚂蚁感冒

时间限制: 1Sec 内存限制: 128MB 提交: 3449 解决: 1539

题目描述

长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。

每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。

当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。

这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。

请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。

输入

第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。

接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数 据代表的蚂蚁感冒了。

输出

要求输出1个整数，表示最后感冒蚂蚁的数目。

样例输入

5
-10 8 -20 12 25

样例输出

3

46

题目 1456: [蓝桥杯][历届试题]连号区间数

时间限制: 1Sec 内存限制: 128MB 提交: 1001 解决: 515

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题：
在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入

第一行是一个正整数N (1 < = N < = 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 < = Pi < = N)， 表示这N个数字的某一全排列。

输出

输出一个整数，表示不同连号区间的数目。

样例输入

5
3 4 2 5 1

样例输出

9

46

题目 1457: [蓝桥杯][历届试题]邮局

时间限制: 1Sec 内存限制: 128MB 提交: 461 解决: 98

题目描述

C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。

现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。

输入

输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。

在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。

数据规模和约定
对于100%的数据，1< =n< =50，1< =m< =25，1< =k< =10。

输出

输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）

样例输入

5 4 2
0 0
2 0
3 1
3 3
1 1
0 1
1 0
2 1
3 2

样例输出

2 4

47

题目 1458: [蓝桥杯][2013年第四届真题]错误票据

时间限制: 1Sec 内存限制: 128MB 提交: 5332 解决: 1840

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。

输入

要求程序首先输入一个整数N(N< 100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。

输出

要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID

样例输入

2
5 6 8 11 9
10 12 9

样例输出

7 9

48

题目 1459: [蓝桥杯][2013年第四届真题]高僧斗法

时间限制: 1Sec 内存限制: 128MB 提交: 446 解决: 104

题目描述

古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。
节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。(如图1所示)
两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。
两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。
对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。

输入

输入数据为一行用空格分开的N个整数，表示小和尚的位置。台阶序号从1算起，所以最后一个小和尚的位置即是台阶的总数。（N< 100, 台阶总数< 1000）

输出

输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解，输出A值较小的解，若无解则输出-1。

样例输入

1 5 9

样例输出

1 4

49

题目 1460: [蓝桥杯][基础练习VIP]2n皇后问题

时间限制: 1Sec 内存限制: 128MB 提交: 1667 解决: 841

题目描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入

输入的第一行为一个整数n，表示棋盘的大小。 n小于等于8

接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出

输出一个整数，表示总共有多少种放法。

样例输入

4
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1 

样例输出

2

50

题目 1461: [蓝桥杯][基础练习VIP]FJ的字符串

时间限制: 1Sec 内存限制: 128MB 提交: 3710 解决: 2470

题目描述

FJ在沙盘上写了这样一些字符串：

A1 = “A”

A2 = “ABA”

A3 = “ABACABA”

A4 = “ABACABADABACABA”

… …

你能找出其中的规律并写所有的数列AN吗？

输入

仅有一个数：N ≤ 26。

输出

请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

样例输入

3 

样例输出

ABACABA

[基础练习VIP]:

51

最长滑雪道
问题描述
　　小袁非常喜欢滑雪， 因为滑雪很刺激。为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。 小袁想知道在某个区域中最长的一个滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。如下：
　　
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。
　　你的任务就是找到最长的一条滑坡，并且将滑坡的长度输出。 滑坡的长度定义为经过点的个数，例如滑坡24-17-16-1的长度是4。
输入格式
　　输入的第一行表示区域的行数R和列数C(1<=R, C<=10)。下面是R行，每行有C个整数，依次是每个点的高度h（0<= h <=10000）。
输出格式
　　只有一行，为一个整数，即最长区域的长度。
样例输入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
样例输出
25

def dfs(x, y):
    """
    深度递归搜索
    :param x: 横坐标
    :param y: 纵坐标
    :return: 最大距离
    """
    max_height = 1  # 初始距离为1
    if dp[x][y] > 0:  # 如果已经有了当前位置出发的最大距离，则直接返回
        return dp[x][y]
    for k in range(4):  # 判断该位置的上下左右四个位置
        tx = x + next_[k][0]
        ty = y + next_[k][1]
        if tx < 0 or tx >= row or ty < 0 or ty >= col:  # 越界情况
            continue
        if arr[tx][ty] >= arr[x][y]:  # 不符合高到低的情况
            continue
        max_height = max(max_height, dfs(tx, ty) + 1)  # 符合，递归搜索下一个位置且距离加1

    dp[x][y] = max_height  # 最终距离放在此矩阵中保存

    return dp[x][y]  # 返回该位置下的最大距离


row, col = map(int, input().split())

dp = [[0 for _ in range(col)] for _ in range(row)]  # 记录从每个位置(x, y)开始，它的最大长度

arr = [list(map(int, input().split())) for _ in range(row)]  # 这里发明了二位数组python输入方法的一种全新方式，偶然发现的

next_ = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 用来表示(x, y)的上下左右四个位置

ans = 0

for i in range(row):
    for j in range(col):
        ans = max(ans, dfs(i, j))

print(ans)

#自己写的失败的代码

def dfs(x,y):
    if DP[x][y]>0:
        return  DP[x][y]
    maxLength=1
    for i in range(4):
        tx=x+Direct[i][0]
        ty=y+Direct[i][1]
        if  tx>=R or tx<0 or ty>=C or ty<0:
            continue
        if G[ty][tx]>G[x][y]:
            continue
        else:
            maxLength=max(maxLength,dfs(tx,ty)+1)
    DP[x][y]=maxLength
    return  DP[x][y]


R,C=map(int,input().split())
G=[]
for i in range(R):
    L=list(map(int ,input().split()))
    G.append(L)
DP=[[0 for j in range(C)] for i in range(R)]
ans=0
Direct=[[0,1],[1,0],[-1,0],[0,-1]]
for i in range(R):
    for j in range(C):
        ans=max(ans,dfs(i,j))
print(ans)

52

龟兔赛跑

R,T=0,0
count=0
flag=0
while R<l and T<l:
    count+=1
    R+=v1
    T+=v2
    if R>=l:
        flag=1
        break
    if T>=l:
        flag=2
        break
    if R-T>=t:
        count1=count
        while count>=count1+s:
            count+=1
            T+=v1
            if T >=l:
                flag=3
                break
        if flag==3:
            break
if R>T:
    print("R")
    print(count)
if T>R:
    print("T")
    print(count)
if T==R:
    print("R T")
    print(count)