Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Зад. из районной олимп. по информ. 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) чисел? Если да, то:
ряд n1*n2*n3...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 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам