Courses

algoritmalar

karma

Module: karma

Problem

7 /8

kültürel temas

Theory Click to read/hide

Sekanslara ek olarak, kümeleri de karma yapabilirsiniz. Yani, üzerinde herhangi bir düzen olmayan nesne kümeleri. Aşağıdaki formüle göre hesaplanır:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\) <- her şeyi sayma modulo
burada ord, kümenin bir nesnesine tüm olası nesneler arasında mutlak sıra sayısını atayan bir işlevdir (örneğin, nesneler doğal sayılarsa, o zaman ord(x) = x ve küçük Latin harfleri ise o zaman ord(& #39;a') = 1, sıra('b') = 2 vb.)

Yani, her nesne için, bu nesnenin sayısının gücüne tabana eşit bir değer ilişkilendiririz ve tüm kümenin bir karmasını elde etmek için tüm bu değerleri toplarız. Formülden de anlaşılacağı gibi, kümeye bir öğe eklenirse veya kümeden çıkarılırsa (sadece gerekli değeri ekleyin veya çıkarın) hash kolayca yeniden hesaplanır. Aynı mantık, tek öğeler eklenmez veya kaldırılmazsa, ancak diğer kümeler eklenirse (sadece hashlerini ekleyin / çıkarın).

Zaten anlayabileceğiniz gibi, tek öğeler, hash'i hesaplayabileceğimiz 1 boyutlu kümeler olarak kabul edilir. Ve daha büyük kümeler, bu tür tekli kümelerin bir birleşimidir; burada kümeleri birleştirerek hashlerini ekleriz.

Aslında, bu hala aynı polinom hash'idir, ancak p^m 'deki katsayıdan önce şu değere sahibiz: dizi elemanının n - m - 1 (burada n, dizinin uzunluğudur) ve şimdi bu, kümedeki mutlak sıra numarası m'ye eşit olan öğelerin sayısıdır.

Bu tür karmada, kişi yeterince büyük bir taban almalı (maksimum küme boyutundan daha büyük) veya mutlak sıra numarası m olan bir p nesnesi kümesinin, mutlak sıra numarası olan bir nesneli bir kümeyle aynı karma değerine sahip olduğu durumlardan kaçınmak için çift karma kullanmalıdır. sıra numarası m+1.

Problem

18. yüzyılın başında, bir grup Avrupalı kaşif, Avrupa medeniyetinin temsilcileriyle hiçbir zaman temas kurmamış bir grup kabilenin yaşadığı bir adaya geldi.

Yerlilerle başarılı bir şekilde iletişim kurmak için grubun lideri tanıştığı her kabilenin liderine bir hediye vermeyi planlıyor. Bu amaçla değerli taşlara benzeyen uzun bir cam zincir getirmiş.
Dizeyi, İngiliz alfabesinin küçük harflerinden oluşan ve her harfin karşılık gelen konumdaki cam parçasının türünü ifade ettiği bir s dizisi olarak gösterelim.
Araştırmacılar zinciri bazı parçalara ayıracaklar ve ardından grubun karşılaştığı her kabilenin liderine tam olarak bir parça teslim edecekler. Araştırma lideri, zinciri aşağıdaki kurallara göre parçalara ayırmaya karar verdi:

Kesmeye fazla zaman harcamamak için, her parça zincirdeki bitişik cam parçalarından oluşan bir grup, yani s dizisinin bir alt dizisi olmalıdır.
Tüm cam parçaları kullanılmalıdır, yani her bir cam parçası tam olarak tek bir parçaya dahil edilmelidir.
Araştırmacılar yerlilerin belirli cam türlerine nasıl değer vereceklerini bilmedikleri için, sıra gözetmeksizin her şefin aynı cam setini almasını istiyorlar. Diğer bir deyişle, herhangi bir cam türü için, bu türdeki camların sayısı her bir parçada aynı olmalıdır.
Araştırmacılar adada kaç kabilenin yaşadığını bilmediğinden, hazırlanan parçaların sayısı mümkün olduğunca fazla olmalıdır.

Yöneticinin elde edilebilecek maksimum parça sayısını belirlemesine yardımcı olun.

Giriş:
İlk satır s (1 <= |s| <= 5000000) dizesini içerir.

Çıktı:
Tek bir sayı yazdırın - araştırmacıların, grup lideri tarafından formüle edilen koşulların hiçbirini ihlal etmeden sahip oldukları zinciri kesebilecekleri mümkün olan maksimum sayıda parça.

Örnekler:

Açıklamalar:
İlk örnekte, araştırmacılar 'abbabbbab' 'abb', 'abb', 'bab' parçaları, ardından karşılaştıkları her kabilenin lideri bir bardak 'a' ve iki adet 'b'.

İkinci örnekte, dizi, tüm koşullar gözetilerek zincirin birden fazla parçasına bölünemez.

time 1000 ms
memory 128 Mb
Rules for program design and list of errors in automatic problem checking