Задачи по программированию. Практикум

[Troll]

Есть предложение немного попрактиковаться! Смотрю ветка практически помирает, так что попытаемся немного её реанимировать
Реализовывать можно на любом языке программирования, выкладываем исходники, будем оценивать и присуждать титулы вроде ламер-неудачник .

Итак, задача № 1. (задачи придуманы не мной, так что ногами не бейте)

N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.

[slonik]

Сообщение от Troll

Есть предложение немного попрактиковаться! Смотрю ветка практически помирает, так что попытаемся немного её реанимировать
Реализовывать можно на любом языке программирования, выкладываем исходники, будем оценивать и присуждать титулы вроде ламер-неудачник .

Итак, задача № 1. (задачи придуманы не мной, так что ногами не бейте)

N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.

-------------------------------
Хм, вроде кто-то задачу неправильно скопипейстил... любых двух съеденных мышей(или любых двух не съеденных) можно поменять местами - порядок изменится, а цифры - нет. Поэтому определить порядок получится только в экзотических случаях (например M == 0, или (K==0)&&(M==L)).

[Pitty]

Сообщение от slonik

-------------------------------
Хм, вроде кто-то задачу неправильно скопипейстил... любых двух съеденных мышей(или любых двух не съеденных) можно поменять местами - порядок изменится, а цифры - нет. Поэтому определить порядок получится только в экзотических случаях (например M == 0, или (K==0)&&(M==L)).

Ну, что? Я поломал голову, поломал и она сломлась. Ждемс комменатрии...Ответ хотя бы.

[бобс]

Задача 1. «Алгоритм Евклида» (100 баллов)

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.
Алгоритм Евклида заключается в следующем:
1.Пусть a, b — числа, НОД которых надо найти.
2.Если b = 0,то число a — искомый НОД.
3.Если b > a, то необходимо поменять местами числа a и b.
4.Присвоить числу a значение a – b.
5.Вернуться к шагу 2.
Дима достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.
Требуется написать программу, которая решает эту задачу.
Формат входных данных
Первая строка входного файла содержит количество наборов входных данных k (1 ___8804; k ___8804; 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ___8804; a, b ___8804; 1018). Вторая строка – два целых числа: c, d (1 ___8804; c, d ___8804; 1018).
Все числа в строках разделены пробелом.
Формат выходных данных
Для каждого набора входных данных выведите в отдельной строке выходного файла слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d), или слово «NO» – в противном случае.



Задача 2. «Преобразование последовательности» (100 баллов)

Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.
Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.
Требуется написать программу, которая решает названную задачу.
Формат входных данных
Первая строка входного файла содержит число n — количество чисел во входной последовательности (3 ___8804; n ___8804; 200000). Следующая строка содержит входную последовательность, состоящую изn целых чисел, не превышающих по модулю 109. Все числа в строке разделены пробелом.
Формат выходных данных
В выходной файл выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.

[бобс]

Задача 1. Двойной листок (30 баллов)

Ученик подготовил N листов одного размера (рис.1), сложил их пополам (рис. 2) и в получившейся тетрадке пронумеровал страницы по порядку: 1, 2, 3, 4…(рис.3)

Листки рассыпались. На одном из них ученик увидел подписанный номер страницы K. По заданным N и K определите все остальные номера страниц, которые тоже находятся на этом же листке.



Задание 2. О костях домино (100 баллов)

У игрока имеется набор костей домино (не обязательно полный). На каждой косточке написаны два числа от 0 до 6 (например, 4-0 или 6-6), которые могут быть переставлены при прочтении (4-6 и 6-4 –одна и та же кость). Игра начинается с выкладывания одной косточки. Следующие косточки могут быть вплотную «пристыкованы» к ней справа или слева так, чтобы соседние числа разных косточек совпали, например, к 5-5 можно «пристыковать» 4-5 и 5-6, получится 4-5 5-5 5-6. Найдите последовательность выкладывания костей данного набора таким образом, чтобы получившаяся в результате цепочка была максимально возможной длины.




Задание 3. Самопорожденные числа (100 баллов)

В 1949 году Индийский математик Д. Р. Капрекар открыл класс чисел, называемых самопорожденными. Для любого положительного целого N можно определить функцию d(N) значением которой будет N плюс сумма цифр N.
Например, d(75) = 75 + 7 + 5 = 87. Взяв любое положительное целое N как начальное значение, можно построить бесконечно возрастающую последовательность чисел: N, d(N), d(d(N)), d(d(d(N))), .... Например, если вы начинаете с 33, то следующим числом будет 33 + 3 + 3 = 39, следующее - 39 + 3 + 9 = 51, следующее - 51 + 5 + 1 = 57, таким образом, получается последовательность 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, ...
Число N называется генератором d(N). В приведенной выше последовательности, 33 является генератором 39, 39 - генератор 51, 51 - генератор 57, и так далее. Некоторые числа могут иметь более одного генератора. Например, 101 имеет два генератора: 91 и 100. Число, не имеющее генераторов, называется самопорожденным.
Пусть ai является самопорожденным числом с номером i. Существует 13 самопорожденных чисел (a1..a13), меньших 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, и 97. (первое самопорожденное число a1=1, второе - a2 = 3, …, тринадцатое - a13=97).
Входные данные

Ввод содержит целые числа Х, K, s1...sk. (1<=Х<=107, 1<=K<=5000), разделенные пробелами и символами перевода строки.
Выходные данные

В первой строке должно содержаться одно число – количество самопорожденных чисел в интервале [1..Х]. Вторая строка должна содержать K чисел - разделенных пробелами. Гарантируется, что все самопорожденные числа входят в интервал [1..Х] (например, если Х = 100, sk может быть от 1 до 13 и не может быть 14, т.к. 14-е самопорожденное число a14 = 108, 108 > 100).


Задание 4. Язык BHTML (100 баллов)

Язык разметки гипертекста BHTMLсодержит всего два парных тега: <UP></UP> и <DOWN></DOWN>. Тег <UP></UP> преобразует все буквы внутри его тела (между открывающим и закрывающим тегом) к верхнему регистру. Тег <DOWN></DOWN> преобразует все буквы внутри его тела нижнему регистру.
Дан текст, состоящий из латинских букв и тегов. Напишите программу, которая преобразует входной текст на языке BHTML в обычный текст, который будет показан пользователю браузера.
Известно, что теги в тексте расположены корректно, т.е. они образуют правильную последовательность вложений. Если буква расположена внутри нескольких тегов, то ее регистр определяется последним открывающим тегом, стоящим перед ней.
Входные данные

Входной файл содержит строку текста на языке BHTML. Длина строки не превышает 1000 символов. Теги всегда записаны в верхнем регистре.
Выходные данные

Выходной файл должен содержать текст после обработки, т.е. в том виде, в каком он будет представленпользователю.

Пример входных данных Thi<UP>sIs<DOWN>EaSY</DOWN>Pr<UP>O</UP>ble</UP>m

Пример выходных данных
ThiSISeasyPROBLEm

[бобс]

ну и тесты ко всем задачам

[TEHb]

Сообщение от Troll

Итак, задача № 1. (задачи придуманы не мной, так что ногами не бейте)

N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.

мышЪ не будет сидеть и ждать пока её съедят!