网站建设开发报价方案模板,网页设计制作实训总结,广告设计与制作专业学校,四川省城乡与建设厅网站首页✅作者简介#xff1a;人工智能专业本科在读#xff0c;喜欢计算机与编程#xff0c;写博客记录自己的学习历程。 #x1f34e;个人主页#xff1a;小嗷犬的个人主页 #x1f34a;个人网站#xff1a;小嗷犬的技术小站 #x1f96d;个人信条#xff1a;为天地立心人工智能专业本科在读喜欢计算机与编程写博客记录自己的学习历程。 个人主页小嗷犬的个人主页 个人网站小嗷犬的技术小站 个人信条为天地立心为生民立命为往圣继绝学为万世开太平。 本文目录TitleTime LimitMemory LimitProblem DescriptionInputOutputSample InputSample OnputNoteSourceSolutionTitle
CodeForces 1804 D. Accommodation
Time Limit
2 seconds
Memory Limit
512 megabytes
Problem Description
Annie is an amateur photographer. She likes to take pictures of giant residential buildings at night. She just took a picture of a huge rectangular building that can be seen as a table of n×mn \times mn×m windows. That means that the building has nnn floors and each floor has exactly mmm windows. Each window is either dark or bright, meaning there is light turned on in the room behind it.
Annies knows that each apartment in this building is either one-bedroom or two-bedroom. Each one-bedroom apartment has exactly one window representing it on the picture, and each two-bedroom apartment has exactly two consecutive windows on the same floor. Moreover, the value of mmm is guaranteed to be divisible by 444 and it is known that each floor has exactly m4\frac{m}{4}4m two-bedroom apartments and exactly m2\frac{m}{2}2m one-bedroom apartments. The actual layout of apartments is unknown and can be different for each floor.
Annie considers an apartment to be occupied if at least one of its windows is bright. She now wonders, what are the minimum and maximum possible number of occupied apartments if judged by the given picture?
Formally, for each of the floors, she comes up with some particular apartments layout with exactly m4\frac{m}{4}4m two-bedroom apartments (two consecutive windows) and m2\frac{m}{2}2m one-bedroom apartments (single window). She then counts the total number of apartments that have at least one bright window. What is the minimum and maximum possible number she can get?
Input
The first line of the input contains two positive integers nnn and mmm (1≤n⋅m≤5⋅1051 \leq n \cdot m \leq 5 \cdot 10^51≤n⋅m≤5⋅105) — the number of floors in the building and the number of windows per floor, respectively. It is guaranteed that mmm is divisible by 444.
Then follow nnn lines containing mmm characters each. The jjj-th character of the iii-th line is “0” if the jjj-th window on the iii-th floor is dark, and is “1” if this window is bright.
Output
Print two integers, the minimum possible number of occupied apartments and the maximum possible number of occupied apartments, assuming each floor can have an individual layout of m4\frac{m}{4}4m two-bedroom and m2\frac{m}{2}2m one-bedroom apartments.
Sample Input
5 4
0100
1100
0110
1010
1011Sample Onput
7 10Note
In the first example, each floor consists of one two-bedroom apartment and two one-bedroom apartments.
The following apartment layout achieves the minimum possible number of occupied apartments equal to 777.
|0 1|0|0|
|1 1|0|0|
|0|1 1|0|
|1|0 1|0|
|1|0|1 1|The following apartment layout achieves the maximum possible number of occupied apartments equal to 101010.
|0 1|0|0|
|1|1 0|0|
|0 1|1|0|
|1|0 1|0|
|1 0|1|1|Source
CodeForces 1804 D. Accommodation Solution
n, m map(int, input().split())
smin smax 0for i in range(n):s input()two j 0# 将连续两盏灯都先视为两居室while j m - 1:if s[j] 1 and s[j 1] 1:j 1two 1j 1two min(two, m // 4) # 两居室的数量不能超过总窗户数的四分之一smin s.count(1) - twotwo j 0# 统计可能的不开灯的两居室和只开一盏灯的两居室数量while j m - 1:if s[j] ! 1 or s[j 1] ! 1:j 1two 1j 1two min(two, m // 4) # 两居室的数量不能超过总窗户数的四分之一smax s.count(1) - (m // 4 - two) # (m // 4 - two) 为开两盏灯的两居室数量
print(smin, smax)
