VBNet - Форум - Зад. из районной олимп. по информ. 2009 (10е кл.)

Вопрос: Зад. из районной олимп. по информ. 2009 (10е кл.) Добавлено: 16.11.09 02:06

Автор вопроса:

Давненько я забросил своё VB, а тут вот пришлось вспоминать функции, синтаксис его и как меняется раскладка на компьютерах без Punto Switcher'а на олимпиадке. Так вот, рапортую. Выбор языков не удивил: Ни Java вам, ни C# - или VB (v.5, прослезился), или Turbo Pascal (прослезился++). Дано 6 банальноватых задач, решение которых, в основном, состоит в умении составлять циклы. Теперь, когда, видимо благодаря и вашим данным мне в своё время конструктивным ответам на мои малоразумные вопросы, занято первое место совместно с другим парнем, можно говорить, что не оказался удивлён ничем, кроме последней, наиболее лакомой по баллам, задачи. Возьму на себя труд привести подробнейший текст задачи F "Тест профессора".
(именно буква 'ф' а не 'ц' в последнем слове)

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 секунды
Максимальный объём используемой памяти: 64 мегабайта

Для того чтобы проверить, как его студенты умеют считать, профессор каждый год задаёт им на дом одну и ту же задачу - для заданного натурального числа a найти минимальное натуральное число n такое, что n в квадрате делится на a. От года к году и от студенту к студенту меняется только число a.
Требуется помочь будущим поколениям и составить программу, решающую задачу профессора.
Формат входных данных
Входной файл input.txt содержит единственное целое число a (1 <= a <= 10^9).
Формат выходных данных
Выходной файл output.txt должен содержать единственное число n.
Пример входного и выходного файлов
input.txt output.txt
8 4
13 13
16 4

Ну, ессно, первое, что пришло в голову:

Private Sub Form_Load()
fileNum = FreeFile()
Open App.Path + "\input.txt" For Input As fileNum
Input #fileNum, a
Close fileNum

n = 1
a = Val(a)
While Not n * n Mod a = 0
n = n + 1
Wend

Open App.Path + "\output.txt" For Output As fileNum
Print #fileNum, n
Close fileNum

End
End Sub

Во-первых, зная некоторую часть посетителей сайта, надеюсь, что кому-то кажется, что я листаю книгу по одному листу с самого начала в поисках нужной главы, вместо того чтобы воспользоваться содержанием. А во-вторых, обратите внимание на это: 1 <= a <= 10^9. Разумеется, при a = 10^9 произойдёт Overflow. Даже на Currency при n=46341, как я смотрел уже дома.

Надеюсь, будет сказано что-то интересное.
Ответить

Ответы Всего ответов: 11

Номер ответа: 1 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #1	Добавлено: 16.11.09 03:55
	Это ужасно. Решение задачи: факторизовать a и заменить каждую степень простых множителей в разложении на roundup(power / 2). Переполнения нигде не возникнет. Ответить

Номер ответа: 2 Автор ответа: Вопросов: 5 Ответов: 79	Профиль \| \| #2	Добавлено: 16.11.09 16:43
	может тока изза переполнения, но вобще уже факторизация - нетривиальная, не такая быстрая штука Ответить

Номер ответа: 3 Автор ответа: Abiron Вопросов: 30 Ответов: 62	Профиль \| \| #3	Добавлено: 16.11.09 17:29
	А есть шустрая функция получения простых(делится на себя и на 1) чисел? Если да, то: ряд n1n2n3...nx простых чисел-число номер х в ряду квадратов. Перебираем все числа n1 сначала, до n1*n2...nx пока не поделится на a. Искать простые числа все же проще, чем перебирать все. Ответить

Номер ответа: 4 Автор ответа: Abiron Вопросов: 30 Ответов: 62	Профиль \| \| #4	Добавлено: 16.11.09 17:33
	стоп, чета я напутал. Щас поправлю. Ответить

Номер ответа: 5 Автор ответа: Вопросов: 5 Ответов: 79	Профиль \| \| #5	Добавлено: 16.11.09 19:37
	шарп, в самом деле интригуешь. расскажи получше насчет power (?) и roundup (??) пошарился за факторизацией уже в вики. хотел бы накодить и этот пауэр и раундап хотябы чтоб не было переполнения для интереса и общего развития Ответить

Номер ответа: 6 Автор ответа: shuffle Администратор ICQ: 201502381 Вопросов: 15 Ответов: 737	Профиль \| \| #6	Добавлено: 16.11.09 22:38
	факторизация - нетривиальная, не такая быстрая штука Тривиальная факторизация в худшем случае работает за O(n^(1/2)), что существенно лучше решения топикстартера, которое вообще линейное. power (?) и roundup (??) Показатель степени и округление наверх. Ответить

Номер ответа: 7 Автор ответа: UnDeAdZak Вопросов: 80 Ответов: 476	Профиль \| \| #7	Добавлено: 17.11.09 03:32
	хмммм... я решил эту задачу без фактОриалов, и само решение(без считывания\записи а\н) у меня заняло 12 строчек. Точно привести щас не могу т.к. сижу с телефона, но алгоритм такой:сначало определаю четное а или нет(if int(a/2)=a...) после в нечетном а всегда равно н(т.к. минимальный квадрат нечетного числа, на который оно делицца без остатка оно само в квадрате) а четное я перебирал в цыкле от 2-х до а с шагом 2 и условие если int(i^2/a)=i^2/a то i=n(i-аргумент цикла) Ответить

Номер ответа: 8 Автор ответа: shuffle Администратор ICQ: 201502381 Вопросов: 15 Ответов: 737	Профиль \| \| #8	Добавлено: 17.11.09 10:53
	после в нечетном а всегда равно н(т.к. минимальный квадрат нечетного числа, на который оно делицца без остатка оно само в квадрате) a = 9 => n = 3. Ответить

Номер ответа: 9 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #9	Добавлено: 17.11.09 14:52
	Факторизация почти ничего общего не имеет с факториалами. Ответить

Номер ответа: 10 Автор ответа: UnDeAdZak Вопросов: 80 Ответов: 476	Профиль \| \| #10	Добавлено: 17.11.09 20:30
	ну значит на 2 строчки больше! Ответить

Номер ответа: 11 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979	Web-сайт: sharpc.livejournal.com Профиль \| \| #11	Добавлено: 18.11.09 06:33
	Твое решение вообще неправильное. Ответить

Страница: 1 |