Форум «Всё о Паскале» _ Задачи _ Обсуждение некоторых задач
Автор: Vinchkovsky 10.01.2007 17:57
Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу (хотя тогда, наверное, я знал несколько меньше, чем сейчас), а здесь сходу за пять минут накатал решение первой из предыдущего поста.
program Zadacha1; uses Crt; var c:boolean; a,b:string; function Sovmestimost(a,b:string):boolean; var len1,len2,i,ii,res:integer; aM,bM:array [1..20] of string; d3:boolean; begin res:=0; len1:=length(a); len2:=length(b); for i:=1 to len1 do aM[i]:=copy(a,i,1); for i:=1 to len2 do bM[i]:=copy(b,i,1); for i:=1 to len2 do for ii:=1 to len1 do if bM[i]=aM[ii] then begin res:=res+1; aM[ii]:=''; bM[i]:='*' end; if res=len2 then d3:=true else d3:=false; Sovmestimost:=d3 end; begin clrscr; writeln('Vvedite pervoe slovo'); readln(a); writeln('Vvedite vtoroe slovo'); readln(b); if length(a)>length(b) then c:=Sovmestimost(a,b) else c:=Sovmestimost(b,a); if c=true then writeln('YES') else writeln('NO'); readln end.
В общем, можно сделать все намного изящнее (напр., процедуру проверки, есть ли "меньшее слово в старшем", сравнить слова и применить процедуру на меньшем), но, так как в задаче ничего не сказано, делал все по проще, так что не судите строго
Ну а вот вторая:
program Zadacha2; uses Crt; const n=6; type masyv=array [1..n] of integer; var a,b:masyv; i,ii,x:integer; begin clrscr; writeln('Vvedite 6 chusel'); for i:=1 to n do readln(a[i]); for i:=1 to n-1 do for ii:=i+1 to n do begin if a[i]>a[ii] then begin x:=a[i]; a[i]:=a[ii]; a[ii]:=x end end; if (a[1]+a[6]=a[2]+a[5])and(a[2]+a[5]=a[3]+a[4]) then writeln(a[1]+a[6]) else writeln('N'); readln end.
А это третья . Знаю, написано плохо в плане стиля, но на доработку и оптимизацию нет времени да и желания (главное, что верно, об чем я надеюсь). Это верно, что этих чисел Армстронга так немного? Например, при н=2 нуль, при н=3 четыре (153,370,371,407), при н=4 три, а при н=5 нуль?
program zadaha3; uses Crt; var n,d5,k,ii:integer; min,max,i,control:longint; iText:string; iLetter:array [1..10] of string; iDigit:array [1..10] of integer;
function Stepin(x,y:integer):integer; var d1:integer; d2:integer; begin d2:=x; for d1:=1 to y-1 do d2:=d2*x; Stepin:=d2 end;
function Minimal(n:integer):longint; var d3:integer; d4:longint; begin d4:=1; if n=0 then d4:=1 else for d3:=1 to n-1 do d4:=d4*10; Minimal:=d4 end;
begin clrscr; writeln('Vvedite n'); readln(n); min:=Minimal(n); max:=Minimal(n+1)-1; for i:=min to max do begin control:=0; str(i,iText); for ii:=1 to n do begin iLetter[ii]:=copy(iText,ii,1); val(iLetter[ii],iDigit[ii],d5) end; for ii:=1 to n do control:=control+Stepin(iDigit[ii],n); if control=i then begin writeln(i); k:=k+1 end end; writeln('Vsego chusel Armstronga ',k); readln end.
Автор: Айра 10.01.2007 18:59
Цитата
так что не судите строго
Попробуй ввести в свою первую прогу "стст" и "стср" и посмотри, что она выдаст. Мне выдала "Mozhno". И в условии вроде не сказано, что слова не могут иметь одинаковое кол-во символов. Так что, как мне уже говорили:
Цитата
такие задачи в лоб не решаются
Автор: Malice 10.01.2007 19:07
Цитата(Vinchkovsky @ 10.01.2007 13:57)
Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу (хотя тогда, наверное, я знал несколько меньше, чем сейчас), а здесь сходу за пять минут накатал решение первой из предыдущего поста.
Не переживай, все равно не правильно накатал (131, 231 к примеру) Попробуй 4-ую порешай, первые 3 решаются в уме..
Автор: Michael_Rybak 10.01.2007 19:28
Цитата(Vinchkovsky @ 10.01.2007 12:57)
Хех... А у вас, в России, задачи ИМХО намого легче, нежели у нас, на Украине. Учусь в 10 класе обычной провинциальной школы, на 2 этапе смог решить лишь одну задачу
Особенно смешно слово "намного".
Ты ошибаешься. Задачи в России даже теоретически ничем не могут уступать задачам из Украины. Кроме того, второй этап - совсем уж не показатель, т.к. зачастую их составляют (а еще чаще - берут) совсем не те люди, которые состоят в комитете всероссийской/всеукраинской олимпиады.
В одном и том же городе (я, в частности, про Киев) районные олимпиады могут проходить на разных задач в разных районах; в прошлом году районная соломенского района была сложнее городской, потому что отвечали за это совершенно некомпетентные люди - просто взяли городские прошлых лет, и повыбирали задачи, у которых балл повыше.
P.S. В данном конкретном случае первые три действительно очень простые. А вот с четвертой (супер-решение которой, кстати, недавно показывал volvo) - похитрее.
Автор: Vinchkovsky 10.01.2007 22:27
Айра, Malice, ну я же написал, что для упрощения сделал по умолчанию первое слово больше второго:
Цитата
В общем, можно сделать все намного изящнее (напр., процедуру проверки, есть ли "меньшее слово в старшем", сравнить слова и применить процедуру на меньшем), но, так как в задаче ничего не сказано, делал все по проще, так что не судите строго
то есть, я показывал принцип, завтра поправлю и выложу полностью верное решение, если это принципиально. Ну а пока тестируйте при слово1>слово2.
Цитата
Попробуй 4-ую порешай, первые 3 решаются в уме..
Я про это и говорил! На российских олимпидах большинство задач решаються в уме, ИМХО, где-то выложу наши задачи, вот и сравните. У нас в уме решается только первая А над последней подумаю, обязательно.
Michael_Rybak, у нас в городе (Львовской области) стабильно все задачи на одном уровне и тяжелее от этих. Да и во всей области задачи ОДИНАКОВЫЕ со всех олимпиад, и складает их какой-то институт ЛОИППО (что-то связано с последипломной учебой). Это все мое личное мнение. Если сделал поспешное заключение, сравнивая лишь одну рос.олимпиаду, то извините. Постараюсь выложить наши задачи, сравните.
И я знаю про недоработки в своих задачах: громоздкий код, большее слово должно быть первым(з1), очень долго считает при н больше 7(з.3);извините, я это постараюсь исправить (задачи делал на скорую руку).
to All - допустился досадной очепятки, вместо НАМОГО должно быть НЕМНОГО, а не намного (хотя последнее, в принципе, вернее) ____________________________________________________________________________ Вот к примеру вторая задача из четырех, 20 баллов (всего-130)
Городок состоит из n домов, которые стоят вдоль прямого шоссе на одном расстоянии один от одного. В городке проводят телефонное подключение, в каждом доме нужно поставить k (0<=k<=30000). В первом рядке файла TEL.DAT содержится количество домов (1<=n<=1000). В следующем рядке через пропуск - количество телефонов, которые должы быть установлены в домах. Вывести на экран и в первый рядок файла TEL.SOL номер дома, в котором нужно поставить АТС, чтобы общее количество кабеля от каждого телефона к АТС было минимальным. Если таких домов несколько, то написать их в порядке увеличения черех пропуск. Каждый телефон соединен отдельным кабелем. Если телефон находится в том доме, что АТС, то считать, что кабеля не ведем. Пример входных данных: 5 1 2 3 2 1 Пример выходных данных: 3 _______________________________________________________________________
Может я и ошибаюсь, но как на меня, то это небо и земля в сравнении с вашей второй задачей
Автор: мисс_граффити 10.01.2007 22:44
а можно условия задач, код к которым содержится в первом сообщении?
Автор: Michael_Rybak 10.01.2007 22:54
Цитата
Michael_Rybak, у нас в городе (Львовской области) стабильно все задачи на одном уровне и тяжелее от этих. Да и во всей области задачи ОДИНАКОВЫЕ со всех олимпиад, и складает их какой-то институт ЛОИППО (что-то связано с последипломной учебой).
Ну вот во львовской - так, а в других - по разному. Я думаю, что наиболее показательны городские/областные и http://neerc.ifmo.ru/school/archive/index.html/http://www.uoi.kiev.ua. Кроме того, сложность, когда речь идет о задачах уровня IOI и выше, не самое ценное качество; главное, на мой взгляд, в задаче - свежесть, оригинальность. А сложность можно получать разными путями.
Цитата
Вот к примеру вторая задача из четырех, 20 баллов (всего-130)
Городок состоит из n домов, которые стоят вдоль прямого шоссе на одном расстоянии один от одного. В городке проводят телефонное подключение, в каждом доме нужно поставить k (0<=k<=30000). В первом рядке файла TEL.DAT содержится количество домов (1<=n<=1000). В следующем рядке через пропуск - количество телефонов, которые должы быть установлены в домах. Вывести на экран и в первый рядок файла TEL.SOL номер дома, в котором нужно поставить АТС, чтобы общее количество кабеля от каждого телефона к АТС было минимальным. Если таких домов несколько, то написать их в порядке увеличения черех пропуск. Каждый телефон соединен отдельным кабелем. Если телефон находится в том доме, что АТС, то считать, что кабеля не ведем. Пример входных данных: 5 1 2 3 2 1 Пример выходных данных:
3
Цитата
Может я и ошибаюсь, но как на меня, то это небо и земля в сравнении с вашей второй задачей
Я бы сказал, трава и земля ;) Код-то (особенно учитывая, что O(N^2) должен проходить) ненамного длиннее будет, чем твоя program zadacha2. Даже короче, наверное. Как решать - знаешь?
Цитата
а можно условия задач, код к которым содержится в первом сообщении?
to All, вы меня неверно поняли. Я своими постами не создавал межнациональную неприязнь. Я просто указывал на своё мнение. Я не имел ввиду, что украинцам и мне в частности все задачки "по зубам" и я щелкаю даже самые сложные задачи. Скорее наоборот - я признал, что смог решить ТОЛЬКО ОДНУ ЗАДАЧУ из нашей олимпиады. Я не указываю на то, что крут, тем, что решил (и то криво!!!) 3 ваших задач. Последюю задачу, которую я запостил, не знаю, как решать. Кто увидел в моих постах неприязнь к россиянам, или то, что хвалюсь своей крутостью - если не трудно, очень прошу зацитировать. Не обращайте внимание на условное деление задач и олимпиад на "ВАШИ" и "НАШИ". Повторюсь, это условно, сделано без какого-либо намерения и не подчеркивает разность народов. Прошу извинить меня, если кто-то заметил двузначность в моих словах. Это значит, что вы меня не поняли; я не имел ввиду ничего плохого, и, собственно, такие слова принимайте в лучшей стороне. Прошу извинить меня за вынужденный оффтоп и не очень хороший русский. В принципе, "в кожній хаті-своя правда ", но я прошу избавится от стереотипа того, что все россияне украинцам враги. Это не так; социальная обстановка не должна совпадать с политической. И вобще - я за "мир во всем мире" и равенство словянских народов, и если кто-то подумал совсем по-другому, прошу внимательно перечитать мои посты Michael_Rybak, если можешь, запости решение в топик с задачами (я про свою задачу) И ЕЩЕ-все решения - полностью и на 100% мои собственные, я не использовал материалы других сайтов или уже готовые решения.
Автор: мисс_граффити 11.01.2007 0:09
Vinchkovsky, перебором можно решать.... но с учетом того, что работаем с файлами - это будет весьма медленно... никаких ограничений по времени и памяти нет?
Автор: Vinchkovsky 11.01.2007 0:16
Ограничений нет никаких, в принципе, можно попробовать перебором . Хотя должен быть какой-то более рациональный способ? Действительно, при 30000 телефонов на дом и 1000 домов програма будет работать достаточно долго. Я не совсем понял это: особенно учитывая, что O(N^2) должен проходить???
Автор: мисс_граффити 11.01.2007 0:20
так.... смотри: если у нас телефоны распределены равномерно (ну например 2 2 2 2 2), то рационально размещать АТС по центру. В общем же случае это не так => надо искать "центр тяжести" системы...
Автор: Michael_Rybak 11.01.2007 1:27
Цитата(Vinchkovsky @ 10.01.2007 18:55)
to All, вы меня неверно поняли.
Нет, это *ты* неправильно понял Я и не считаю что ты
Цитата
своими постами создавал межнациональную неприязнь. имел ввиду, что украинцам и мне в частности все задачки "по зубам" и я щелкаю даже самые сложные задачи.
Я понял, что ты сравнил свою и эту районные олимпиады, и сказал что твоя сложнее. И рискнул обобщить до межнационального уровня - вот против этого я и возражал
Цитата
Скорее наоборот - я признал, что смог решить ТОЛЬКО ОДНУ ЗАДАЧУ из нашей олимпиады. Я не указываю на то, что крут, тем, что решил (и то криво!!!) 3 ваших задач. Последюю задачу, которую я запостил, не знаю, как решать. Кто увидел в моих постах неприязнь к россиянам, или то, что хвалюсь своей крутостью - если не трудно, очень прошу зацитировать.
Не обращайте внимание на условное деление задач и олимпиад на "ВАШИ" и "НАШИ". Повторюсь, это условно, сделано без какого-либо намерения и не подчеркивает разность народов. Прошу извинить меня, если кто-то заметил двузначность в моих словах. Это значит, что вы меня не поняли; я не имел ввиду ничего плохого, и, собственно, такие слова принимайте в лучшей стороне. Прошу извинить меня за вынужденный оффтоп и не очень хороший русский. В принципе, "в кожній хаті-своя правда ", но я прошу избавится от стереотипа того, что все россияне украинцам враги. Это не так; социальная обстановка не должна совпадать с политической. И вобще - я за "мир во всем мире" и равенство словянских народов, и если кто-то подумал совсем по-другому, прошу внимательно перечитать мои посты
Не переймайся, брате ;)
Цитата
Я не совсем понял это: особенно учитывая, что O(N^2) должен проходить
Это означает, что решение с временной оценкой O(N^2) должно набирать полный балл по этой задаче. Это следует из того, что n <= 1000.
Вообще я не понимаю проблемы: спрашивают,
Цитата
номер дома, в котором нужно поставить АТС
Всего домов n, а значит
Цитата(мисс_граффити @ 10.01.2007 19:09)
перебором можно решать....
Для каждого дома вычисляем общую длину кабеля и выбираем лучшие дома: (псевдопаскаль)
... function CalcCabel(i) begin cabel := 0; for j := 1 to n do cabel := cabel + Abs(i - j) * phones[j]; CalcCabel := cabel; end;
...
best := 10^12; for i := 1 to n do best := min(best, CalcCabel(i)); for i := 1 to n do if CalcCabel(i) = best then Write(i, ' ');
...
Небольшая, но очень важная деталь: с таким выводом легко получить 0 баллов по задаче, потому что в условии сказано "написать их в порядке увеличения через пропуск", т.е. после последнего номера не нужно выводить пробел. Это вообще жутко юзаные грабли.
Ну и другие тут грабли тоже скрыты - для теста n = 1000 и в каждом доме по 30000 ответ чуть-чуть вылазит за лонгинт.
Автор: мисс_граффити 11.01.2007 1:35
Цитата
т.е. после последнего номера не нужно выводить пробел.
Собираем в строку, и перед выводом в файл удаляем последний пробел.... А вот со вторым хуже....
Но на 1000 домов это будет работать довольно долго (с учетом, что файл текстовый...) Попробую насчет центра тяжести додумать.
Автор: Michael_Rybak 11.01.2007 1:47
Цитата
Собираем в строку, и перед выводом в файл удаляем последний пробел....
В общем случае так лучше не делать; 1) строки медленно собираются вроде бы (каждый раз строится новая строка), 2) сама конвертация время занимает. При больших данных и то и другое (особенно первое) критично.
Проще с флагом: if not first then Write(' '); Write(i); first := false;
Цитата
А вот со вторым хуже....
Тоже ничего страшного; comp ведь никто не отменял.
Цитата
Но на 1000 домов это будет работать довольно долго (с учетом, что файл текстовый...)
Так мы ж сначала массив заводим, а потом по нему бегаем. Быстро должно работать.
Вообще задача решается за O(N), без внутреннего цикла - просто бежим сначала слева-направо, накапливая кабель, а потом справа-налево. Но здесь и N^2 покатит.
Автор: Vinchkovsky 11.01.2007 16:30
Цитата(Michael_Rybak @ 10.01.2007 22:27)
Нет, это *ты* неправильно понял Я и не считаю что ты...
Мне это приятно. Получается, только админ считает так и меня неверно понял Спасибо тебе и мисс_граффити за помощь в решении задачи ___________________________________ Чтобы не засорять форум и не создавать лишних тем, пару слов об следующей задаче:
Цитата
Задача 4. Числа от 1 до n расставлены по кругу. Вычеркиваем каждое второе число, начиная с 1. Написать программу, которая определит какое число останется последним и напечатает его. Исходное натуральное число - 1<n=<=1 000 000. Общий случай: определите количество шагов для произвольного числа.
Например, н=7. Тогда что делаем - это:
Цитата
1 2 3 4 5 6 7 2 4 6 6 2
(выделеная цифра, которая вычеркивается) или как? Тоесть, я прошу пример выводных данных (на верное решение не толкайте, хочу сам понять)
Автор: Malice 11.01.2007 17:21
Нет, вот так:
Цитата
1 2 3 4 5 6 7 1 3 5 7 3 7
Ааа, пока тебе пример писал дошло как в 3 строки сделать ! Пойду попробую
Автор: мисс_граффити 11.01.2007 21:07
Поиск->Казнь или Считалка. Решалось на массивах.
Если понимать "по кругу" буквально, надо делать циклический список... Но, имхо, если олимпиада школьная, это относится только к тому, как работать с данными (то есть после последнего переходить на первое.)
Автор: Vinchkovsky 11.01.2007 23:44
Да я не хочу решение, а просто утачниваю условие задачи. Но все равно спасибо.
Есть в общем идейка - написать процедуру смещения тех чисел, которые остаются, на места тех, которые будем стирать (в динамическом массиве, ведь n-потенциальное longint), а лишним елементам присуждаем "0". И собственно применять эту процедуру, пока не останется 1 символ, отличный от нуля. Только в процедуре надо сделать отдельно старт с нулевой ситуации (ведь стираем с единницы) и отдельно последующие операции, анализируя парность количества елементов, которые остались (тоесть, новых n). Уже большую половину реализовал, завтра буду доканчивать.
Автор: мисс_граффити 12.01.2007 0:05
если массив динамический, то зачем присваивать нули? удалять элементы...
Автор: Malice 12.01.2007 14:01
Цитата(мисс_граффити @ 11.01.2007 17:07)
Поиск->Казнь или Считалка. Решалось на массивах.
Решение усложняется максимальным значением n=1 000 000. На на массивах тоже можно при желании. Допустим для того, чтобы знать вычеркнут/не вычеркнут достаточно 1-го бита, т.е. размер сокращается до 1000000/8 =125000. Пока еще не хватает. Но, учитывая, что при первом проходе быдут вычеркнуты все четные элементы, мы точно знаем, что младший бит=1 и его хранить не надо. Тогда размер массива сокращается до 125000/2 = 62500. Такой массив запросто организуется в tp. Кстати, на счет 3-х строк выше я погорячился слегка, вышло побольше, но не намного. Пока не выкладываю, чтоб не мешать..
Автор: Vinchkovsky 12.01.2007 14:43
В общем,смещением массива все проходит, но только к верхней границе. Тоесть, для большых чисел моя прога не подходит . Malice, тебя не очень понял, можешь подробно обяснить? А сама задача, в общем, вполне решаема, только проблема с большыми числами . И еще - дайте кто-то линк на FAQ про списки и дин.массивы (описание процедур), а то на факе форума нет, а в и-нете не нашел - почти все под Дельфи . p.s. А название топика не совсем соотвествовало его теме
Автор: Malice 12.01.2007 15:09
Цитата(Vinchkovsky @ 12.01.2007 10:43)
Malice, тебя не очень понял, можешь подробно обяснить?
На массивах ? Запросто.. Смотри: одно число типа byte може хранить информацию вычеркнут/нет о 8-ми числах. Берем пример, n=7. (в одном байте чтоб) В начале массив=0 12345678 (8-не используется, по-этому ставим *) 0000000* левый младший 0101010* 1-ый проход 1101110*- 2-ой 1111110*- 3-й Осталась 7-ка. n=12, используется 2 байта 12345678 12345678 01010101 0101**** 01110111 0111**** 01111111 0111**** 11111111 0111**** Осталась 9-ка Повторюсь- т.к. все четные сразу вычеркиваются то 1 бит можно не хранить и массив сократится еще в 2 раза, что позволит организовать такой массив в TP и мы будем знать 1-ый бит результата. Ps. Путем дальнейших логических умозаключений можно точно вычислить и следующий бит результата, что приведет к сокращению массива еще на половину и так до полного исчезновения массива как такового..
Автор: Michael_Rybak 12.01.2007 18:40
Цитата(Malice @ 12.01.2007 9:01)
Решение усложняется максимальным значением n=1 000 000. На на массивах тоже можно при желании. Допустим для того, чтобы знать вычеркнут/не вычеркнут достаточно 1-го бита, т.е. размер сокращается до 1000000/8 =125000. Пока еще не хватает. Но, учитывая, что при первом проходе быдут вычеркнуты все четные элементы, мы точно знаем, что младший бит=1 и его хранить не надо. Тогда размер массива сокращается до 125000/2 = 62500. Такой массив запросто организуется в tp.
Всеукраинки (и вроде бы областные) уже достаточно давно тестируются на fp. Так что не думаю, что эта проблема стоит.
Но!
Нам это на самом деле не нужно. Можно просто помнить, какие числа сейчас есть, и с какого числа (первого или второго) начинаем вычеркивать.
Пример:
1 2 3 4 5 6 7 8 9 10 11 - есть числа вида K+1, где 0 <= K <= 10, вычеркиваем, начиная со 2го 1 2 3 4 5 6 7 8 9 10 11 - четность меняется, теперь начнем вычеркивать с первого
1 3 5 7 9 11 - есть числа вида 2K+1, где 0 <= K <= 5, вычеркиваем, начиная с 1го 1 3 5 7 9 11 - опять начнем вычеркивать с 1го
3 7 - есть числа вида 4K+3, где 0 <= K <= 1, вычеркиваем, начиная с 1го: 3 7
7 - есть числа вида 8К+7, где 0 <= K <= 0, вычеркиваем, начиная с 1го.
После каждого прохода будут оставаться числа вида (2^p)K + t, где 1 <= t <= 2^p (чтобы выполнялось 0<=t<2^p, надо вести нумерацию с 0), а К лежит в пределах от 0 до некоторого q. Поэтому их можно хранить не массивом, а тройкой (p, t, q).
Автор: Гость 12.01.2007 19:00
Вот как сделал я:
var i,first, last,pred,y,n:longint; begin readln(n); y:=0; first:=0; last:=n; pred:=n; repeat for i:=1 to n do if (i and y) xor first=0 then begin write (i,' '); last:=i; end; writeln; first:=first+(y+1)*byte(last=pred); pred:=last; y:=y shl 1+1; until (first=last) or (first>n); writeln (last); end.
Как мне кажется, очень логично получилось
Автор: Malice 12.01.2007 19:02
Цитата(Гость @ 12.01.2007 15:00)
Вот как сделал я:
Это я был, зайти забыл, но по стилю, имхо, и так понятно
Автор: мисс_граффити 12.01.2007 19:28
Цитата
И еще - дайте кто-то линк на FAQ про списки и дин.массивы (описание процедур), а то на факе форума нет, а в и-нете не нашел - почти все под Дельфи