Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Miniolimp порядковый номер букв и чисел
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию Miniolimp порядковый номер букв и чисел - 31.01.2006, 21:21

Пусть X = xn-1)

Тут N(a) = 0, N(B) = 1, N© = 2, ..., N(z) = 25 - порядковый номер буквы в латинице, начиная с нуля. Для произвольных X - не пустой последовательности и h - натурального числа, создадим такую функцию:

HF(X, h) - это остаток от деления N(X) на h. Вам надобно исследовать поведение функции HF.

Задание
Дано последовательность X длинны n, которая содержит только маленькие буквы латиницы, и натуральное число h. Рассмотрим все возможные (в смысле разных индексов i и j) ее непустые подпоследовательности Xij и значения HF(Xij, h), которые достигает функция на этих последовательностях. Вам надобно выяснить, сколько раз функция HF принемает значение 0, сколько раз 1 и т.д.

Входные данные
Первая строка входного файла hf.in содержит целое число n (0 <= n <= 500) и натуральное число h (h <= 10000), разделенные пробелом. Вторая строка содержит X - последовательность n малых символов латиницы. Никаких других символов во второй строке нет (кроме переноса строки). В 30% входных файлов n <= 100.

Выходной файл
hf.out. Вам необходимо вывести в файл hf.out h чисел. Первым виведите количество подпоследовательностей X, на которых функция HF(X, h) принимает значение 0. Вторым - 1. И т.д.

Пример данных
Код:
hf.in
3 5
bbc

