Покраска забора Время: 1000ms, Память: 128MB, Сложность: 15% В одной далекой стране жил был Виталик-Гитарист, да к тому же и народный певец да на дуде игрец. Его мама постоянно заставляла делать дела по дому, и на этот раз она попросила его покрасить забор. Забор состоит из прямоугольных панелей одинаковой длины и единичной ширины.
Виталик знает, что мама решила сэкономить на краске и купила самую дешевую, методом экспериментов он смог определить что если нанести краску не менее чем A слоев и не более чем B слоев, забор будет выглядеть как раз нормально. Виталя был достаточно хитер и решил свалить всю работу на младшего брата, который согласился с этим делом.
Для простоты брат решил красить забор секциями, нанося на панели забора текущей секции краску в один слой. Завершив покраску секции он произвольно выбирал другую секцию (и не факт, что эта секция не совпадала полностью или частично с уже покрашенной частью забора) и приступал к ее покраске. Таким образом некоторые панели забора он мог покрасить несколько раз, в то время как другие - ни разу.
Пока брат красил забор Виталик ушел играть на гитаре и петь свои любимые песни, а когда вернулся, он был повергнут в шок! Местами забор был покрыт очень большим слоев краски, а местами и вовсе не покрашен.
К счастью его брат обладал хорошей памятью и помнил какие секции и в каком порядке он красил. Теперь Виталик должен понять сколько панелей забора он не должен переделывать. Чтобы дефекты покраски были менее заметно, брат обязательно покрасил первую и последнюю панели забора.
Входные данные:
Во входном потоке в первой строке записано натуральное число N (N <= 106) - количество закрашенных секций. Во второй строке - натуральные числа A и B (A, B <= 100) - допустимое количество слоев краски. Далее идет список координат N секций в порядке их окрашивания (номер первой Xi и последней Xj панели забора, составляющее текущую секцию). Значения номеров панелей (координат) не превышают 1000.
Пример входного файла (input.txt):
4
1 1
1 2
3 4
5 8
3 6
Выходные данные:
Вывести единственное число - количество панелей которые не придется перекрашивать Виталику-гитаристу.
Пример выходного файла (output.txt):
4
#include<stdio.h>
int main()
{
int n=3,m=3,a[50][50],i,j,k,g;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&a[i][j]);
for(j=0;j<m;++j)
{
g=0;
for(i=0;i<n;++i)
if(a[i][j]>0) ++g;
if(g==n)
{
for(k=j;k<m-1;++k)
for(i=0;i<n;++i)
a[i][k]=a[i][k+1];
m--;
break;
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
printf("%2d",a[i][j]);
printf("\n");
}
return 0;
}
Объяснение:
(см. объяснение)
Объяснение:
Решение на Java:
import java.math.BigInteger;
public class Main
{
public static void main(String[] args) {
System.out.println(BigInteger.valueOf(2).multiply(BigInteger.valueOf(27).pow(7)).add(BigInteger.valueOf(3).pow(10)).subtract(BigInteger.valueOf(9)).toString(3).chars().filter(x->x=='0').count());
}
}
Решение на Python 3:
a = 2*27**7+3**10-9
s = ''
while a>0:
s = str(a % 3) + s
a //= 3
print(s.count('0'))
Результат работы программ в обоих случаях одинаковый и равен 13.
Задание выполнено!