Паскаль Задача 3. Ремонт забора Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в
замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать
продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ...,
в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых
L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.
Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор.
Формат входных данных
Первая строка входных данных содержит целое число L (L > 0) — максимальный размер щита.
Во второй строке входных данных записано целое число N (N > 0) — количество досок в заборе.
Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 — что доска может быть сохранена.
Формат выходных данных
Программа должна вывести одно целое число — минимальное число щитов, которое необходимо
приобрести для ремонта всего забора.
Система оценивания
Решение, правильно работающее только для случаев, когда числа L и N не превосходят 1000,
будет оцениваться в
В будет оцениваться решение, правильно работающее, когда числа L и N не превосходят 105
.
Пример
стандартный ввод стандартный вывод
3
8
0
0
1
0
1
0
1
0
3
Пояснение к примеру
Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски
с номерами 3, 5 и 7. Для этого достаточно двух щитов, например, одним щитом меняем доски с
номерами 3, 4, 5, а другим щитом меняем доску с номером 7
#include <iostream>
using namespace std;
int main() {
int h, m, s, time;
cin >> h >> m >> s >> time;
int hour, minute, second;
second = time % 60;
time -= second;
time = time/60;
minute = time % 60 ;
hour = time / 60;
if ( s + second > 60 ) {
s = (s+second) % 60;
if ( m + minute + 1 > 60 ) {
m = (m+minute+1) % 60;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h+=hour+1;
}
} else if( m + minute + 1 == 60 ) {
m = 0;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h+=hour+1;
}
} else {
m = m+minute;
if ( h + hour >= 24 ) {
h = (h+hour) % 24;
} else {
h += hour;
}
}
} else if ( s+second == 60 ) {
s = (s+second) % 60;
if ( m + minute + 1 > 60 ) {
m = (m+minute+1) % 60;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h+=hour+1;
}
} else if( m + minute + 1 == 60 ) {
m = 0;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h +=hour+1;
}
} else {
m += minute;
if ( h + hour >= 24 ) {
h = (h+hour) % 24;
} else {
h = h + hour;
}
}
} else {
s = s+second;
if ( m + minute > 60 ) {
m = (m+minute) % 60;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h+=hour+1;
}
} else if( m + minute == 60 ) {
m = 0;
if ( h + hour + 1 >= 24 ) {
h = (h+hour+1) % 24;
} else {
h += hour+1;
}
} else {
m += minute;
if ( h + hour >= 24 ) {
h = (h+hour) % 24;
} else {
h += hour;
}
}
}
cout << h << ":" << m << ":" << s;
}
Витя - Москва
Боря - Омск
Гриша - Санкт-Петербург
Егор - Киров.
Объяснение:
Известно что Боря жил в одной комнате с мальчиком из Кирова и ни один из этих мальчиков не был в Москве, ни в Санкт-Петербурге, то есть Боря был не из Москвы, не из Питера и не из Кирова, остаётся-Омск.
Гриша играл в одной команде с мальчиком из Москвы, а вечерами к ним заходил мальчик из Кирова, значит, точно знаем, что Гриша был не из Москвы, не из Кирова, остаются Питер и Омск, но мы уже установили, что из Омска был-Боря, получается, что Гриша был из Питера.
Егор и мальчик из Москвы увлекались игрой в шахматы, значит, Егор был точно не из Москвы, и при этом мы знаем, что Омск и Питер уже заняты. Остался Киров У нас остался один город Москва и один мальчик, которого зовут Витя, значит, Витя был из Москвы.