Ολυμπιάδα Πληροφορικής


Tasks [Balkan Olympiad in Informatics 2016]

Day 1

Day 2

Advertisements

Blackgate Penitentiary

Vangelis the Batbear trapped all the members of Joker’s Streetgang in a basement.
Your job as a police officer is to transport all gang members to Blackgate Penitentiary.

To facilitate the transport, you should form a row such that the heights of the gang members are in non-decreasing order. For each gang member you should find the min and the max position where they can be in a valid sorted row and produce a roster with this information.

Input data

Input will start with a line that contains only one integer M, the number of crew members that were arrested. On each of the following M lines there will be a single word N and an integer H separated by a space character, where N is the name and H is the height of the crew member.

Output data

On the output, there will be G lines. Each line will contain in alphabetical order and space separated the names of the crew members that have the same height, followed by the min and the max position where any member of the specific group can be placed.

Limitations and notes

1 ≤ M ≤ 1000
1 ≤ length(N) ≤ 10
120 ≤ H ≤ 250

Names are only composed of characters of the Latin alphabet.


Ο άντρας-νυχτερίδα και η πρόκληση των φυσαλίδων

Καλησπέρα αφέντη Wayne.

Ο Joker και η συμμορία του πήγαν στο Black Hat USA 2017 όπου και έμαθαν τρόπο νέο να κάνουν ζημιά στη πόλη μας!
Συγκεκριμένα, αύριο βράδυ θα προσπαθήσουν να κάνουν ζημιά στις αντλίες νερού της Gotham με τη χρήση φυσαλίδων!
Οι φυσαλίδες προκαλούν διάβρωση στις αντλίες και μέσα σε μερικές ώρες θα τους κάνουν ζημιά με καταστροφικά αποτελέσματα!
Για να καταστρέψετε το σχέδιο του Joker, πρέπει να εκτός από το να τον σταματήσετε, να βεβαιωθείτε ότι το δίκτυο της πόλης δεν περιέχει κύκλους.
Αν προλάβει ο Joker να βάλει φυσαλίδες στο δίκτυο και μπουν σε κύκλο, θα κάνουν ζημιά σε εκείνη τη περιοχή παρόλο που θα έχετε ήδη συλλάβει τον Joker και την συμμορία του.

Δεδομένου του χάρτη με το σύστημα διανομής νερού, πρέπει να βεβαιωθείτε ότι ο χάρτης δεν έχει κύκλους.

Δεδομένα εισόδου

Στην πρώτη γραμμή υπάρχει ένας ακέραιος T, ο αριθμός των test cases που θα ακολουθήσουν.
Για κάθε test case, υπάρχουν 2 γραμμές εισόδου:

  1. Στην πρώτη γραμμή του test case, υπάρχουν 2 ακέραιοι V και E, όπου V είναι ο αριθμός των κορυφών (vertices) και E είναι ο αριθμός των ακμών (edges).
  2. Στη δεύτερη γραμμή, υπάρχουν E ζεύγη ακέραιων χωρισμένα με το κενό. Κάθε ζεύγος δείχνει τη διπλή κατεύθυνσης σύνδεση της κορυφής A με την κορυφή B.

Δεδομένα εξόδου

Για κάθε test case θα πρέπει να γράψετε μια γραμμή με ένα ακέραιο, στην περίπτωση που υπάρχει κύκλος θα γράψετε τον αριθμό 1 αλλιώς θα γράψετε τον αριθμό 0.

Περιορισμοί

1 ≤ T ≤ 1000
1 ≤ V ≤ 1000
1 ≤ E ≤ 10000
0 ≤ A,B ≤ V-1

Ο Βαγγέλης ο αρκούδος είναι ο άντρας-νυχτερίδα! (ή ο αρκούδος-νυχτερίδα για να είμαστε πιο σωστοί)

Ο Βαγγέλης ο αρκούδος είναι ο άντρας-νυχτερίδα! (ή ο αρκούδος-νυχτερίδα για να είμαστε πιο σωστοί)

Υλικό ανάγνωσης

Βοηθητικό υλικό


Κυπριακή Ολυμπιάδα Πληροφορικής – Επίσημο Λογότυπο Logo

cyprus-informatics-olympiad-logo

Είμαστε στην ευχάριστη θέση να ανακοινώσουμε ότι η επιτροπή της Κυπριακής Ολυμπιάδα Πληροφορικής έχει  αποφασίσει το λογότυπο που θα χρησιμοποιηθεί για την ομάδα!

Το λογότυπο απεικονίζει έναν πιγκουίνο ντυμένος ως Κύπριος Οπλίτης.

Θέλουμε να ευχαριστήσουμε τον Μιλτιάδη (Μίλτος) Κωνσταντίνου για το όμορφο έργο του http://cargocollective.com/Miltos.


Installing Task Translation System for IOI competitions (Linguist) on Ubuntu Server 14.04LTS

First, install any missing (also for font) related dependencies:

sudo apt-get update;
sudo apt-get install git unzip build-essential chrpath libssl-dev libxft-dev libfreetype6 libfreetype6-dev libfontconfig1 libfontconfig1-dev fontconfig fontconfig-config fonts-dejavu-core fonts-droid fonts-freefont-ttf fonts-kacst fonts-kacst-one fonts-khmeros-core fonts-lao fonts-liberation fonts-lklug-sinhala fonts-nanum fonts-opensymbol fonts-sil-abyssinica fonts-sil-padauk fonts-takao-pgothic fonts-thai-tlwg fonts-tibetan-machine fonts-tlwg-garuda fonts-tlwg-kinnari fonts-tlwg-loma fonts-tlwg-mono fonts-tlwg-norasi fonts-tlwg-purisa fonts-tlwg-sawasdee fonts-tlwg-typewriter fonts-tlwg-typist fonts-tlwg-typo fonts-tlwg-umpush fonts-tlwg-waree -y;

Then, get a copy of the repository:

git clone https://github.com/ioi/translation.git

Switch to the newly created directory:

cd translation/

And, add the gpg keys needed to make the setup.
The gpg command in the setup will contact a public key server (hkp://keys.gnupg.net) and request the key associated with the RVM project key which is used to sign each RVM release. To get the key, we need to provide the ID that is related to the key, in this case the ID is 409B6B1796C275462A1703113804BB82D39DC0E3. Having the RVM project’s public key allows us to verify the legitimacy of the RVM release we will be downloading, which is signed with the matching private key.

gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3

If the above command fails with the following error

$ gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3
gpg: requesting key D39DC0E3 from hkp server keys.gnupg.net
?: [fd 4]: read error: Connection reset by peer
gpgkeys: HTTP fetch error 7: couldn't connect: eof
gpg: no valid OpenPGP data found.
gpg: Total number processed: 0

Try using the following alternative:

command curl -sSL https://rvm.io/mpapis.asc | gpg --import -

Afterwards, perform the installation (this might take some time, depending on your connection to the server where it will download the necessary packages and your CPU performance as it will perform some compilation locally):

./deploy.sh

While installing codemirror we got the following prompt:

replace public/codemirror-3.22/doc/upgrade_v3.html? [y]es, [n]o, [A]ll, [N]one, [r]ename:

We typed A and pressed Enter. We are not sure if this is what we are supposed to do but it worked later on properly.

Edit the ./config.yml file and set new values for the api_token and cookie_secret.

api_token: "4c0a6fe55f3d4aa9c5dbb9a59db7b20e"
cookie_secret: "SDfadadsf90u84oh23jnrwf"
  • api_token is a 32 characters long random key. It can contain only character a-f and numbers 0-9.
  • cookie_secret is a 23 characters long value. This example contains any character from a-z and A-Z and the numbers 0-9.

You can generate random passwords from here http://bytefreaks.net/random-password-generator

Then start the redis service using the following:

redis-server

 

In an new terminal, go to DbInit folder:

cd translation/DbInit/

and update the files users.json and tasks.json to prepare the initial data to be imported in redis:

  • users.json Be sure to update the passwords of the users.
  • tasks.json Set the names of your tasks and the .md filenames of the original content.

The original content of tasks.json is:

[
    { "id": "1",    "title": "notice",     "filename": "notice.md" },
    { "id": "2",    "title": "gondola",    "filename": "gondola.md" },
    { "id": "3",    "title": "friends",    "filename": "friends.md" },
    { "id": "4",    "title": "holiday",    "filename": "holiday.md" }
]

Place the original .md files in this folder. And then initialize redis using the following command:

ruby dbinit.rb

Finally, go to the previous folder and start the translation system:

cd ..;
shotgun -o 0.0.0.0 -p 8080;

Visit http://SERVER_NAME_OR_IP:8080 to view the translation system.

You can use the admin account to make changes to users, to send notifications (if you omit the to field, then the notification will be send to all users) and to check out all task with their translations.

Staff accounts allow you to check out all task with their translations.

Note on the architecture

The deploy.sh script assumes your architecture and OS is 64bit. To find what type of architecture you are using execute uname -i. If the result is not x86_64, then phantomjs will not work for you and you will not be able to generate the PDFs. To fix this issue you need to download the correct version from https://bitbucket.org/ariya/phantomjs/downloads. At the time this tutorial was written deploy.sh was installing version https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-x86_64.tar.bz2, so we installed https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-i686.tar.bz2 using the following commands:

wget https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-i686.tar.bz2;
tar xf phantomjs-1.9.7-linux-i686.tar.bz2;
sudo cp phantomjs-1.9.7-linux-i686/bin/phantomjs /usr/local/bin;
rm -rf phantomjs-1.9.7-linux-i686*;

The above commands follow the example in deploy.sh.

Updating logos and website look

To update the views of the website you can do the by editing the .erb files that are in the translation/views folder.

Examples:

  • login.erb You need to modify this file to change the login screen
  • tasks_index.erb This file holds the structure of the main index the user sees after login (/tasks)
  • _navbar.erb Modify this file to change the navigation bar on top of each page
  • .. and more