Организаторы детского праздника планируют надуть для него \(M\) воздушных шариков. С этой целью они пригласили \(N\) добровольных помощников, \(i\)-й среди которых надувает шарик за \(T_i\) минут, однако каждый раз после надувания \(Z_i\) шариков устает и отдыхает \(Y_i\) минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).
В первой строке входных данных задаются числа \(M\) и \(N\) (0 <= \(M\) <= 15000, 1 <= \(N\) <= 1000). Следующие \(N\) строк содержат по три целых числа - \(T_i\), \(Z_i\) и \(Y_i\) соответственно (1 <= \(T_i\), \(Y_i\) <= 100, 1 <= \(Z_i\) <= 1000).
Выведите в первой строке число \(T\) - время, за которое будут надуты все шарики. Во второй строке выведите \(N\) чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
2 2 1 1 1 1 1 1
1 1 1
3 2 2 2 5 1 1 10
4 2 1
Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника
M×N метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во первых, каждый новый клиент очевидно захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных
клиентов этой фирмы, а во вторых, этот узор должен быть симпатичным.
Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!
В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: \(M\) и \(N\) (1 <= \(M\)·\(N\) <= 30).
Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера \(M\)×\(N\) . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.
1 2
4
4 1
16
Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.
Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать - ведь разные буквы могут находиться на одном и том же кубике и тогда Петя не сможет использовать обе буквы в слове. Правда одна и та же буква может встречаться на разных кубиках. Помогите Пете!
Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.
В первой строке вводится число \(N\) (1 <= \(N\) <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.
В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.
В случае положительного ответа, во второй строке выведите \(M\) различных чисел из диапазона 1…\(N\), где \(M\) - количество букв в имени Петиной сестры. \(i\)-е число должно быть номером кубика, который следует положить на \(i\)-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.
2 AB AAAAAB AAAAAA
YES 2 1
3 ANNY AAAAAA NNNNNN YYYYYY
NO
Недавно Петя научился считать. Он тут же заметил, что число 2 обладает замечательным свойством - 2 + 2 = 2 × 2. Его старший брат Ваня тут же объяснил ему, что дело не в двойке.
"Дело в том, что последовательность 2, 2 - волшебная," - сказал Пете Ваня. - "Волшебная последовательность - это такая последовательность натуральных чисел, что сумма ее членов равна их произведению. Например последовательность 1, 2, 3 - тоже волшебная."
Петя тут же сложил 1, 2 и 3, потом перемножил их и обрадовался.
Теперь Петя хочет найти более длинные волшебные последовательности. Помогите ему!
В первой строке входных данных содержится целое число \(N\) (2 <= \(N\) <= 100).
Выведите любую волшебную последовательность длины \(N\). Разделяйте числа пробелами. Члены последовательности не должны превышать \(10^9\). Если такой волшебной последовательности длины \(N\) не существует, выведите единственное число - "-1".
2
2 2
3
1 2 3
Рассмотрим таблицу, состоящую из \(N\) строк и \(M\) столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу \(p\), если все числа в ее ячейках кратны \(p\).
Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел \(i\)-й строки за \(H_i\), а сумму чисел \(j\)-го столбца за \(V_j\). Упорядоченный набор чисел (\(H_1\), \(H_2\), …, \(H_N\), \(V_1\), \(V_2\), …, \(V_M\)) назовем профилем матрицы. Скажем, что матрица почти кратна \(p\), если все числа, входящие в ее профиль, кратны \(p\). Почти кратная 5 матрица и ее профиль изображены на рисунке 1.
1. отличается от не более чем на \(p\)
2. профили \(B\) и \(A\) совпадают.
Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.
В первой строке входных данных задаются целые числа \(p\) (1 <= \(p\) <= 10), \(N\) и \(M\) (1 <= \(N\), \(M\) <= 30). Следующие \(N\) строк содержат по \(M\) целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы \(A\).
Выведите матрицу \(B\) по строкам - сначала \(M\) элементов первой строки, затем \(M\) элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.
3 3 3 1 2 3 2 3 1 3 1 2
3 0 3 0 3 3 3 3 0