Информатика

Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.

Входные данные
Первая строка входных данных содержит целое число N (3 <= N <= 10⁵ ) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 < |ai | <= 10⁴ ). Если ai > 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai < 0, то в i-м доме проживает |ai | избирателей, голосующих против кандидата от партии X.

Выходные данные
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести в одной строке три целых положительных числа N1, N2, N3, N1 + N2 + N3 = N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 -3 -5 3 -4 2 5 -3	4 1 2	На улице расположены 7 домов, избиратели в них распределены так: (−3, −5, 3, −4, 2, 5, −3). Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: (−3, −5, 3, −4). В этом округе за X голосует 3 избирателя, против — 12 избирателей и X разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за X, в этом округе X выиграет. В третьем округе два дома: (5, −3), и в этом округе X тоже выиграет. Итого X выигрывает в двух округах.

Незнайка и его друг Гунька играют в игру. Игра состоит из N ходов. На каждом ходу каждый игрок играет одним из двух жестов, Камень и Бумага, как в «Камень-ножницы-бумага», при следующих условиях:
- После каждого хода
(количество раз, когда игрок играл Бумагу) <= (количество раз, когда игрок играл Камень).
- Счет каждого игрока рассчитывается по формуле:
(количество ходов, на которых игрок выигрывает) - (количество ходов, на которых игрок проигрывает),
где результат каждого хода определяется по правилам «камень-ножницы-бумага».

Для тех, кто не знаком с игрой "Камень-нужница-бумага": если один игрок играет Камень, а другой играет Бумагу, последний игрок выиграет, а первый проиграет. Если оба игрока играют одним и тем же жестом, раунд считается ничейным, и ни один из игроков ни выиграет ни проиграет.

Используя волшебную палочку Незнайка смог предвидеть жест, который Гунька будет использовать в каждом из N ходов перед началом игры. Распланируйте жесты Незнайки на каждом шагу, чтобы максимизировать его счет.
Жест, который Гунька будет воспроизводить на каждом ходу, задается строкой s. Если i-й (1 <= i <= N) символ в s равен g, то Гунька будет играть "Камень" на i-м ходу. Аналогично, если i-й (1 <= i <= N) символ s в p, Гунька будет играть Бумага на i-м ходу.

Входные данные
На вход подается одна строка s длиной N. Каждый символ в строке s - это g или p. Жесты, представленные s, удовлетворяют условию игры.

Выходные данные
Выведите максимально возможный счет Незнайки.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	gpg	0	Выполнение одного и того же жеста с противником на каждом этапе дает 0 очков, что является максимально возможным результатом.
2	ggppgggpgg	2	Например, рассмотрите возможность воспроизведения жестов в следующем порядке: Камень, Бумага, Камень, Бумага, Камень, Камень, Бумага, Бумага, Камень, Бумага. Эта стратегия приносит три победы и одно поражение, в результате чего получается 2, что является максимально возможным результатом.

Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера.
На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a₁, a₂, . . . , a_N. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из a_i−1 и a_i+1 секунд (для удаления первого файла потребуется a₂ секунд, а для удаления последнего — a_N−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно.
У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы.
Сергей может удалять файлы последовательно в любом порядке.

Входные данные
В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 10⁵) — количество файлов на компьютере шпиона.
В каждой из следующих N строк записано по одному целому числу a_i (1 ≤ a_i ≤ 10⁴) — размер файла с номером i на компьютере Сергея.

Выходные данные
В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов.
 

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 100	4
2	1 1	0

Замечание
В первом примере у Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже:
1. Удалим последний файл. Это займет одну секунду.
2. Затем удалим файл размера 2 за одну секунду.
3. Далее удалим файл размера 3 за одну секунду.
4. Теперь удалим любой из оставшихся двух файлов за одну секунду.
5. Последний файл моментально удалится сам.
Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды.
Во втором примере у Сергея изначально есть всего один файл, который сразу же удалится.
 

Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон.
Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами 1, 10, 100 и 1 000 бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое.
Мальчик выбрал два целых числа x и y (x ≤ y) и заявил, что теперь в Берляндии будут использоваться только банкноты с номиналами x, x + 1, x + 2, . . . , y бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства начались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму.
Например, если Мишей были выбраны числа x = 5 и y = 7, то невозможно набрать суммы 1, 2, 3 и 4 бурлей. Также не получится набрать суммы 8 и 9 бурлей. Если же выбрать числа x = y = 2, то невозможно будет набрать любую нечетную сумму.
Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число N, что при помощи новых банкнот возможно набрать любую сумму, начиная с N. Таким образом, должно быть возможно набрать суммы N бурлей, N + 1 бурлей, N + 2 бурлей, и так далее. Помогите Мише найти искомое число N и избежать увольнения.

Входные данные
В первой строке входных данных записано целое число x — минимальный номинал новых банкнот.
Во второй строке записано целое число y (1 ≤ x ≤ y ≤ 2 · 10⁹ ) — максимальный номинал новых банкнот.

Выходные данные
Выведите одно натуральное число N — минимальное число, такое, что при помощи банкнот с номиналами x, x + 1, x + 2, . . . , y можно набрать любую сумму, начиная с N бурлей. Если такого числа не существует, в качестве ответа выведите −1.

 
Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 7	10	Имеются банкноты трех номиналов: 5, 6 и 7 бурлей. Ниже перечислены суммы, которые можно набрать при помощи данных банкнот: • 5 = 5, • 6 = 6, • 7 = 7, • 10 = 5 + 5, • 11 = 5 + 6, • 12 = 5 + 7, • 13 = 6 + 7, • . . . Можно показать, что при помощи банкнот данных номиналов возможно набрать любую сумму, начиная с 10 бурлей.
2	2 2	-1	Есть банкноты всего одного номинала: 2 бурля. При помощи данных банкнот можно набрать только любую чётную сумму: 2, 4, 6, .... Таким образом, искомого числа N не существует.
3	1900000000 2000000000	36100000000

Придя домой, уставший Константин захотел выпить свой любимый чай. Для этого ему нужно было достать с высокой полки самое красивое блюдце, которое представляет собой клетчатое поле N × N. Но, так как Константин не очень аккуратен, он блюдце разбил.
В спешке Костя начал думать, как же починить столь ценную вещь. И тогда он заметил, что блюдце распалось ровно на клетчатые квадраты K × K! Более того он обнаружил, что N делится на K без остатка.
Восстановив исходное блюдце из кусочков, Костя понял, что ему также нужно купить клей, чтобы склеить все соприкасающиеся кусочки в исходное клетчатое поле N × N. Он тут же посчитал, что, для того чтобы проклеить границу  между двумя соприкасающимися клетками длины 1, необходима ровно одна банка клея.
Помогите Косте посчитать, сколько банок клея ему нужно купить, чтобы склеить его любимое блюдце.

Входные данные
В первой строке входных данных записано одно целое число N (1 ≤ N ≤ 10⁴ ) — размер квадратного блюдца.
Во второй строке записано одно целое число K (1 ≤ K ≤ N, N делится на K без остатка) — размер квадратного осколка блюдца.

Выходные данные
В единственной строке выведите одно число — количество банок клея, которые Косте понадобится купить, чтобы починить блюдце.
Если на самом деле блюдце не разбилось, и Костя зря паниковал, выведите число 0.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 1	4	Различными цветами обозначены различные части блюдца, изначально имевшего размер 2 × 2. Между частями белым цветом обозначен клей, который Костя купил и намазал, чтобы починить блюдце. Каждая часть блюдца имеет размер 1 × 1.
2	3 3	0	Костя зря паниковал, и на самом деле он не разбил блюдце!

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите минимальный балл, набранный учащимися 11 класса школы 138 по предметам естественно-научного цикла.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите максимальный балл, набранный учащимися 11 класса школы 138 по предметам естественно-научного цикла.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите сколько учащихся 11 класса школ ЗАО выбрали тестирование по физике. 

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите количество учеников 10 класса школ ЦАО, набравших за тестирование по информатике более 90 баллов.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите ID учащегося, который набрал минимальный балл по информатике, среди всех учащихся 10 класса школ ЦАО..

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите минимальный балл по информатике, среди учащихся 10 класса школ ЦАО.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите ID учащегося, который набрал максимальный балл по информатике, среди всех учащихся 10 класса школ ЦАО.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите максимальный балл по информатике, среди учащихся 10 класса школ ЦАО.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите сколько учащихся 10 класса школ ЦАО выбрали тестирование по информатике.

Скачать файл

Проверьте, есть ли среди данных N чисел нули.

Входные данные

Вводится число N, а затем N чисел.

Выходные данные

Выведите YES, если среди введенных чисел есть хотя бы один нуль, или NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 4 19 14	NO

С клавиатуры вводится неотрицательное целое число N - количество чисел. Затем вводятся N чисел.
Напишите программу, которая подсчитывает количество нулей, положительных и отрицательных чисел среди введенных чисел.

Формат входных данных
В первой строке вводится натуральное число N - количество чисел, в седующих N строках записано по одному целому числу.

Формат выходных данных
Необходимо вывести три числа в одной строке, разделенных пробелом: сначала количество нулей, затем количество положительных и отрицательных чисел.

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите сколько различных предметов выбрали учащиеся 11 классов школы № 130 для тестирования.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите средний балл учащихся 10 класса школ ЮЗАО по математике.
В ответе укажите только целую часть среднего балла.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите количество учащихся 10 класса школ ЮЗАО, набравших по математике более 90 баллов.

Скачать файл

В файле приведён фрагмент базы данных "Тестирование учащихся", содержащий информацию о результатах всех попыток тестирования учеников 10-11 классов по различным предметам.
Таблица "Результаты тестирования" содержит записи о набранных баллах каждым учащимся в тестировании по выбранным предметам. Таблица "Школа" содержит информацию о школах и округах, в которых они находятся. Таблица "Предметы" содержит информацию о предметах и предметных циклах.

На рисунке приведена схема базы данных, содержащая все поля каждой таблицы и связи между ними. 
 

Используя информацию из приведённой базы данных, определите средний балл учащихся 11 класса школы № 121, набранный в результате тестирования по точным наукам.
В ответе укажите только целую часть среднего балла.

Скачать файл