hf.out
0 2 2 1 1
Последним символом в строке не должен быть пробел.
Источник - городская олимпиада по информатике 2006. 1 тур. 11 класс. Автор - Дмитрий Кордубан. Огранчения по времени - 2 сек. Ограничения по памяти - 64 Mb
Ответить с цитированием
  (#2 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 31.01.2006, 21:29

Сразу вставляю свой комментарий. Это была одна из ужаснейших олимпиад т.к. когда я пришел у них не оказалось моего родного компилятора Borland C++ 3.11 [на Visual'е писать нельзя т.к. платный]. Но на прогзе все можно)))

Свое решение не буду пока вывешивать, т.к. там никаких оптимизаций нету. Простое лобовое решение. И сами напишите.
Ответить с цитированием
  (#3 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 11:43

Вот, пока начальство не пришло, набросал решение на Питоне.

Код:
def string2num(str):
    n=0
    l=len(str)
    for i in xrange(l):
        n+=(ord(str[i])-ord('a'))*pow(26,(l-i-1))
    return n

def task(str,h):
    result=[0]*h
    for i in xrange(len(str)):
        for j in xrange(i+1,len(str)+1):
            result[string2num(str[i:j])%h]+=1
    print result

Пример работы.
Код:
>>> task('bbc',5)
[0, 2, 2, 1, 1]
>>> task('abcdadbch',5)
[7, 12, 6, 11, 9]
Решение лобовое.
Сравнивать скорость с С++ вряд ли имеет смысл.


kost не написал, напишу я.
Эта тема возникла как продолжение темы "Самый крутой язык программирования" в форуме "Мысли вслух". К участию приглашаются носители самых разных языков, для сравнения по критериям выразительности, лаконичности, скорости, да мало ли еще чему...
Ответить с цитированием
  (#4 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 01.02.2006, 16:06

gromozeka
Насколько я понял, в твоём решении для каждой подстроки вычисляется соответствующее ей число. А если n=500? Питон посчитает число порядка 26^500? Да и ввод/вывод не соответствуют условиям.

Вот для разнообразия на Паскале (BP7.0):
Код:
PROGRAM HF;

VAR
    n, h,
    i, j, k, r  : integer;
    X           : char;
    Xnum        : array[1..500] of integer;
    remainders  : array[0..9999] of integer;

BEGIN
    assign(input, 'hf.in');
    reset(input);
    assign(output, 'hf.out');
    rewrite(output);

    { Инициализация }
    readln(n, h);
    for i := 1 to n do begin
        read(X);
        Xnum[i] := ord(X) - ord('a');
    end;
    for i := 0 to h-1 do remainders[i] := 0;

    { Главный цикл }
    for i := 1 to n do for j := i to n do begin
        r := 0;
        for k := i to j do r := (r*26 + Xnum[k]) mod h;
        inc(remainders[r]);
    end;

    { Вывод результатов }
    for i := 0 to h-2 do write(remainders[i], ' ');
    write(remainders[h-1]);

    close(input);
    close(output);
END.
Ответить с цитированием
  (#5 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 16:25

Цитата:
Originally posted by michael
[b]Питон посчитает число порядка 26^500?
Вы будет смеяться. Без проблемм.

Код:
>>> pow(26,500)
3066719010709157759218730382894297180963385809296626491827561
8330500334433121813081928284734883100452206007691283755964409
8699334709240527350190646031025837546102152121291975798800960
2513055041910699237259767327525363311928181280934382322467755
8147723581071116471279278470144494966525147639149956361198435
2385924433726442837188664140031524288279657689036013415368557
7419351158650365685710713089108166787472127440623505992236821
9884707274015122953529247797199442783348599329511469463698112
4608899223693456039910061012374251339355346595256165737721775
6769954754745104850657073371736423138718378175379129335541561
4076995780643283564956052205630302751795867328321921167289287
7094792948786349986271953168814309376L
С числами порядка 26^5000 тоже проблемм не возникает, но приводить пример не буду, экрана не хватит.

Тем не менее, признаю что сглупил.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 17:09

случайно 2 раза запостил.
Ответить с цитированием
  (#7 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 17:18

Код:
from string import *
import sys

def string_mod(str,h):
    n=0
    for i in xrange(len(str)):
        n=((n*26)+(ord(str[i])-ord('a')))%h
    return n

def task(str,h):
    result=[0]*h
    for i in xrange(len(str)):
        for j in xrange(i+1,len(str)+1):
            result[string_mod(str[i:j],h)]+=1
    for i in result: print i,

f=open('hf.in','r')
n,h,X=rsplit(f.read())
sys.stdout=open('hf.out', 'w')
task(X,int(h))
sys.stdout.close()
f.close()
Решение исправленное и дополненное.
Ввод-вывод на 100% соответствуют условию.
Поиск остатка оптимизирован.
Ответить с цитированием
  (#8 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 01.02.2006, 17:28

Ну вот. Раскритиковал Питон, а сам в Паскале ошибся.
Совсем забыл, что строки в Паскале максимум 255 символов... Впрочем, исправлять немного: X объявить как char, а не string, а вместо
Код:
    readln(X);
    for i := 1 to n do Xnum[i] := ord(X[i]) - ord('a');
вписать
Код:
    for i := 1 to n do begin
        read(X);
        Xnum[i] := ord(X) - ord('a');
    end;
Добавлено.
Что-то совсем торможу:
Код:
        for k := i to j do begin
            if ((r < hnum[1]) or ((r = hnum[1]) and (Xnum[k] < hnum[2])))
            then r := r*26 + Xnum[k]
            else r := (r*26 + Xnum[k]) mod h;
        end;
эквивалентно
Код:
        for k := i to j do r := (r*26 + Xnum[k]) mod h;
Ответить с цитированием
  (#9 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 17:46

Цитата:
Источник - городская олимпиада по информатике 2006. 1 тур. 11 класс.
Можно поподробнее? 2006 год? она же начнется только 12 февраля... вроде... или ты из ОргКомитета?
Ответить с цитированием
  (#10 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 17:47

Цитата:
Originally posted by michael
[b]Что-то совсем торможу:
Код:
        for k := i to j do begin
            if ((r < hnum[1]) or ((r = hnum[1]) and (Xnum[k] < hnum[2])))
            then r := r*26 + Xnum[k]
            else r := (r*26 + Xnum[k]) mod h;
        end;
эквивалентно
Код:
        for k := i to j do r := (r*26 + Xnum[k]) mod h;
уберите еще хнумы заодно
они теперь не нужны
Ответить с цитированием
  (#11 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 01.02.2006, 17:49

Цитата:
Originally posted by gromozeka
[b]уберите еще хнумы заодно
они теперь не нужны
Ну да, ну да...
Ответить с цитированием
  (#12 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 17:49

ой, ты не из Москвы... тогда понятно... можешь линк дать на сайт олимпиады или задания вывесить ? (можно по личке...)
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 18:03

Цитата:
Originally posted by Talisman
[b]ой, ты не из Москвы... тогда понятно... можешь линк дать на сайт олимпиады или задания вывесить ? (можно по личке...)
От, кляті Маскалі та Паскалі...

Короче, сайт не дам т.к. его нету в природе. Не существует. [иначе б хрен я руки свои напрягал набирать это все]

Задания по-тихоньку вывешу. Вот уже одно есть. Еще два осталось. В это воскресенье будет 2 тур. Там еще три задачки будет. Тесты будут после. На разборе. (там и оптимальные по мнению авторов решения).
Ответить с цитированием
  (#14 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 01.02.2006, 18:54

Я поиграю в Винитарха.

Цитата:
Originally posted by michael
[b]Насколько я понял, в твоём решении для каждой подстроки вычисляется соответствующее ей число. А если n=500?
Если n=500, вполне логично предположить, что h может быть больше 10000. А у Вас это не предусмотренно.

Апдейт:
Извиняюсь, по условию kost не может

Тем не менее. В программе на Питоне, нет обоих этих ограничений.
n и h могут принимать любые значения.
Ответить с цитированием
  (#15 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 01.02.2006, 18:58

В отличии от Винитарха на олимпиадах всегда чётко оговорены условия.
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нужно разобрать программу для перевода списка арабских чисел в список римских чисел. RuslanTM Prolog 2 18.12.2011 17:04
Порядковый номер снова не найден) 6orotblpb Любые вопросы от новичков 9 30.06.2011 15:42
порядковый номер 650 не найден в библиотеке dll iertutil.dll dee Любые вопросы от новичков 32 24.06.2011 12:16
Из множества целых чисел 1..100 выделить множество чисел, являющихся, в свою очере Tormiz61 Pascal 4 18.06.2011 15:07
Найти порядковый номер ого из элементов последовательности... razor052 Pascal 1 27.10.2010 10:43
Функция которая считала среднее значение чисел и количество букв СеРенЯ Lisp 1 12.10.2009 23:38
Минимальный элемент и его порядковый номер OksanaIST Prolog 2 16.12.2007 10:59
Как отключить строку, на которой пишется номер строки и номер символа Audio2005 Delphi 6 11.07.2007 18:42
Miniolimp как настроить написанную программу kost Игры разума 11 02.02.2006 01:27
Серийный номер и номер авторизации WorldWideWeb C++ Builder 1 29.08.2005 14:17
Как определять порядковый номер предыдущей недели Евгения DHTML, JavaScript, VBScript 0 04.07.2005 16:33
Номер колонки и номер строки в QTextEdit krutoj_pablo Trolltech Qt 11 09.02.2005 20:24



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов