Суббота, 17 Февраля 2007 г.
14:28 Задачка
(Отборочный тур СПб математической олимпиады 2006 г., 10-й класс)
Два юноши в буфете угощают девушку конфетами. За один ход юноша покупает у буфетчицы 1 или 2 конфеты и отдаёт их девушке. Ходят по очереди. Изначально у молодых людей по 550 рублей, а у буфетчицы 1000 конфет. Каждая конфета стоит рубль. Игрок, который не может в свой ход угостить девушку, проигрывает. Кто выиграет при правильной игре?
(К.Кохась)
Бедная девушка...
Два юноши в буфете угощают девушку конфетами. За один ход юноша покупает у буфетчицы 1 или 2 конфеты и отдаёт их девушке. Ходят по очереди. Изначально у молодых людей по 550 рублей, а у буфетчицы 1000 конфет. Каждая конфета стоит рубль. Игрок, который не может в свой ход угостить девушку, проигрывает. Кто выиграет при правильной игре?
(К.Кохась)
Бедная девушка...
Группы: [ математика ]
[ юмор ]
Комментарии [7]
Среда, 15 Ноября 2006 г.
13:19 Задачка
Вот тут очень интересным человеком выложена интересная задачка по программированию. Интересна она не столько деталями решения (за исключением одной детали, задача совершенно тривиальная), сколько формулировкой. Я тоже обхохотался.
PS. После минутного размышления нетривиальная деталь тоже оказалась очевидной.
PS. После минутного размышления нетривиальная деталь тоже оказалась очевидной.
Группы: [ математика ]
[ юмор ]
Вторник, 8 Августа 2006 г.
10:28 Выпуклость на сетке
Пока я делал карту, придумал пару определений. Правда, не исключено, что аналогичные термины были придуманы и до меня, но сделать запись с вумным видом это мне не помешает.
Как легко доказать, составить из квадратиков выпуклую фигуру можно лишь в том случае, если эта выпуклая фигура – прямоугольник. Мне же при составлении карты хотелось, чтобы она не имела прямоугольный формы, но была в некотором смысле выпуклой. Поразмыслив немного, я сформулировал, что я имею в виду под этим самым "некоторым смыслом".
Как известно, область называется выпуклой, если любой отрезок, соединяющий две точки области, целиком принадлежит этой области. А теперь назовём область выпуклой относительно прямой l, если любой отрезок, соединяющий две точки области и параллельный прямой l, целиком принадлежит этой области.
Теперь легко определить выпуклость на прямоугольной сетке. Область, выпуклая на прямоугольной сетке, должна быть выпуклой относительно базисных прямых (понятно, что я имею в виду) этой сетки.
Легко видеть, что моя карта является выпуклой на горизонтально-вертикальной сетке.
Как легко доказать, составить из квадратиков выпуклую фигуру можно лишь в том случае, если эта выпуклая фигура – прямоугольник. Мне же при составлении карты хотелось, чтобы она не имела прямоугольный формы, но была в некотором смысле выпуклой. Поразмыслив немного, я сформулировал, что я имею в виду под этим самым "некоторым смыслом".
Как известно, область называется выпуклой, если любой отрезок, соединяющий две точки области, целиком принадлежит этой области. А теперь назовём область выпуклой относительно прямой l, если любой отрезок, соединяющий две точки области и параллельный прямой l, целиком принадлежит этой области.
Теперь легко определить выпуклость на прямоугольной сетке. Область, выпуклая на прямоугольной сетке, должна быть выпуклой относительно базисных прямых (понятно, что я имею в виду) этой сетки.
Легко видеть, что моя карта является выпуклой на горизонтально-вертикальной сетке.
Группы: [ математика ]
Вторник, 11 Июля 2006 г.
21:50 Яглом
Читаю книжку "Как разрезать квадрат?"
Очень интересная книжка оказалось. Достаточно легко, чтобы быть понятным, но и достаточно нетривиально, чтобы быть интересным. Жаль только, что я не наткнулся на неё лет на десять пораньше.
Наконец-то я понял это отображение разрезаний прямоугольника на квадраты на некоторый подкласс ориентированных взвешенных графов, веса которых подчиняются законам Кирхгофа.
Очень интересная книжка оказалось. Достаточно легко, чтобы быть понятным, но и достаточно нетривиально, чтобы быть интересным. Жаль только, что я не наткнулся на неё лет на десять пораньше.
Наконец-то я понял это отображение разрезаний прямоугольника на квадраты на некоторый подкласс ориентированных взвешенных графов, веса которых подчиняются законам Кирхгофа.
Группы: [ книги ]
[ математика ]
Вторник, 20 Июня 2006 г.
07:40 Задачка на футбольную тему
Всегда любил изучать, можно ли восстановить результаты матчей на основе турнирных таблиц. На картинке приведено положение команд в восьми группах после двух туров. В некоторых группах результаты можно вычислить однозначно. В некоторых есть варианты. А есть даже, когда нельзя однозначно определить, кто с кем играл. 
Группы: [ математика ]
Суббота, 22 Апреля 2006 г.
21:47 Суббота
Впервые после долгого перерыва поиграл в шахматы. Выиграл две довольно неплохие партии.
Писал программу для конвертации БД. Из DBF сконвертировал, теперь надо из Экселя. А то все заполняли кто в чём горазд...
Вчера от нечего делать набрёл на задачку, которая привела к некоторым числам. Не знаю, как они называются, но я для себя назвал их обобщёнными сочетаниями. Если в треугольнике Паскаля каждое число является суммой двух вышестоящих, то здесь – (M+1) вышестоящих. Жаль, неудобно тут писать формулы...
Но задачка, приводящая к ним, очень простая в формулировке. Сколько комбинаций из N неотрицательных целых чисел, каждое из которых не превосходит M, дают в сумме число K?
Писал программу для конвертации БД. Из DBF сконвертировал, теперь надо из Экселя. А то все заполняли кто в чём горазд...
Вчера от нечего делать набрёл на задачку, которая привела к некоторым числам. Не знаю, как они называются, но я для себя назвал их обобщёнными сочетаниями. Если в треугольнике Паскаля каждое число является суммой двух вышестоящих, то здесь – (M+1) вышестоящих. Жаль, неудобно тут писать формулы...
Но задачка, приводящая к ним, очень простая в формулировке. Сколько комбинаций из N неотрицательных целых чисел, каждое из которых не превосходит M, дают в сумме число K?
Группы: [ математика ]
Понедельник, 20 Февраля 2006 г.
08:26 Как я провёл "лето"
В субботу ездили к дяде Валере. Формально – на день рождения Оли. Как ни стыдно, я её вроде ни разу (по крайней мере, не помню) не видел за 15 лет. Заодно познакомился с их новым домом. Мама говорила, что он большой (она вообще большая завистница), так что когда нам с Костей (который тоже никогда там не был) устроили экскурсию по дому, я был разочарован. На первом этаже — большая кухня и 2 маленьких (по сравнению с кухней) комнаты. На втором этаже ещё 2 такие же комнаты плюс комната-балкон (а как ещё назвать такой многооконный павильон?) над кухней, да ещё одна действительно большая комната над гаражом. Свалка на чердачном третьем этаже, пара холодных комнат в подвале (одна из них как раз и используется для хранения банок). Но на самом деле портит впечатление от дома лестница. Типичная винтовая пожарная лестница. И такая же узкая. И даже ещё без перил. А всё остальное очень даже удобно. Вот что мне очень понравилось, так это обилие туалетов. Я видел их целых 3. Не исключено, что где-то ещё завалялись.
После еды я обнаружил, что девочки играют за компьютером и никак не могут пройти головоломки из квеста. Игра мне понравилась настолько, что в воскресенье я её даже купил себе. Называется "Sentinel: страж времени". Типичный мистоидный квест. Сюжета никакого, зато какие головоломки! Особенно мне понравилась одна с гирляндами, которые нужно зажигать. Смысл в следующем. Есть гирлянда из 20 лампочек. Каждая из них можент находиться в состоянии от 0 до 4 включительно. Имеются 4 панели. На каждой из них по 8 рычагов. Каждый включенный рычаг добавляет 1 к состоянию 15 лампочек. Надо включить по одному рычагу на каждой панели так, чтобы все лампочки оказались в состоянии 3. Выписал на лист бумаги в клетку 640 (=4*8*20) цифр, помедитировал над ними и довольно быстро получил ответ. В общем, хорошо съездил в гости! Мама потом сказала, что свинья везде компьютер найдёт.
В воскресенье ходили с Кселлосом пить чай, после чего я купил этот самый диск, а заодно "Логические игры и головоломки". Но вечером играл исключительно в GW. Прошёл со случайной партией (правда, два человека там вроде знали друг друга) миссию по защите крепости. Работал монахом-лекарем. Это для меня куда легче, чем бить монстров. А на острове, куда я попал после этого, вытащил два полезных элитных скилла.
После еды я обнаружил, что девочки играют за компьютером и никак не могут пройти головоломки из квеста. Игра мне понравилась настолько, что в воскресенье я её даже купил себе. Называется "Sentinel: страж времени". Типичный мистоидный квест. Сюжета никакого, зато какие головоломки! Особенно мне понравилась одна с гирляндами, которые нужно зажигать. Смысл в следующем. Есть гирлянда из 20 лампочек. Каждая из них можент находиться в состоянии от 0 до 4 включительно. Имеются 4 панели. На каждой из них по 8 рычагов. Каждый включенный рычаг добавляет 1 к состоянию 15 лампочек. Надо включить по одному рычагу на каждой панели так, чтобы все лампочки оказались в состоянии 3. Выписал на лист бумаги в клетку 640 (=4*8*20) цифр, помедитировал над ними и довольно быстро получил ответ. В общем, хорошо съездил в гости! Мама потом сказала, что свинья везде компьютер найдёт.
В воскресенье ходили с Кселлосом пить чай, после чего я купил этот самый диск, а заодно "Логические игры и головоломки". Но вечером играл исключительно в GW. Прошёл со случайной партией (правда, два человека там вроде знали друг друга) миссию по защите крепости. Работал монахом-лекарем. Это для меня куда легче, чем бить монстров. А на острове, куда я попал после этого, вытащил два полезных элитных скилла.
Группы: [ игры ]
[ математика ]
Комментарии [15]
Пятница, 10 Февраля 2006 г.
08:36 GW и арифметика
Немного предыстории.
В GW, как и в большинстве других ролевых игр, есть такое понятие, как опыт (Experience points). Опыт даётся за выполнение миссий и квестов, а также за убийство монстров. А ещё в GW есть уровень (Level). От уровня персонажа зависит его здоровье и наносимый урон. После накопления определённого количества опыта персонаж получает следующий уровень, а вместе с уровнем ещё и attribute points (речь сейчас не о них) и скилл-пойнты (SP). Но фокус в том, что максимальный уровень, который может получить персонаж – 20. 20 уровень набирается примерно к середине сюжетной линии, и дальше по мере набора опыта уровень не растёт, а даются только скилл-пойнты.
Скилл-пойнты нужны для покупки заклинаний у торговцев. На каждое купленное заклинание тратится скилл-пойнт и определённое количество денег (чем дальше, тем больше). При этом из 156 заклинаний, доступных элементалисту-монаху, только 80 даются бесплатно (за квесты). Остальные 76 нужно либо покупать, либо вытягивать из боссов. Учитывая, что 2 Signet of Capture даются бесплатно, получаем, что для сбора всех доступных заклинаний элементалист-монах должен набрать за свою жизнь 74 скилл-пойнта.
Скилл-пойнты даются как за уровни (и "виртуальные уровни" в дальнейшем), так и за миссии и некоторые квесты. И вот решил я понять, сколько же скилл-пойнтов к данному моменту я получил именно за опыт (пересчитывать миссии и вспоминать квесты, за которые я мог получить скилл-пойнты, мне не хотелось).
Итак, я имел 47 скилл-пойнтов и 263856 опыта. Следующий скилл-пойнт, как мне любезно подсказал интерфейс, будет получен при достижении 272600 опыта.
На одном из сайтов я нашёл сведения, из которых вывел простую формулу арифметической прогрессии: между уровнями (L-1) и L нужно набрать D(L)=800+600*L опыта (L>=2, так как первый уровень персонаж имеет сразу). Просуммировав, нетрудно получить, что общий опыт, необходимый для достижения уровня L, составляет S(L)=100*(3*L+14)*(L-1). Проверив на своих дополнительных низкоуровневых персонажах, я убедился, что формула вроде верна.
И тут меня ждало разочарование. При попытке приравнять S(L)=272600 я обнаружил, что целочисленного решения нет. То есть для моих "виртуальных уровней" эта формула уже не работает!
Первой гипотезой была следующая: раз уровень после 20-го не меняется, возможно, что его дают за фиксированную разницу опыта. То есть логично было предположить, что S(20)=140600, а дальше D(L)=D(21)=13400. Но и эта гипотеза оказалась неверной.
На другом сайте я нашёл сведения, что после 20-го уровня даётся 1 скилл-пойнт на каждые 15000 опыта. Подставил в первую гипотезу вместо 13400 15000, но тоже не получил ничего разумного.
И только тут я догадался! Третья моя гипотеза заключалась в том, что D(L) растёт, пока не превосходит 15000, а потом обрезается на этой отметке. То есть D(23)=14600, а D(24)=D(25)=15000. Проверяем... S(23)=182600.
(272600-182600)/15000=6. Работает! Таким образом, мой "виртуальный уровень" на данный момент составляет L=23+6-1=28, а за опыт я получил 28-1=27 скилл-пойнтов. Остальные 47-27=20 скилл-пойнтов – за квесты и миссии.
В GW, как и в большинстве других ролевых игр, есть такое понятие, как опыт (Experience points). Опыт даётся за выполнение миссий и квестов, а также за убийство монстров. А ещё в GW есть уровень (Level). От уровня персонажа зависит его здоровье и наносимый урон. После накопления определённого количества опыта персонаж получает следующий уровень, а вместе с уровнем ещё и attribute points (речь сейчас не о них) и скилл-пойнты (SP). Но фокус в том, что максимальный уровень, который может получить персонаж – 20. 20 уровень набирается примерно к середине сюжетной линии, и дальше по мере набора опыта уровень не растёт, а даются только скилл-пойнты.
Скилл-пойнты нужны для покупки заклинаний у торговцев. На каждое купленное заклинание тратится скилл-пойнт и определённое количество денег (чем дальше, тем больше). При этом из 156 заклинаний, доступных элементалисту-монаху, только 80 даются бесплатно (за квесты). Остальные 76 нужно либо покупать, либо вытягивать из боссов. Учитывая, что 2 Signet of Capture даются бесплатно, получаем, что для сбора всех доступных заклинаний элементалист-монах должен набрать за свою жизнь 74 скилл-пойнта.
Скилл-пойнты даются как за уровни (и "виртуальные уровни" в дальнейшем), так и за миссии и некоторые квесты. И вот решил я понять, сколько же скилл-пойнтов к данному моменту я получил именно за опыт (пересчитывать миссии и вспоминать квесты, за которые я мог получить скилл-пойнты, мне не хотелось).
Итак, я имел 47 скилл-пойнтов и 263856 опыта. Следующий скилл-пойнт, как мне любезно подсказал интерфейс, будет получен при достижении 272600 опыта.
На одном из сайтов я нашёл сведения, из которых вывел простую формулу арифметической прогрессии: между уровнями (L-1) и L нужно набрать D(L)=800+600*L опыта (L>=2, так как первый уровень персонаж имеет сразу). Просуммировав, нетрудно получить, что общий опыт, необходимый для достижения уровня L, составляет S(L)=100*(3*L+14)*(L-1). Проверив на своих дополнительных низкоуровневых персонажах, я убедился, что формула вроде верна.
И тут меня ждало разочарование. При попытке приравнять S(L)=272600 я обнаружил, что целочисленного решения нет. То есть для моих "виртуальных уровней" эта формула уже не работает!
Первой гипотезой была следующая: раз уровень после 20-го не меняется, возможно, что его дают за фиксированную разницу опыта. То есть логично было предположить, что S(20)=140600, а дальше D(L)=D(21)=13400. Но и эта гипотеза оказалась неверной.
На другом сайте я нашёл сведения, что после 20-го уровня даётся 1 скилл-пойнт на каждые 15000 опыта. Подставил в первую гипотезу вместо 13400 15000, но тоже не получил ничего разумного.
И только тут я догадался! Третья моя гипотеза заключалась в том, что D(L) растёт, пока не превосходит 15000, а потом обрезается на этой отметке. То есть D(23)=14600, а D(24)=D(25)=15000. Проверяем... S(23)=182600.
(272600-182600)/15000=6. Работает! Таким образом, мой "виртуальный уровень" на данный момент составляет L=23+6-1=28, а за опыт я получил 28-1=27 скилл-пойнтов. Остальные 47-27=20 скилл-пойнтов – за квесты и миссии.
Четверг, 10 Ноября 2005 г.
11:02 Карта Москвы в метро
Вчера я обратил внимание на карту Москвы, висящую в метро. На ней показаны все линии метро не схематично, а прямо на фоне улиц.
Но очевидно, что эта карта искажена, так как центр Москвы на ней гораздо больше, чем на самом деле. Вот и думал, какое преобразование могло быть использовано для создания такого эффекта.
В голову сразу приходит два варианта (в обоих предполагается, что полярный угол сохраняется).
1) r → r*√(R/(R+r))
R ≈ 2 км
2) r → ∫(exp(-x²/R²))dx
R ≈ 20 км
(интеграл от 0 до r)
Но очевидно, что эта карта искажена, так как центр Москвы на ней гораздо больше, чем на самом деле. Вот и думал, какое преобразование могло быть использовано для создания такого эффекта.
В голову сразу приходит два варианта (в обоих предполагается, что полярный угол сохраняется).
1) r → r*√(R/(R+r))
R ≈ 2 км
2) r → ∫(exp(-x²/R²))dx
R ≈ 20 км
(интеграл от 0 до r)
Группы: [ математика ]
[ рельсовый транспорт ]
Комментарии [5]
Я жив
[Print]
kv75