Algorytmiczny sukces
(Zam: 12.05.2020 r., godz. 08.59)...Naszą szkołę reprezentowała drużyna w składzie: Natalia Szlom, Marcin Grzymała oraz Szymon Jusiński. Debiut okazał się udany, ponieważ w etapie lokalnym, nasza drużyna zajęła 3. miejsce i awansowała do etapu regionalnego...
Algorytmiczny sukces
W tym roku szkolnym w naszej szkole działa CMI – Centrum Mistrzostwa Informatycznego. Od października członkowie CMI zgłębiali tajniki programowania w języku Python. Po kilku miesiącach wytężonej pracy mieli możliwość zmierzenia się z rówieśnikami ze szkół regionu warszawskiego w zawodach algorytmicznych. Naszą szkołę reprezentowała drużyna w składzie: Natalia Szlom, Marcin Grzymała oraz Szymon Jusiński. Debiut okazał się udany, ponieważ w etapie lokalnym (koła informatyczne z regionu, nad którym sprawuje patronat Politechnika Warszawska), nasza drużyna zajęła 3. miejsce i awansowała do etapu regionalnego, który odbędzie się w formule online 16 maja.
Uczniom należą się zasłużone gratulacje, a dla odwiedzających szkolną stronę internetową publikujemy treści 2 z 7 zadań konkursowych z etapu lokalnego (co najmniej 1 zadanie jest w języku angielskim), aby mogli się przekonać, z jakimi problemami musieli się zmierzyć uczestnicy zawodów.
Tomasz Rurarz – opiekun CMI
Poczekalnia
Przychodnia lekarska w Bajtocji przyjmuje codziennie wielu pacjentów. W poczekalni ważny jest porządek wśród oczekujących, dlatego każdy pacjent zaraz po wejściu otrzymuje numerek i ustawia się na końcu kolejki. Pierwszy pacjent danego dnia otrzyma numer 1, kolejny numer 2, itd. Niektóre przypadki są jednak pilniejsze od innych – stąd wyróżnia się pacjentów zwykłych oraz priorytetowych. Jeżeli doktor prosi o wejście kolejnej osoby, a w kolejce znajdują się jacykolwiek pacjenci priorytetowi, to pacjenci zwykli mają obowiązek ich przepuścić´. Oczywiście w przypadku wielu pacjentów priorytetowych, wchodzi ten z nich, który przyszedł wcześniej.
Znając kolejność zdarzeń , które pewnego dnia miały miejsce w bajtockiej przychodni, ustal, jakie były numery kolejnych pacjentów wchodzących do gabinetu lekarskiego.
Wejście
Pierwszy i jedyny wiersz standardowego wejścia zawiera łańcuch n znaków (n <= 1 000 000), którego znaki odpowiadają kolejnym zdarzeniom, jakie miały miejsce w przychodni. Łańcuch ten składa się wyłącznie z następujących liter:
· 'Z' – pacjent zwykły wchodzi do poczekalni;
· 'P' – pacjent priorytetowy wchodzi do poczekalni;
· 'G' – doktor przyjmuje do gabinetu pacjenta z kolejki.
Istnieje gwarancja, że zawsze, gdy doktor ma przyjąć pacjenta, w kolejce znajduje się przynajmniej jeden pacjent, oraz że wszyscy pacjenci zostaną prędzej czy później przyjęci.
Wyjście
Na standardowe wyjście należy w osobnych wierszach wypisać liczby całkowite oznaczające numery pacjentów w takiej kolejności, w jakiej wchodzili do gabinetu doktora.
Przykład
Dla danych wejściowych:
ZPZGGPZPGGGG
poprawnym wynikiem jest:
2
1
4
6
3
5
Wyjaśnienie do przykładu: W kolejce najpierw ustawiają sie pacjenci o numerach 1, 2, 3, przy czym pacjent 2 posiada priorytet. Gdy doktor zaczyna wpuszczać pacjentów, jako pierwszy wchodzi więc pacjent priorytetowy 2, a później pacjent zwykły 1. Następnie w kolejce ustawiają się pacjenci 4, 5, 6, z których pacjenci 4 i 6 posiadają priorytet. Wchodzą oni zatem do gabinetu lekarskiego jako pierwsi, a potem w kolejce nie znajduje się już żaden pacjent priorytetowy, więc pacjenci zwykli mogą kolejno odbyć´ swoje wizyty.
Bridge Club
Bridge is a card game played by four players sitting around a table. The four players are divided into two competing teams. Pupils of the 0th Secondary School in Byteland decided to organize a bridge club and meet together in one of the classrooms to play the game.
The whole idea is supported by a teacher, Mr. Byteslaw, who wants to make sure the participants have a good time. For this purpose, he first evaluated the skill level of every pupil. Then, he decided that the skill level of a two-person team should be defined as the lower of the skill levels of these two persons. Now he wants to assign the pupils to teams and the teams to tables, in such a way, that the skill levels of both teams sitting at the same table are equal, for as many tables as possible. The problem is that Mr. Byteslaw is a history teacher and he has no idea how best to do it. Help him and create a program which will calculate how many such fair tables can be created.
Input
The first line of standard input contains one natural number n, denoting the number of bridge club members (4 <= n <= 100 000). In the second line there is a sequence of n natural numbers z1; z2; …; zn (1 <= zi <= 1 000 000 000) separated by single spaces. They denote the skill levels of the bridge club members.
Output
A single integer, equal to the largest number of fair tables that may be formed, should be printed to standard output.
Example
For input data:
9
1 3 3 1 9 10 1 9 4
the correct result is:
2
Explanation of the example: There are many ways in which two fair tables may be formed here. For example, we can create teams: (1; 1); (1; 9); (3; 4); (3; 10). Then we have one pair of teams with skill level 1 and another pair of teams with skill level 3.
W tym roku szkolnym w naszej szkole działa CMI – Centrum Mistrzostwa Informatycznego. Od października członkowie CMI zgłębiali tajniki programowania w języku Python. Po kilku miesiącach wytężonej pracy mieli możliwość zmierzenia się z rówieśnikami ze szkół regionu warszawskiego w zawodach algorytmicznych. Naszą szkołę reprezentowała drużyna w składzie: Natalia Szlom, Marcin Grzymała oraz Szymon Jusiński. Debiut okazał się udany, ponieważ w etapie lokalnym (koła informatyczne z regionu, nad którym sprawuje patronat Politechnika Warszawska), nasza drużyna zajęła 3. miejsce i awansowała do etapu regionalnego, który odbędzie się w formule online 16 maja.
Uczniom należą się zasłużone gratulacje, a dla odwiedzających szkolną stronę internetową publikujemy treści 2 z 7 zadań konkursowych z etapu lokalnego (co najmniej 1 zadanie jest w języku angielskim), aby mogli się przekonać, z jakimi problemami musieli się zmierzyć uczestnicy zawodów.
Tomasz Rurarz – opiekun CMI
Poczekalnia
Przychodnia lekarska w Bajtocji przyjmuje codziennie wielu pacjentów. W poczekalni ważny jest porządek wśród oczekujących, dlatego każdy pacjent zaraz po wejściu otrzymuje numerek i ustawia się na końcu kolejki. Pierwszy pacjent danego dnia otrzyma numer 1, kolejny numer 2, itd. Niektóre przypadki są jednak pilniejsze od innych – stąd wyróżnia się pacjentów zwykłych oraz priorytetowych. Jeżeli doktor prosi o wejście kolejnej osoby, a w kolejce znajdują się jacykolwiek pacjenci priorytetowi, to pacjenci zwykli mają obowiązek ich przepuścić´. Oczywiście w przypadku wielu pacjentów priorytetowych, wchodzi ten z nich, który przyszedł wcześniej.
Znając kolejność zdarzeń , które pewnego dnia miały miejsce w bajtockiej przychodni, ustal, jakie były numery kolejnych pacjentów wchodzących do gabinetu lekarskiego.
Wejście
Pierwszy i jedyny wiersz standardowego wejścia zawiera łańcuch n znaków (n <= 1 000 000), którego znaki odpowiadają kolejnym zdarzeniom, jakie miały miejsce w przychodni. Łańcuch ten składa się wyłącznie z następujących liter:
· 'Z' – pacjent zwykły wchodzi do poczekalni;
· 'P' – pacjent priorytetowy wchodzi do poczekalni;
· 'G' – doktor przyjmuje do gabinetu pacjenta z kolejki.
Istnieje gwarancja, że zawsze, gdy doktor ma przyjąć pacjenta, w kolejce znajduje się przynajmniej jeden pacjent, oraz że wszyscy pacjenci zostaną prędzej czy później przyjęci.
Wyjście
Na standardowe wyjście należy w osobnych wierszach wypisać liczby całkowite oznaczające numery pacjentów w takiej kolejności, w jakiej wchodzili do gabinetu doktora.
Przykład
Dla danych wejściowych:
ZPZGGPZPGGGG
poprawnym wynikiem jest:
2
1
4
6
3
5
Wyjaśnienie do przykładu: W kolejce najpierw ustawiają sie pacjenci o numerach 1, 2, 3, przy czym pacjent 2 posiada priorytet. Gdy doktor zaczyna wpuszczać pacjentów, jako pierwszy wchodzi więc pacjent priorytetowy 2, a później pacjent zwykły 1. Następnie w kolejce ustawiają się pacjenci 4, 5, 6, z których pacjenci 4 i 6 posiadają priorytet. Wchodzą oni zatem do gabinetu lekarskiego jako pierwsi, a potem w kolejce nie znajduje się już żaden pacjent priorytetowy, więc pacjenci zwykli mogą kolejno odbyć´ swoje wizyty.
Bridge Club
Bridge is a card game played by four players sitting around a table. The four players are divided into two competing teams. Pupils of the 0th Secondary School in Byteland decided to organize a bridge club and meet together in one of the classrooms to play the game.
The whole idea is supported by a teacher, Mr. Byteslaw, who wants to make sure the participants have a good time. For this purpose, he first evaluated the skill level of every pupil. Then, he decided that the skill level of a two-person team should be defined as the lower of the skill levels of these two persons. Now he wants to assign the pupils to teams and the teams to tables, in such a way, that the skill levels of both teams sitting at the same table are equal, for as many tables as possible. The problem is that Mr. Byteslaw is a history teacher and he has no idea how best to do it. Help him and create a program which will calculate how many such fair tables can be created.
Input
The first line of standard input contains one natural number n, denoting the number of bridge club members (4 <= n <= 100 000). In the second line there is a sequence of n natural numbers z1; z2; …; zn (1 <= zi <= 1 000 000 000) separated by single spaces. They denote the skill levels of the bridge club members.
Output
A single integer, equal to the largest number of fair tables that may be formed, should be printed to standard output.
Example
For input data:
9
1 3 3 1 9 10 1 9 4
the correct result is:
2
Explanation of the example: There are many ways in which two fair tables may be formed here. For example, we can create teams: (1; 1); (1; 9); (3; 4); (3; 10). Then we have one pair of teams with skill level 1 and another pair of teams with skill level 3.