![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
1 | |
Квадратная страна08.01.2010, 15:57. Показов 5202. Ответов 10
Метки нет Все метки)
(
http://acm.timus.ru/problem.as... &locale=ru
В одном квадратном государстве жили квадратные люди. И всё остальное в этом государстве было тоже квадратное. Так, Квадратная Дума приняла Квадратный Закон о земле. Согласно этому закону, любой житель государства имел право приобрести землю. Земля продавалась, естественно, квадратными участками. Длина стороны каждого участка выражалась натуральным числом метров. Приобретая участок земли со стороной a метров, покупатель платил a2 квадриков (местная валюта) и получал одно квадратное свидетельство о праве собственности на этот участок. Один житель этого государства решил вложить все свои N квадриков без остатка в покупку земли. Это безусловно можно было сделать, приобретя участки размером 1 × 1 метр. Но этот житель потребовал от агентства недвижимости минимизации количества покупаемых участков. «Так мне будет легче общаться с Квадратной Налоговой Инспекцией», — сказал он. Сделка состоялась. Найдите, какое количество квадратных свидетельств он получил. Исходные данные В единственной строке стоит положительное число N ≤ 60 000 — число квадриков, которое было у жителя. Результат В единственной строке стоит число свидетельств, полученных в результате сделки. Пример: INPUT 344 OUTPUT 3
0
|
|
08.01.2010, 15:57 | |
Ответы с готовыми решениями:
10
создание структуру СТРАНА. добавление и удаление элементов из структуры
C++ задача. C 2009 года наша страна празднует день программиста 13 сентября нужно чтоб нашлась страна и все данные об этой стране вывелись в таблицу... |
outoftime
|
08.01.2010, 16:06
#2
|
Не по теме: сейчас камп будет занят, я пока поразмышляю над задачей, напишу потом
0
|
UNIX-way
712 / 495 / 49
Регистрация: 15.01.2009
Сообщений: 1,720
|
|||||||||||
08.01.2010, 16:22 | 3 | ||||||||||
Интересная задача.
Алгоритм решения
0)переменной, в которой будет число участков (у меня - k), присваиваем ноль
1)берём квадратный корень из числа имеющихся квадриков 2)округляем результат вниз до целого 3)возводим результат в квадрат 4)отнимаем результат от числа квадриков 5)k++; 6)повторяем п.п. 1-5 до тех пор, пока деньги не кончатся Код программы. Вариант с While
Код программы. Вариант с For
В программе я использовал консольный ввод/вывод. Если нужно из файла - переделывайте. Работоспособность кода проверена на приведённом в первом посте примере и для случая когда квадрик только 1. Использовал DevCPP 4.9.9.2
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.01.2010, 16:58 [ТС] | 4 |
Delphin_KKC, то что программа компилируется - это НЕ ЗНАЧИТ что задача правильно решена.
Ты забываешь что это олимпиадные задачи. А значит всегда есть над чем подумать. А именно - приведенный тобой алгоритм находит какое-то разбиение на квадраты. А нужно найти разбиение чтобы число квадратов было минимально. Добавлено через 3 минуты Вот тебе тест: N=18 Правильный ответ: 2 ( 9+9 ) Твоя программа выводит 3 ( видимо 16+1+1 )
1
|
UNIX-way
712 / 495 / 49
Регистрация: 15.01.2009
Сообщений: 1,720
|
|
08.01.2010, 17:53 | 5 |
Потому и написал что задача интересная.
Тот алгоритм - это первое до чего я додумался. По свободе подумаю над другими алгоритмами. Добавил вывод отладочной информации. Действительно 16+1+1.
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
08.01.2010, 18:18 [ТС] | 6 | |||||
Вспомнил - что-то подобное я уже решал.
Момент такой: Любое натуральное N может быть представлено в виде суммы квадратов не более чем 4-ех слагаемых. То есть в худшем случае будет 4 участка. Значит задача резко упрощается. 1) Проверить N - это A0^2 2) Проверить что N = A0^2+A1^2, причем A0>=A1 3) Проверить что N= A0^2+A1^2+A2^2, причем A0>=A1>=A2 4) Проверить - но можно и не проверять N = A0^2+A1^2+A2^2+A3^2, причем A0>=A1>=A2>=A3 Какой вариант нашли раньше - такой ответ и будет. Добавлено через 24 минуты Все - сдал ![]() Программа
2
|
║XLR8║
|
|
08.01.2010, 21:28 | 7 |
odip, хорошо что вы до теста 18 сами дошли, и то что програма рабочая - тоже хорошо, но можно поподробнее, именно тот факт что любое натуральное чисо можно представить в виде сумы не более чем 4-ех слагаемых?
0
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.01.2010, 21:38 [ТС] | 8 |
Что за тест 18 ?
Этот факт упоминался в какой-то олимпиадной задаче. Я проверял от 1 до INT_MAX - не врут ![]()
1
|
3131 / 1324 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
|
|
08.01.2010, 23:34 | 9 |
То, что Вы ищете есть не что иное, как знаменитая теорема Лагранжа о четырёх квадратах.
2
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
08.01.2010, 23:55 [ТС] | 10 |
Буду знать как называется
![]() Так вот для кубов: Каждое натуральное число представимо в виде суммы не более 8 кубов чисел.
0
|
b4990
|
||||||
25.09.2010, 18:36 | 11 | |||||
Извиняюсь за некрофильство, но возможно кому-то будет интересно.
Без знания теоремы Лагранджа задачу можно решить динамическим программированием, например так
|
25.09.2010, 18:36 | |
Помогаю со студенческими работами здесь
11
Свойства и методы классов Ученик, Учитель, Школа, Экзамен, Турнир, Урок, Страна, Браузер Реализовать односвязный список данных вида "Страна, город, количество населения" Разработать класс "Машина" с полями: марка, страна-производитель, максимальная скорость, объём двигателя игра "туманная страна" на с++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |