频道栏目
首页 > 程序开发 > Web开发 > Python > 正文
Python解决codeforces ---- 6
2013-10-15 11:25:19           
收藏   我要投稿

 

 第一题 16A

A. Flag

time limit per test 2 seconds

memory limit per test 64 megabytes

input standard input

output standard output

According to a new ISO standard, a flag of every country should have a chequered field n × m, each square should be of one of 10 colours, and the flag should be «striped»: each horizontal row of the flag should contain squares of the same colour, and the colours of adjacent horizontal rows should be different. Berland's government asked you to find out whether their flag meets the new ISO standard.

Input

The first line of the input contains numbers n and m (1 ≤ n, m ≤ 100), n — the amount of rows, m — the amount of columns on the flag of Berland. Then there follows the description of the flag: each of the following n lines contain m characters. Each character is a digit between 0 and 9, and stands for the colour of the corresponding square.

Output

Output YES, if the flag meets the new ISO standard, and NO otherwise.

Sample test(s)

input

3 3

000

111

222

output

YES

input

3 3

000

000

111

output

NO

input

3 3

000

111

002

output

NO

 

 

 题意:给定一个n*m的矩阵,现在要判断这个矩阵是否满足“同一行的所有元素相同,相邻行之间是不同的”

 思路:直接暴力枚举

 代码:

[python]  

# input  

n , m = map(int , raw_input().split())  

  

def getAns():  

    ans = "YES"  

    for i in range(n):  

        str = raw_input()  

        for j in range(1 , len(str)):  

            if str[0] != str[j]:  

               ans = "NO"  

        if i > 0 and pre == str:  

            ans = "NO"  

        pre = str  

    return ans  

  

print getAns()  

 

 

 

 第二题 17A

A. Noldbach problem

time limit per test 2 seconds

memory limit per test 64 megabytes

input standard input

output standard output

Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick's attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least k prime numbers from 2 to n inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5+ 7 + 1.

Two prime numbers are called neighboring if there are no other prime numbers between them.

You are to help Nick, and find out if he is right or wrong.

Input

The first line of the input contains two integers n (2 ≤ n ≤ 1000) and k (0 ≤ k ≤ 1000).

Output

Output YES if at least k prime numbers from 2 to n inclusively can be expressed as it was described above. Otherwise output NO.

Sample test(s)

input

27 2

output

YES

input

45 7

output

NO

Note

In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.

 

 

 题意:给定一个n和k,现在要判断2~n之间的数满足以下两个条件的个数是否大于等于k。1 数是质数 2 这个数 = 两个相邻的质数+1

 思路:先暴力求出1~1100之间的所有质数,然后暴力从3~n直接去求出符合的个数再和k比较

 代码:

[python]  

from math import sqrt  

# input  

n , k = map(int , raw_input().split())  

prime = []  

  

# judge is prime  

def isPrime(x):  

    for i in range(2,int(sqrt(x))+1):  

        if x%i == 0:  

           return False  

    return True  

  

# get 1~1000 prime number  

def getPrime():  

    for i in range(3,1100):  

        if isPrime(i):  

            prime.append(i)  

  

# isok  

def isOk(x):  

    if prime.count(x) != 0:  

       for j in range(prime.index(x)+1):  

           if x-1 == prime[j]+prime[j+1]:  

              return True;  

    return False  

  

# get ans  

def getAns():  

    cnt = 0  

    getPrime()  

    for i in range(3,n+1):   

        if isOk(i):  

           cnt += 1  

    if cnt >= k:  

       return "YES"  

    return "NO"  

  

print getAns()  

 

 第三题 18A

A. Triangle

time limit per test 2 seconds

memory limit per test 64 megabytes

input standard input

output standard output

At a geometry lesson Bob learnt that a triangle is called right-angled if it is nondegenerate and one of its angles is right. Bob decided to draw such a triangle immediately: on a sheet of paper he drew three points with integer coordinates, and joined them with segments of straight lines, then he showed the triangle to Peter. Peter said that Bob's triangle is not right-angled, but is almost right-angled: the triangle itself is not right-angled, but it is possible to move one of the points exactly by distance 1 so, that all the coordinates remain integer, and the triangle become right-angled. Bob asks you to help him and find out if Peter tricks him. By the given coordinates of the triangle you should find out if it is right-angled, almost right-angled, or neither of these.

Input

The first input line contains 6 space-separated integers x1, y1, x2, y2, x3, y3 — coordinates of the triangle's vertices. All the coordinates are integer and don't exceed 100 in absolute value. It's guaranteed that the triangle is nondegenerate, i.e. its total area is not zero.

Output

If the given triangle is right-angled, output RIGHT, if it is almost right-angled, output ALMOST, and if it is neither of these, outputNEITHER.

Sample test(s)

input

0 0 2 0 0 1

output

RIGHT

input

2 3 4 5 6 6

output

NEITHER

input

-1 0 2 0 0 1

output

ALMOST

 

 

 题意:给定三个点,如果这三个点能够组成直角三角形输出"RIGHT",如果不能组成直角三角形但是我们可以移动某一个点到和它距离为1的位置,如果新的三个点能够组成三角形输出"ALMOST",其它所有情况全部输出"NEITHER"

 思路:直接暴力枚举判断,但是要注意构成直角三角形的条件,已经构成三角形的条件

 代码:

[python]  

from math import sqrt  

# input  

input_list = map(int , raw_input().split())  

# getDis  

def getDis(point_list):  

    x1,y1,x2,y2,x3,y3 = point_list  

    list = []  

    list.append((x1-x2)**2+(y1-y2)**2)  

    list.append((x1-x3)**2+(y1-y3)**2)  

    list.append((x3-x2)**2+(y3-y2)**2)  

    list.sort()   

    return list  

  

def isOk(list , i):  

    list[i] -= 1  

    # 如果有相同的两个点,直接返回false  

    if (list[0] == list[2] and list[1] == list[3]) or (list[0] == list[4] and list[1] == list[5]) or (list[2] == list[4] and list[3] == list[5]):  

        list[i] += 1  

        return False;    

    # 如果三个点在同一条直线,直接返回false  

    if (list[0] == list[2] and list[2] == list[4]) or (list[1] == list[3] and list[3] == list[5]):  

        list[i] += 1  

        return False  

    a,b,c = getDis(list)  

    if (a+b == c):  

        return True  

      

    list[i] += 2  

    # 如果有相同的两个点,直接返回false  

    if (list[0] == list[2] and list[1] == list[3]) or (list[0] == list[4] and list[1] == list[5]) or (list[2] == list[4] and list[3] == list[5]):  

        list[i] -= 1  

        return False;    

    # 如果三个点在同一条直线,直接返回false  

    if (list[0] == list[2] and list[2] == list[4]) or (list[1] == list[3] and list[3] == list[5]):  

        list[i] -= 1  

        return False  

    a,b,c = getDis(list)  

    if (a+b == c):  

        return True  

      

    list[i] -= 1  

    return False  

# getAns  

def getAns():  

    a,b,c = getDis(input_list)  

    # judge  

    if (a+b == c):  

       return "RIGHT"  

    # else  

    for i in range(6):  

        if isOk(input_list , i):  

           return "ALMOST"  

    return "NEITHER"  

  

# output  

print getAns()  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:[Cocos2D]如何创建Cocos2D-X的项目(版本号2.2)
下一篇:HBASE shell 常用命令大全
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站