Zadania z olimpiad i konkursów informatycznych

0

Co jakiś czas pojawia się tutaj jakiś post z pytaniem o przykładowe zadania z olimpiad, konkursów, meczów itp. imformatycznych czy matematycznych - pomyślałrm więc, że warto by zrobić siakieś jednolite źródło informacji.

Zasada działania tego tematu ma być z założenia taka sama, jak w tym o darmowych serwerach w dziale PHP - kto chce, dopisuje. W formie linku lub samego tekstu zadania. Dopuszczalne jest także umieszczanie poprawnych rozwiązań - coby rozwiązujący mogli porównać efekty swojej pracy.
Co jakiś czas ktoś (ja :)) będzie temat ciut porządkował, żeby bałagan usunąć i zrobić sensowną listę.
Aha, jedna ważna uwaga - nie prosić tutaj o rozwiązania. Jak ktoś już zamieścił, to OK. Jak nie, to można rozwiązać samemu i opublikować dla innych.

PS. Można by nawet zrobić dział na artykuły na 4p, przeznaczony na zadania - co o tym sądzicie?

0

Zadanie praktyczne z etapu wojewódzkiego kuratoryjnego konkursu informatycznego 2004.

Producent okien "Jasna przyszłość" kupił okazyjnie 1000 m uszczelki i chce użyć je do uszczelnienie 250 okien o maxymalnej powierzchni i kształcie

[i tutaj obrazek okna. Prostokąt z walniętym półokręgiem na dachu. Prawy bok prostokąta to y a dolny to x.]
Używając arkusza kalkulacyjnego dobierz wymiary x i y pojedynczego okna. Obliczenia dla zmiennej dokonaj z dokładnoscia do 1cm. Arkusz powinien automatycznie okreslic (wskazac) poszukiwane wymiary x i y podajac komunikat "najwieksza" obok obliczonego maksymalnego pola, przy zmianie danych do zadania powyższy konmunikat może ukazywać się w innym miejscu arkusza

-Narysuj w osobnym arkuszu, stosując odpowiednie narzędzia informatyczne, wykres pola powierzchni okna w zależnosci od x w układzie współrzędnych XOY. opisz wykres (tytuł, os odciętych ==>>nazwa, jednostka rozłożona równomiernie wzdłuż osi oraz oś rzędnych + nazwa , jednostka rozłożona równomiernie wzdłuż osi Y)

PS:

Spójrzmy na ciąg cyfr: 1, 2, 3, 4, 5, 6, 7…
Gdzie ukryła się ósemka? Na pierwszy rzut oka w podanym ciągu ósemki nie ma.
A kiedy przyjrzymy się uważnie jeszcze raz:
1, 2, 3, 4, 5, 6, 7…
cyfry osiem nadal nie dostrzeżemy.
Ciekawostką jest, że sztuczka ta udaje się tylko wtedy, kiedy w ciągu cyfr nie ma ósemki.

0

Mamy takie "równanie":

NINE * THREE = NEUF * TROIS

gdzie za każdą literą ukrywa się inna cyfra. Liczby NINE i TROIS sa podzielne przez 3, a liczby THREE i NEUF sa podzielne przez 9.
Znaleźć liczby THREE i NINE oraz ich iloczyn.

problem bardziej programistyczny niż matematyczny

0

a ja cos takiego mialem na 'Wstep do programowania' ;)
Pani dała wszycho po ang.

PROBLEM A: DERIVATIVE

Input file: standard input

Output file: standard output

Problem

Using the following grammar:

wyrazenie skladnik
<expression> ::= <component> | <component> + <expression>
czynnik
<component> ::= <factor> | <factor> * <component>

<factor> ::= <positive integer="integer"> | <argument> | (<expression>)

<argument> ::= X

write a program which analyses expressions conforming to the rules of this grammar and evaluates their derivatives for a given value of the argument, if the analysis has been successfully completed.

It may be assumed that there is no overflow of float(C)/real(Pascal) numbers range.

Input

Expression given as a character string (max 250). Value of the argument given as an integer number.

Output

Value of the expression or output message ERROR if the expression does not follow the grammar.

Example
X IN OUT
3 32 0
3 12+X 1
3 XX+3 6
3 X
X*X+3 27
3 1(2+3)+3 ERROR
3 qwe323 ERROR


PROBLEM B: PEPTIDES

Input file: standard input

Output file: standard output

Problem

In a laboratory it has been decided to study the peptides with respect to aminoacids which build them. All aminoacids have been assigned one character codes. Thus a sample aminoacids sequence of a peptide may look like this: FFAFTOKA

The aim of the study is to find among obtained peptides those which:

  1. are built with the same aminoacids e.g. FFAFTOKA and OKATFA
  2. are built with the same aminoacids and each aminoacid occur the same number of times in both peptides. The last example does not fulfil this condition because aminoacid F occurs three times in the first peptide and only once in the second one.

Your task is to write a program which searches input data for aminoacids fulfilling conditions a) or b).

Input

Any number of tests, each one ending with symbol 0. First line of test data contains the test name. Consecutive ones contain peptide data: peptide identifier and a symbol ":" followed by aminoacids sequence.

Output

Name of the test and below groups of peptides fulfilling conditions a) or b) (their identifiers). If for two peptides both conditions were fulfilled then their identifiers should be written. If only condition a) were fulfilled then identifier should be followed by symbol "*".

Groups should be listed in the same order as they appeared in input data.

Do not repeat groups what means that the output:

PT2 PT7

and later

PT7 PT2

is wrong.

Assumptions

Number of peptides in single test does not exceed 1000, number of aminoacids in a peptide does not exceed 200.

Example

Input file
test1 test2
PT1:XYXYXYXYXYXIKL
PT2:UJKLCTCTC
PT3:VICDAWR
PT4:KXXXXXXYYYYYLI
PT5:RRWADIVC 0
PT6:XYXYXYXYXYXIKL
PT7:UJKLCTCTC
PT8:VICDAWR
PT9:KXXXXXXYYYYYLI
PT10:RWADIVC
0

Output file
test1 test2
PT1 PT4 PT6 PT9
PT2 PT7
PT3 PT5* PT8 PT10
PT4 PT6 PT9
PT5 PT8* PT10*
PT6 PT9
PT8 PT10


PROBLEM C: 3D-CHESS

Input file: standard input

Output file: standard output

Problem

It is year 2213 and you travel aboard a spacecraft. It was back in XXII century when rapidly developed computers, despite incredibly big number of possible combinations, definitely solved the chess problem. It became possible to predict the result when two good players sat at the opposite sides of the chessboard. Anyway for mankind it was a challenge. On one hand traditional chess game bored people, but on the other hand none wanted to leave aside a game which used to enjoy people for centuries. It raised the need to modify the rules of the game. In 2206 work started on game called 3D-Chess. As it may be easily figured out the chessboard was enhanced to third dimension (can it be still called "board"?). It is unfortunately not yet done and the work still continues on optimal size of the "chess-space" and the set of chessmen. It seems however that it will end up with more familiar size 888, but to stress it once again - it is not yet decided. One of the most keen on the chess players was captain Picard who also worked on optimal set of chessmen. His invention was a "superknight". A superknight slightly resembles its ancestor, but it was also enhanced to 3D space. Thus it can move in one of the following ways:

* two fields forward (in any direction) and one sidewise (all within one plane) - like a "regular" knight.
* two planes upwards or downwards and one sidewise in one of the four possible dimensions
  • teleportation - movement to field which is a mirror reflection of the standpoint with respect to one of the three axes of symmetry of the "chess-space" parallel to its edges.

For superknight it is not relevant whether the fields between the starting field and ending one are occupied or not (again like for the "regular" knight).

It only matters whether the ending field is empty. Then the movement can be performed. There has to be a restriction among so many capabilities of the superknight. It cannot perform the same sort of movements consecutively (just not to fall into routine).

As an example in the table below it is shown what movements are allowed for a superknight standing on the field with coordinates (2, 3, 4). The "chess-space" has size 888 and the numbers of the fields start form (1, 1, 1).

(4, 4, 4) (3, 3, 6) (7, 3, 4)

(4, 2, 4) (1, 3, 6) (2, 6, 4)

(3, 5, 4) (2, 4, 6) (2, 3, 5)

(3, 1, 4) (2, 2, 6)

(1, 5, 4) (3, 3, 2)

(1, 1, 4) (1, 3, 2)

(2, 4, 2)

(2, 2, 2)

Your task is to write a program which could help poor captain Picard in his research. It should calculate the minimal number of movements necessary to get the knight from one field to the given another.

Input

It can contain several sets of data. Each one starts with a line with a number N being size of the "chess-space" (its a cube NNN). Successive two lines contain coordinates of the starting and the ending point. Successive lines contain description of obstacles in the "chess-space". Each obstacle is a rectangular parallelepiped and is described in the following way: first three numbers stand for one vertex coordinates, successive three numbers stand for sizes of its edges. Line containing numbers: 0, 0, 0, 0, 0, 0 ends the obstacle description. It may be assumed that 3 N 16.

Output

For each set of data you should generate one line containing the minimal number of movements. If the solution did not exist then you should output a string "The solution doesn't exist"

Example

Input file

8

1 1 1

2 3 1

0 0 0 0 0 0

8

1 1 1

8 8 8

0 0 0 0 0 0

16

2 3 4

8 8 8

1 1 1 8 1 1

3 5 6 2 2 2

3 4 4 3 3 1

1 1 4 1 2 1

7 6 8 1 1 1

6 7 8 1 1 1

7 8 6 1 1 1

8 7 6 1 1 1

8 8 1 1 1 1

8 1 8 1 1 1

1 8 8 1 1 1

0 0 0 0 0 0

0

Output file

1

5

7

0

Nie wiem czy juz to pisalem, ale zadanie z komisu z ASD, troszke przeze mnie zmodyfikowane.

Mamy tablice n-elementowa. Jej elementami sa kolejne potegi 2. W czasie mniejszym niz liniowy (ze wzgledu na liczbe porownan) znalezc element maksymalny.

Przyklad:
n = 5
tab: 16, 8, 32, 64, 4
Element maksymalny: 64

Podpowiem, ze mi sie udalo to zrobic bez jakiegokolwiek porownania :)
Rozwiazanie:<font color="white"> for(int i=0;i<n;i++) pom |= tab[i]; maks = ((~pom) << 1) & pom</span>

0

Tu jest link do strony Olimpiady Informatycznej. Jest trochę zadań, niektóre nawet ciekawe: :d

http://www.oi.edu.pl/

1 użytkowników online, w tym zalogowanych: 0, gości: 1