Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Usaco: contact problem

[es] :: Art of Programming :: Usaco: contact problem

[ Pregleda: 3200 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

D3adly

Član broj: 43272
Poruke: 35
*.cmu.carnet.hr.

ICQ: 281458481


Profil

icon Usaco: contact problem26.08.2005. u 15:07 - pre 225 meseci
Svaka pomoć bi mi dobro došla! To mi je zadnji zadatak iz Section 2.1. Svako rjesenje koje sam pokušao daje mi TLE.
Evo zadatka:

Citat:

The cows have developed a new interest in scanning the universe outside their farm with radiotelescopes. Recently, they noticed a very curious microwave pulsing emission sent right from the centre of the galaxy. They wish to know if the emission is transmitted by some extraterrestrial form of intelligent life or if it is nothing but the usual heartbeat of the stars.

Help the cows to find the Truth by providing a tool to analyze bit patterns in the files they record. They are seeking bit patterns of length A through B inclusive (1 <= A <= B <= 12) that repeat themselves most often in each day's data file. They are looking for the patterns that repeat themselves most often. An input limit tells how many of the most frequent patterns to output.

Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.

PROGRAM NAME: contact
INPUT FORMAT
Line 1: Three space-separated integers: A, B, N; (1 <= N < 50)
Lines 2 and beyond: A sequence of as many as 200,000 characters, all 0 or 1; the characters are presented 80 per line, except potentially the last line.

SAMPLE INPUT (file contact.in)
2 4 10
01010010010001000111101100001010011001111000010010011110010000000


In this example, pattern 100 occurs 12 times, and pattern 1000 occurs 5 times. The most frequent pattern is 00, with 23 occurrences.

OUTPUT FORMAT
Lines that list the N highest frequencies (in descending order of frequency) along with the patterns that occur in those frequencies. Order those patterns by shortest-to-longest and increasing binary number for those of the same frequency. If fewer than N highest frequencies are available, print only those that are.

Print the frequency alone by itself on a line. Then print the actual patterns space separated, six to a line (unless fewer than six remain).

SAMPLE OUTPUT (file contact.out)
23
00
15
01 10

12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100





#include <D3adly.h>
 
Odgovor na temu

stf

Član broj: 51276
Poruke: 65
62.108.101.*



Profil

icon Re: Usaco: contact problem26.08.2005. u 15:25 - pre 225 meseci
Ucitas niz tih znakova u niz. Zatim redom krenes od prvog do posledenjeg znaka i redom u matricu m(a,b) smestas binarni broj (to je zapravo decimalni broj b) duzine a znakova. Dakle u ciklusu i treba ti jos jedan ciklus j koji ide od 1 do 12, cime generises sve moguce duzine frenkvencija koje pocinju znakom na kome se trenutno nalazi brojac i. Vrednost matrice predstavlja ustvari broj pojavljivanja određene frenkvencije (binarnog broja). Za ovaj zadatak ti treba funckcija koja binarni broj prebacuje u decimalni i funkcija koja vrši obrnut proces (zbog ispisivanja u binarnom obliku).
If you don't live for something, you will die for nothing.
 
Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
*.sbb.co.yu.



Profil

icon Re: Usaco: contact problem26.08.2005. u 15:41 - pre 225 meseci
Pored navedenog resenja, mozes jos i svaki bit da povecas za jedan, pa da paterne stavljas u niz pod indeksom koji izracunas tako sto patern posmatras kao broj u sistemu sa osnovom 3. Ili mozes i da dodas 1 ispred celog paterna i izracunas vrednost u sistemu sa osnovom 2.
Don’t do drugs, sleep deprivation is better.
 
Odgovor na temu

[es] :: Art of Programming :: Usaco: contact problem

[ Pregleda: 3200 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.