PilsProg 2019

Výsledky Lite

Splněných úlohPočet soutěžících
91
72
31

Pozn.: Jména a příjmení soutěžících byla odstraněna, protože pominul účel zpracování osobních údajů.

Cena udělená za 1. místo v PilsProg Lite: Externí 1TB 2.5" HDD

Výsledky kvalifikace

Splněných úlohPočet soutěžících
61
53
47
31
26
11

Pozn.: Jména a příjmení soutěžících byla odstraněna, protože pominul účel zpracování osobních údajů.

Výsledky finále

Splněných úlohPočet finalistů
51
33
26
02

Pozn.: Jména a příjmení finalistů byla odstraněna, protože pominul účel zpracování osobních údajů.

Ilustrační úlohy

NázevČísloÚspěšných řešitelů
AxB170110
AplusB17027
Největší ze tří celých čísel17037
Pascalův trojúhelník17046

Lite1 úlohy

NázevČísloÚspěšných řešitelů
Fibonacciho řada19114
Pod diagonálou19124
Trojúhelník19134

Lite2 úlohy

NázevČísloÚspěšných řešitelů
Česká vlajka19142
Jednotková matice19153
Kvadratická rovnice19162

Lite3 úlohy

NázevČísloÚspěšných řešitelů
Dělitele čísla19173
Medián19182
Spirála19192

Kvalifikační úlohy

NázevČísloÚspěšných řešitelů
Jezdec192112
Kolize19225
Obdélníky19232
Ping pong192411
Programátoři192518
Radioamatér192617

Finálové úlohy

NázevČísloÚspěšných řešitelů
Evakuace19314
ISBN193210
Přístupové karty19331
Lišák19341
Sirky193510

A jaké bylo finále?

Finále začíná ...

Harmonogram PilsProg 2019

Lite úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Jak úlohy řešili soutěžící, je ukázáno na vybraných příkladech zdrojových kódů odevzdaných soutěžních úloh.

Fibonacciho řada

  1. Pokud je n rovno 0, vypsat „0“. Pokud je n rovno 1, vypsat „0, 1“
  2. Pro větší n si připravit proměnnou pro předpředchozí a předchozí člen řady a inicializovat je hodnotami 0 a 1.
  3. Použít cyklus for opakující se v intervalu <2; n>.
  4. V každé obrátce cyklu vypočítat aktuální člen jako součet předpředchozího a předchozího a vypsat ho.
  5. Do předpředchozího členu přiřadit předchozí a do předchozího aktuální.

Příklad zdrojového kódu:

import java.util.Scanner; public class FibRada{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int nums = sc.nextInt() + 1; long f_2 = 0; long result = 0; for (int n = 0; n < nums; n++) { long tmp = result; result = result + f_2; f_2 = tmp; if (n == 1) { result = 1; } if (n + 1 != nums) System.out.print(result + ", "); else System.out.print(result); } System.out.println(" "); } }

Pod diagonálou

  1. Pro zadaný řád matice (n) načíst jednotlivé řádky matice po jednotlivých číslech a uložit je do dvourozměrného pole.
  2. Připravit si proměnnou pro součet prvků a použít dva vnořené cykly for pro procházení matice. Vnější cyklus určuje aktuální řádku matice. Vnitřní cyklus for určuje aktuální prvek na řádce (tj. sloupec).
  3. Vnější cyklus se opakuje v intervalu <1; n).
  4. Vnitřní cyklus se opakuje podle aktuální řádky - pro řádku 1 jen jednou, pro řádku 2 dvakrát, atd.
  5. V každé obrátce vnitřního cyklu se aktuální prvek přičte do celkového součtu.
  6. Vypsat součet.

Příklad zdrojového kódu:

#include <iostream> int main(){ int n; std::cin >> n; long long sum = 0; int num = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ std::cin >> num; if(i-j>0) sum += num; } } std::cout << sum; return 0; }

Trojúhelník

  1. Pro každý testovací případ načíst délky všech tří stran.
  2. Vzájemně porovnat jednotlivé strany.
  3. Pokud pro všechny kombinace stran platí, že součet dvou stran je větší než strana zbývající, trojúhleník lze sestrojit, vypsat „Lze.“. Jinak vypsat „Nelze.“.

Příklad zdrojového kódu:

//#include "stdafx.h" #include <iostream> using namespace std; int main() { int n = 0; cin >> n; float x = 0, y = 0, z = 0 ; bool status; for (size_t i = 0; i < n; i++) { cin >> x >> y >> z; status = true; if (x+y <= z) { status = false; } if (x+z <= y) { status = false; } if (z+y <= x) { status = false; } if (!status) { cout << "Nelze." << endl; } if (status) { cout << "Lze." << endl; } } return 0; }

Česká vlajka

  1. Pro zadaný počet řádek vlajky si vypočítat počet sloupců.
  2. Vlajku vykreslit po řádkách. Každý „pixel“ je tvořen dvěma znaky. Přírůstek modré je 1.5 pixelu na řádku, tedy 3 znaky na řádku.
  3. Vykreslení provést ve dvou po sobě jdoucích for cyklech.
  4. První for cyklus vykreslí modrobílou polovinu vlajky po řádách a v rámci řádky po jednotlivých znacích. Část řádky je modrá (tj. znaky „M“) a část je bílá (tj. znaky „.“). Na první řádce jsou 3 znaky modré, zbytek je bílý. Na druhé řádce je 6 znaků modrých, atd. Po každé řádce odřádkovat.
  5. Druhý for cyklus vykreslí modročervernou polovinu vlajky po řádách a v rámci řádky po jednotlivých znacích. Část řádky je modrá (tj. znaky „M“) a část je červená (tj. znaky „C“). Na první řádce je polovina znaků modrých, zbytek je červený. Na druhé řádce je o 3 modré znaky méně atd. Po každé řádce odřádkovat.

Příklad zdrojového kódu:

import java.util.Scanner; public class CeskaVlajka { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int rows = sc.nextInt(); int width = rows * 3; int mStep = width / 2 /(rows / 2); for (int x = 0; x < rows / 2; x++) { for (int a =0; a < mStep * (x + 1); a++) System.out.print("M"); for (int a =0; a < width - mStep * (x + 1); a++) System.out.print("."); System.out.println(); } for (int x = rows / 2; x > 0; x--) { for (int a =0; a < mStep * (x); a++) System.out.print("M"); for (int a =0; a < width - mStep * (x); a++) System.out.print("C"); System.out.println(); } } }

Jednotková matice

  1. Pro zadaný řád matice n vypsat jednotkovou matici pomocí dvou vnořených cyklů for opakujících se v intervalu <0; n).
  2. Ve vnitřním cyklu vypisovat čísla 0 oddělená mezerou bez odřádkování, pokud je aktuální sloupec různý od aktuální řádky. V opačném případě vypsat 1.
  3. Ve vnějším cyklu po skončení vnitřního cyklu odřádkovat.

Příklad zdrojového kódu:

package pilspro; import java.util.*; public class jednotkovaMatice { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int r = sc.nextInt(); for (int y = 0; y < r; y++) { for (int x = 0; x < r; x++) { if (x == y) System.out.print(1); else System.out.print(0); if (x != r-1) System.out.print(" "); } System.out.println(); } } }

Kvadratická rovnice

  1. Pro každou rovnici načíst koeficienty a, b a c.
  2. Vypočítat diskriminant.
  3. Podle velikosti diskriminantu určit, zda má rovnice 2, 1 či 0 reálných kořenů. Protože se počítá s reálnými čísly, je potřeba pro porovnání použít zvolenou toleranci (např. 1 milióntina - kvůli zaokrouhlovacím chybám nemusí vypočítaná hodnota diskriminantu přesně odpovídat teoretické hodnotě).
  4. Vypočítat příslušná řešení rovnice podle postupu pro výpočet kořenů kvadratické rovnice a vypsat je, pokud nějaká jsou. Pokud rovnice nemá reálné řešení, vypsat „Nema reseni“.

Příklad zdrojového kódu:

import java.util.Scanner; import java.text.DecimalFormat; import java.text.DecimalFormatSymbols; public class KvadrRovnice { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int exercises = sc.nextInt(); String[] results = new String[exercises]; sc.nextLine(); DecimalFormatSymbols sym = new DecimalFormatSymbols(); sym.setDecimalSeparator('.'); DecimalFormat f = new DecimalFormat("0.00", sym); for (int x = 0; x < exercises; x++) { String[] splits = sc.nextLine().split(" "); double a = Double.parseDouble(splits[0]); double b = Double.parseDouble(splits[1]); double c = Double.parseDouble(splits[2]); double dis = Math.pow(b, 2) - (4*a*c); if (dis < 0) { results[x] = "Nema reseni"; continue; } else if (dis == 0) { results[x] = "Ma 1 koren: " + f.format(-b / (2*a)); continue; } else { double kor1 = (-b - Math.sqrt(dis))/(2*a); double kor2 = (-b + Math.sqrt(dis))/(2*a); if (kor1 < kor2) results[x] = "Ma 2 koreny: " + f.format(kor1) + " a " + f.format(kor2); else results[x] = "Ma 2 koreny: " + f.format(kor2) + " a " + f.format(kor1); continue; } } for (int x = 0; x < exercises; x++) { System.out.println(results[x]); } } }

Dělitele čísla

  1. Pro každé načtené číslo c vypsat 1.
  2. Pro čísla větší než 1 si připravit proměnnou pro počet dělitelů a inicializovat ji na 2.
  3. Pro výpis dělitelů čísla větších než 1 a menších než číslo samotné použít cyklus for opakující se v intervalu <2; c / 2>.
  4. Pro všechna čísla v tomto intervalu vyzkoušet, zda dělí číslo c. Pokud ano, aktuální dělitel vypsat a inkrementovat počet dělitelů.
  5. Vypsat číslo c (každé číslo dělí sebe sama).
  6. Pokud je počet dělitelů roven 2, vypsat text „ (prvocislo)“.
  7. Odřádkovat.

Příklad zdrojového kódu:

#include <iostream> #include <vector> using namespace std; std::vector<int64_t> numbers; int main() { int counter; int number; int prime_counter; cin >> counter; for (size_t i = 0; i < counter; i++) { prime_counter = 0; cin >> number; cout << "1"; for (size_t modulo = 2; modulo <= number; modulo++) { if (number%modulo==0) { prime_counter++; cout << ", "<< modulo ; } } if (prime_counter == 1) { cout << " (prvocislo)"; } cout << endl; } return 0; }

Medián

  1. Pro každou řadu načíst všechny její prvky do pole.
  2. Seřadit prvky podle velikosti (vzestupně či sestupně).
  3. Pokud je počet prvků řady lichý, vypsat prostřední prvek jako reálné číslo na jedno desetinné místo.
  4. Pokud je počet prvků řady sudý, vzít dva prostřední prvky, spočítat jejich aritmetický průměr a vypsat ho jako reálné číslo na 1 desetinné místo.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> #include <iostream> #include <iomanip> using namespace std; std::vector<int> numbers; int main() { int counter; int sec_counter; int number; float oper_number; int oper_counter; cin >> counter; for (size_t i = 0; i < counter; i++) { cin >> sec_counter; for (size_t y = 0; y < sec_counter; y++) { cin >> number; numbers.push_back(number); } sort(numbers.begin(), numbers.end()); if (sec_counter % 2 != 0) { oper_counter = sec_counter / 2; oper_number = numbers.at(oper_counter); cout << std::fixed << std::setprecision(1) << oper_number << endl; } else { oper_counter = sec_counter / 2; oper_number = (numbers.at(oper_counter) + numbers.at(oper_counter-1)); oper_number = oper_number / 2; cout << std::fixed << std::setprecision(1) << oper_number << endl; } numbers.clear(); } return 0; }

Spirála

  1. Pro zadaný řád matice n vyplnit matici klesající číselnou řadou do spirály z levého horního rohu po směru hodinových ručiček končící ve středu matice do dvourozměrného pole.
  2. Všechny prvky matice (dvourozměrného pole) inicializovat na 0.
  3. Vyplnění matice provést v jediném cyklu for opakující se v intervalu <0; n2 - 1> pozpátku.
  4. V každé obrátce cyklu se do matice uloží jeden její prvek (odpovídá řídící proměnné cyklu for).
  5. Matici začít vyplňovat z levého horního rohu směrem doprava, dokud nenarazíme na hranici (konec matice, nebo již vyplněný prvek matice).
  6. Pokud narazíme na hranici matice, změníme směr vyplňování o 90 stupňů po směru hodinových ručiček.

Příklad zdrojového kódu:

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Spirala { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); sc.nextLine(); int[][] results = new int[size][size]; int x = 0; int y = 0; int direction = 0; int currentNum = size * size - 1; int longestNumLength = (currentNum + "").length(); while (true) { if (size == 1) { results[0][0] = 0; break; } if (currentNum == -1) break; if (results[x][y] != 0) { if (direction == 0) //right { x--; y++; } else if (direction == 1) //down { y--; x--; } else if (direction == 2) //left { x++; y--; } else if (direction == 3) //up { y++; x++; } if (direction == 3) direction = 0; else direction++; continue; } if (x + 1 == size && direction == 0 || x == 0 && direction == 2) { if (direction == 3) direction = 0; else direction++; //x--; continue; } if ( y + 1 == size && direction == 1 || y == 0 && direction == 3) { if (direction == 3) direction = 0; else direction++; //y--; continue; } results[x][y] = currentNum--; if (direction == 0) //right x++; else if (direction == 1) //down y++; else if (direction == 2) //left x--; else if (direction == 3) //up y--; } for( x = 0; x < size; x++) { for( y = 0; y < size; y++) { if (y == 0) { PrintSpaces(SpacesNeeded(longestNumLength, results[y][x])); System.out.print(results[y][x]); continue; } PrintSpaces(1); PrintSpaces(SpacesNeeded(longestNumLength, results[y][x])); System.out.print(results[y][x]); } System.out.println(); } } private static void PrintSpaces(int count) { for (int x = 0; x < count; x++) System.out.print(" "); } private static int SpacesNeeded(int longest, int current) { return longest - String.valueOf(current).length(); } }

Kvalifikační úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Jak úlohy řešili soutěžící, je ukázáno na vybraných příkladech zdrojových kódů odevzdaných soutěžních úloh.

Jezdec

  1. Pro každou šachovnici si načíst její rozměr a jednotlivá pole.
  2. Startovní, cílové a volná políčka považovat za vrcholy grafu. Vrcholy spolu sousedí (mají mezi sebou hranu), pokud mezi nimi zle skočit pohybem jezdce (do L).
  3. Pomocí prohledávání do šířky najít nejkratší cestu ze startovního do cílového pole a při tom určit její délku.
  4. Pokud taková cesta existuje, vypsat její délku. Pokud neexistuje, vypsat „-1“.

Příklad zdrojového kódu:

#include<iostream> #include<queue> using namespace std; int n; int dist[123][123]; char c[123][123]; int inf = 1e6; int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1}; struct s { int i, j, d; }; queue<s> q; void clr() { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) dist[i][j] = inf; while(!q.empty()) q.pop(); } int main(int argc, char const *argv[]) { while(cin>>n) { if(!n) break; clr(); s end; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin>>c[i][j]; if(c[i][j] == 'S') q.push({i, j, 0}); if(c[i][j] == 'C') end = {i, j, 0}; } } while(!q.empty()) { s x = q.front(); q.pop(); for(int i = 0; i < 8; i++) { if(x.i+dx[i] >= 0 && x.i+dx[i] < n && x.j+dy[i] >= 0 && x.j+dy[i] < n) { if(dist[x.i+dx[i]][x.j+dy[i]] > x.d+1 && (c[x.i+dx[i]][x.j+dy[i]] == '.' || c[x.i+dx[i]][x.j+dy[i]] == 'C')) { dist[x.i+dx[i]][x.j+dy[i]] = x.d+1; q.push({x.i+dx[i], x.j+dy[i], x.d+1}); } } } } if(dist[end.i][end.j] < inf) cout<<dist[end.i][end.j]<<endl; else cout<<-1<<endl; } return 0; }

Kolize

  1. Pro každou hru načíst rozměry stolu, maximální dráhu disku a počáteční pozice a směry disků obou hráčů.
  2. Simulovat pohyb obou disků současně z jejich počátečních pozic krok za krokem.
  3. V každém kroku podle směru inkrementovat obě složky souřadnice obou disků, zkontrolovat, zda disky nenarazily na stěnu a pokud ano, obrátit směr podle toho, o jakou stěnu se jedná.
  4. V každém kroku dále zkontrolovat, zda se disky nesrazily mezi mřížkou a na mřížce (porovnáním souřadnic) a zda už neurazily maximální dráhu.
  5. Pokud se srazily, vypsat souřadnice srážky. Pokud se nesrazily a urazily maximální dráhu, vypsat „-1 -1“.

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <algorithm> using namespace std; void solve(){ double s, v, p; cin >> s >> v >> p; vector<vector<double> > arr(2, vector<double>(4)); for(int i = 0; i < 2; i++){ cin >> arr[i][0] >> arr[i][1] >> arr[i][2] >> arr[i][3]; } double it = 0; double len; double px, py; while(it <= p){ /*cout << arr[0][0] << (arr[0][2] > 0 ? " + " : " - ") << arr[0][1] << (arr[0][3] > 0 ? " + " : " - ") << endl; cout << arr[1][0] << (arr[1][2] > 0 ? " + " : " - ") << arr[1][1] << (arr[1][3] > 0 ? " + " : " - ") << endl;*/ if(it == p){ if(arr[0][0] == arr[1][0] && arr[0][1] == arr[1][1]){ cout << arr[0][0] << " " << arr[0][1] << endl; return; }else break; } len = min( min(arr[0][2] > 0 ? (s-1) - arr[0][0] : arr[0][0], arr[0][3] > 0 ? (v-1) - arr[0][1] : arr[0][1]), min(arr[1][2] > 0 ? (s-1) - arr[1][0] : arr[1][0], arr[1][3] > 0 ? (v-1) - arr[1][1] : arr[1][1]) ); if(len == 0){ for(int i = 0; i < 2; i++){ if(arr[i][0]+arr[i][2] >= s || arr[i][0]+arr[i][2] < 0) arr[i][2] *= -1; if(arr[i][1]+arr[i][3] >= v || arr[i][1]+arr[i][3] < 0) arr[i][3] *= -1; } continue; } px = (abs(arr[0][0] - arr[1][0]) / 2); py = (abs(arr[0][1] - arr[1][1]) / 2); if(it + px <= p && len >= px){ if(arr[0][0] + px*arr[0][2] == arr[1][0] + px*arr[1][2] && arr[0][1] + px*arr[0][3] == arr[1][1] + px*arr[1][3]){ cout << arr[0][0] + px*arr[0][2] << " " << arr[0][1] + px*arr[0][3] << endl; return; } } if(it + py <= p && len >= py){ if(arr[0][0] + py*arr[0][2] == arr[1][0] + py*arr[1][2] && arr[0][1] + py*arr[0][3] == arr[1][1] + py*arr[1][3]){ cout << arr[0][0] + py*arr[0][2] << " " << arr[0][1] + py*arr[0][3] << endl; return; } } for(int i = 0; i < 2; i++){ arr[i][0] += len*arr[i][2]; arr[i][1] += len*arr[i][3]; } it += len; } cout << -1 << " " << -1 << endl; } int main(){ int h; cin >> h; while(h--){ solve(); } return 0; }

Obdélníky

  1. Načíst a uložit všechny obdélníky do datové struktury.
  2. Pro určení maximální souvislé plochy použít zametací přímku, která bude postupovat zleva doprava ve směru osy x a udržovat intervaly aktivních obdélníků (ty, které mají s přímkou nějaký průnik). K tomu lze použít např. stromovou strukturu.
  3. Když přímka narazí na začátek nového obdélníku, najít průnik se sousedem ve stromě, propojit je a do stromu vložit nový interval. Když přímka narazí na konec obdélníku, vyjmout příslušný interval ze stromu.
  4. Po spojení všech sousedních obdélníku pomocí zametací přímky (viz výše) projít komponenty souvislosti, spočítat jejich plochu, vybrat a vypsat maximum.

Příklad zdrojového kódu:

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Random; import java.util.Scanner; public class Obdelniky3 { public static List<Obdelnik> list = new ArrayList<>(); public static HashMap<Integer, List<Interval>> verticalData = new HashMap<>(); public static HashMap<Integer, List<Interval>> horizontalData = new HashMap<>(); public static long maxSize = 0; public static GroupObdelnik tmpGroup = new GroupObdelnik(); public static void main(String[] args) { readObdelniky(); start(); } public static long start() { verticalData = new HashMap<>(); horizontalData = new HashMap<>(); maxSize = 0; tmpGroup = new GroupObdelnik(); for(int i = 0; i < list.size(); i++) { Obdelnik o = list.get(i); o.setSize(o.s * o.v); //System.out.println(" - Jdeme řešit obdelnik: "+o); // dolní strana addToData(horizontalData, o.y, o.x, o.x + o.getOpSirka(), o); // horní strana if(o.v != 1) { addToData(horizontalData, o.y+o.getOpVyska(), o.x, o.x + o.getOpSirka(), o); } // levá strana addToData(verticalData, o.x, o.y, o.y+o.getOpVyska(), o); // pravá strana if(o.s != 1) { addToData(verticalData, o.x+o.getOpSirka(), o.y, o.y+o.getOpVyska(), o); } o.addToPridruzene(checkForObdelnik(horizontalData, o.y-1, o.x, o.x + o.getOpSirka(), o)); // dolní strana o.addToPridruzene(checkForObdelnik(horizontalData, o.y+o.getOpVyska()+1, o.x, o.x + o.getOpSirka(), o)); // horní strana o.addToPridruzene(checkForObdelnik(verticalData, o.x-1, o.y, o.y+o.getOpVyska(), o)); // levá strana o.addToPridruzene(checkForObdelnik(verticalData, o.x+o.getOpSirka()+1, o.y, o.y+o.getOpVyska(), o)); // pravá strana for(Obdelnik pridruzenec : o.pridruzene){ pridruzenec.addToPridruzene(o); } //o.zarad(); } /* for(int i = 0; i < list.size(); i++) { Obdelnik o = list.get(i); //System.out.println("-"+o); for(Obdelnik pri : o.pridruzene) { //System.out.println(" "+pri); } }*/ while(!list.isEmpty()){ tmpGroup = new GroupObdelnik(); Obdelnik o = list.get(list.size()-1); //System.out.println("nová groupa z "+o); o.addToGroup(); } System.out.println(maxSize); return maxSize; } public static class GroupObdelnik { private int size = 0; public List<Obdelnik> obdelniky = new ArrayList<>(); public void add(Obdelnik o) { if(!obdelniky.contains(o)) { size += o.size; if(size > maxSize){ maxSize = size; } //System.out.println("Momental size: "+size); obdelniky.add(o); } } } public static List<Obdelnik> checkForObdelnik( HashMap<Integer, List<Interval>> data, int key, int start, int end, Obdelnik o) { List<Obdelnik> obdelniki = new ArrayList<>(); List<Interval> li = data.get(key); if(li != null) { for(Interval i : li) { ////System.out.println("prvni interval: " + start + "-"+end + "; druhy: "+i.start + "-"+i.end); if(!(i.start > end || start > i.end)) { Obdelnik obdelnikIntervalu = i.getObdelnik(); if(!obdelniki.contains(obdelnikIntervalu)) { obdelniki.add(obdelnikIntervalu); } } // TODO pokud je větší než uložené storovat do global proměnné } } return obdelniki; } public static void addToData( HashMap<Integer, List<Interval>> data, int key, int start, int end, Obdelnik o) { //System.out.println("Starting adding data"); List<Interval> li; if(data.containsKey(key)) { li = data.get(key); } else { li = new ArrayList<>(); } Interval newInterval = new Interval(start, end, o); li.add(newInterval); data.put(key, li); } public static void readObdelniky() { Scanner sc = new Scanner(System.in); int pocet = sc.nextInt(); sc.nextLine(); for(int i=0; i<pocet; i++) { String body = sc.nextLine(); String[] arrBody = body.split("\\s+"); Obdelnik inst = new Obdelnik( Integer.parseInt(arrBody[0]), Integer.parseInt(arrBody[1]), Integer.parseInt(arrBody[2]), Integer.parseInt(arrBody[3])); list.add(inst); } sc.close(); } public static class Interval { int start, end; public Obdelnik obdelnik; public Interval(int start, int end, Obdelnik Obdelnik) { this.start = start; this.end = end; this.obdelnik = Obdelnik; } public Obdelnik getObdelnik() { return obdelnik; } public void setObdelnik(Obdelnik obdelnik) { this.obdelnik = obdelnik; } @Override public String toString() { return "Interval [start=" + start + ", end=" + end + ", Obdelnik=" + obdelnik + "]"; } } public static int obdelnikIndex = 1; public static class Obdelnik { int x, y, s, v; int index = 0; int size; public void addToGroup(){ if(!tmpGroup.obdelniky.contains(this)) { tmpGroup.add(this); } list.remove(this); for(Obdelnik pri : pridruzene){ if(!tmpGroup.obdelniky.contains(pri)) { //System.out.println("pridávám do groupy " + pri); pri.addToGroup(); } } } List<Obdelnik> pridruzene = new ArrayList<>(); public Obdelnik(int x, int y, int s, int v) { this.x = x; this.y = y; this.s = s; this.v = v; this.index = obdelnikIndex++; } public Obdelnik(int x, int y, int s, int v, int index) { this.x = x; this.y = y; this.s = s; this.v = v; this.index = index; } public int getOpSirka() { return s -1; } public int getOpVyska() { return v -1; } @Override public String toString() { return "Obdelnik "+index+" [x=" + x + ", y=" + y + ", s=" + s + ", v=" + v + "] " + size; } public int getSize() { return size; } public void setSize(int size) { this.size = size; } public void addToPridruzene(List<Obdelnik> ob) { if(ob != null) { for(Obdelnik o : ob) { if(!pridruzene.contains(o)) { pridruzene.add(o); } } } } public void addToPridruzene(Obdelnik ob) { if(!pridruzene.contains(ob)) { pridruzene.add(ob); } } } }

Ping pong

  1. Pro každý turnaj načíst počet hráčů a zápasů a následně všechny odehrané zápasy.
  2. Každé číslo hráče představuje vrchol grafu. Vrcholy spolu sousedí (mají mezi sebou hranu), pokud spolu hráči odehráli zápas.
  3. Obarvit graf dvěmi barvami pomocí prohledávání do šířky. Počátečnímu vrcholu (lze zvolit náhodně) přiřadit jednu z barev (lze zvolit náhodně). Nově nalezeným sousedním vrcholům vždy přiřadit tu druhou barvu, než má aktuální vrchol. Zároveň u již navštívených sousedů zjišťovat, zda nemají stejnou barvu, jako aktuální vrchol. Pokud ano, někdo hrál za opačné pohlaví, lze skončit a vypsat „Nekdo hral za opacne pohlavi“.
  4. Pokud prohledávání do šířky doběhlo, ale nebyly navštíveny všechny vrcholy (všichni hráči), vybrat ze seznamu vrcholů první nenavštívený vrchol a z tohoto vrcholu pokračovat v obarvování grafu (graf nemusí být souvislý, nemusí hrát každý s každým).
  5. Pokud se podaří obarvit celý graf tak, aby měli všechny sousední vrcholy rozdílné barvy, vypsat „OK“.

Příklad zdrojového kódu:

#include<bits/stdc++.h> #include<iostream> using namespace std; int main(){ int t; cin>>t; int a, b; int start, koukam, soused; for(int i=0;i<t;i++){ queue<int> fronta; int h,l; cin>>h>>l; vector <int> graf[h]; int barva[h]; for(int j=0;j<h;j++){barva[j]=-1;} for(int j=0;j<l;j++){ cin>>a>>b; graf[a-1].push_back(b-1); graf[b-1].push_back(a-1); } /* for(int j=0;j<h;j++){ cout<<"vrchol "<<j+1<<" sousedi s vrcholy: "; for(int k=0;k<graf[j].size();k++){ cout<<graf[j][k]+1<<" "; } cout<<endl; } */ while(true){ start=-1; for(int j=0;j<h;j++){ if(barva[j]==-1){start=j;break;} } if(start==-1){cout<<"OK"<<endl;break;} //cout<<"zacinam bfs z vrcholu "<<start+1<<endl; fronta.push(start); barva[start]=1; while(!fronta.empty()){ koukam = fronta.front(); fronta.pop(); //cout<<"koukam: "<<koukam+1<<endl; for(int k=0;k<graf[koukam].size();k++){ soused=graf[koukam][k]; if(barva[soused]==-1){ barva[soused]=(barva[koukam]+1)%2; fronta.push(soused); } else if(barva[soused]==barva[koukam]){ cout<<"Nekdo hral za opacne pohlavi"<<endl; goto NEVYSLO; } } /* cout<<"barvicky jsou: "; for(int k=0;k<h;k++){ cout<<barva[k]<<", "; } cout<<endl; */ } } NEVYSLO:continue; } return 0; }

Programátoři

  1. Pro každý pracovní plán načíst počet programátorů a jednotlivé části práce a uložit je do pole, ve kterém indexy odpovídají jednotlivým programátorům.
  2. Vytvořit alternativní plán do stejně velkého pole, kde jednotlivé indexy odpovídají jednotlivým částem práce.
  3. Porovnat obě pole buňku po buňce. Pokud je nalezen rozdíl, vypsat „Nutno upravit!“. Pokud jsou obsahy obou polí shodné, vypsat „Ke strojum!“.

Příklad zdrojového kódu:

program programatori; var o, i : byte; p, pom : Integer; prace : array of Integer; begin ReadLn(o); for I := 1 to o do begin ReadLn(p); SetLength(prace,p+1); For Pom := 1 to P do Read(prace[Pom]); While (p >= 1) and (p = prace[prace[p]]) do dec(p); if p = 0 then WriteLn('Ke strojum!') else WriteLn('Nutno upravit!'); end; end.

Radioamatér

  1. Pro každý čas načíst hodiny a minuty.
  2. Postupně inkrementovat čas o jednu minutu. Pokud minuty dosáhnou hodnoty 60, nastavit minuty na 00 a inkrementovat hodinu. Pokud hodiny dosáhnou hodnoty 24, nastavit hodiny na 00.
  3. Po každé inkrementaci zjistit, zda je aktuální čas palindromatický (tj. jednotky hodin se rovnají desítkám minut a desítky hodin se rovnají jednotkám minut).
  4. Pokud je čas palindromatický, vypsat ho.

Příklad zdrojového kódu:

#include <stdio.h> #include <stdlib.h> /* Kvalifinkacni ukol pro PILSPROG-Radioamater Filip Borsodi Time&date: 13:51 24.2.2019 Najde nejblizsi cas vysilani pro n zadanych casu. */ int main() { int c=0; scanf("%d",&c); int m=0; int h=0; int h1; int h2; int i; for(i=0;i!=c;i++){ scanf("%d:%d",&h,&m); h1=h/10; h2=h-h1*10; if((h>=6)&&(h<=9)){ h1=1; h2=0; h=10; m=0; } if((h>=16)&&(h<=19)){ h1=2; h2=0; h=20; m=0; } if(((h2*10)+h1)>m){ //printf("\n%d%d:%d%d",h1,h2,h2,h1); }else if(h==5){ h1=1; h2=0; h=10; m=0; }else if(h==15){ h1=2; h2=0; h=20; m=0; }else if(h==23){ h1=0; h2=0; h=0; m=0; }else{ h++; h1=h/10; h2=h-h1*10; } printf("%d%d:%d%d\n",h1,h2,h2,h1); } return 0; }

Finálové úlohy - řešení

Nejprve je stručně popsán způsob, jakým je možno úlohu řešit. Následně je ukázán zdrojový kód řešení vytvořeného jedním z finalistů.

K nahlédnutí je rovněž prezentace s popisem řešení předvedená po skončení finále.

Evakuace

  1. Načíst počet místností a následně všechny místsnoti (název a jednotlivé velikosti evakuačních položek). Nakonec načíst dveře spojující místnosti.
  2. Místnosti představují vrcholy a dveře hrany grafu. Jeden vrchol grafu představuje i východ (exit). Ohodnocení hrany grafu odpovídá velikosti dveří. Pokud je mezi dvěma místnostmi více dveří, důležité jsou pouze ty větší, hrana tedy bude mít ohodnocení odpovídající největším dveřím spojující dané dvě místnosti.
  3. Hledat maximální „propustnost“ cesty z východu do místnosti pro každou místnot. Propustnost odpovídá velikosti nejmenších dveří, přes které je nutno projít. Tyto cesty lze najít upraveným Dijkstrovým algoritmem pro hledání nejkratší cesty.
  4. Změna Dijkstrova algoitmu spočívá ve změněném ohocnocení hledaných cest. Při konstruování cest přidáváním hran se místo délky cesty, která se standardně počítá jako součet ohocnocení všech hran, přes které cesta vede, použije propustnost určená jako minimum z dosavadní propustnosti cesty a propustnosti právě přidávané hrany.
  5. Po dokončení upraveného Dijkstrova algoritmu je ve všech vrcholech (tj. místnostech) zaznamenána maximální propustnost, tedy velikost největší evakuační položky, která z místnosti může být odnesena ven. V každém vrcholu pak stačí projít všechny položky a spočítat, kolik z nich lze odnést.
  6. Vypsat celkový součet všech odnesitelných položek pro všechny vrcholy.

Příklad zdrojového kódu:

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; public class Evakuace { public static Scanner sc = new Scanner(System.in); public static HashMap<String, Room> rooms = new HashMap<>(); public static List<Door> doors = new ArrayList<>(); public static boolean newPathFound = true; public static void main(String[] args) { loadInput(); calculate(); int itemsCount = 0; for (Room room : rooms.values()) { itemsCount += room.getAvailableItemsCount(); } System.out.println(itemsCount); } private static void calculate() { while (newPathFound) { newPathFound = false; for (Door door : doors) { Room room1 = rooms.get(door.room1); Room room2 = rooms.get(door.room2); calculateDoor(door, room1, room2); } } } private static void calculateDoor(Door door, Room room1, Room room2) { if ( room1.maxSizeToExit < room2.maxSizeToExit && room1.maxSizeToExit < door.size) { if (door.size > room2.maxSizeToExit) { room1.maxSizeToExit = room2.maxSizeToExit; newPathFound = true; } else { room1.maxSizeToExit = door.size; newPathFound = true; } } else if ( room2.maxSizeToExit < room1.maxSizeToExit && room2.maxSizeToExit < door.size) { if (door.size > room1.maxSizeToExit) { room2.maxSizeToExit = room1.maxSizeToExit; newPathFound = true; } else { room2.maxSizeToExit = door.size; newPathFound = true; } } } public static class Room { public String name; public int[] items; public int maxSizeToExit = 0; public Room(String roomString) { String[] roomStringSplit = roomString.split(" "); name = roomStringSplit[0]; items = new int[roomStringSplit.length - 1]; for (int i = 0; i < items.length; i++) { items[i] = Integer.parseInt(roomStringSplit[i+1]); } } public Room() { this.name = "exit"; this.items = new int[0]; this.maxSizeToExit = Integer.MAX_VALUE; } public int getAvailableItemsCount() { int itemsCount = 0; for (int item : items) { if (item <= maxSizeToExit) { itemsCount++; } } return itemsCount; } } public static class Door { public int size; public String room1; public String room2; public Door(String doorString) { String[] doorStringSplit = doorString.split(" "); room1 = doorStringSplit[0]; room2 = doorStringSplit[1]; size = Integer.parseInt(doorStringSplit[2]); } } public static void loadInput() { int roomsCount = sc.nextInt(); sc.nextLine(); for (int i = 0; i < roomsCount; i++) { Room room = new Room(sc.nextLine()); rooms.put(room.name, room); } int doorsCount = sc.nextInt(); sc.nextLine(); for (int i = 0; i < doorsCount; i++) { doors.add(new Door(sc.nextLine())); } // Creates exit rooms.put("exit", new Room()); } }

ISBN

  1. Pro každý testovací případ načíst ISBN-13 a odstranit z něj všechny pomlčky.
  2. Jednotlivé číslice (kromě poslední) a váhy popsané v zadání použít pro výpočet kontrolního součtu ISBN-13. Ověřit, že je číslo podle kontrolního součtu platné. Ověřit, že číslo má prefix 978.
  3. Pokud číslo není platné nebo nemá správný prefix, vypsat „nelze“
  4. Jinak odstranit prefix a zbylé číslice (kromě poslední) a váhy popsané v zadání použít pro výpočet kontrolního součtu ISBN-10. Doplnit odpovídající číslici nebo „X“. Výsledné ISBN-10 vypsat.

Příklad zdrojového kódu:

package isbn; import java.util.*; public class isbn { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int cases = sc.nextInt(); sc.nextLine(); String present; String temp; for(int i = 0; i<cases; i++) { present = sc.nextLine().trim(); temp = ""; for(int j = 0; j<present.length();j++) { if(present.charAt(j)!='-') temp+= present.charAt(j); } System.out.println(solve(temp)); } } public static String solve(String present) { //String old = ""; String digits = "0123456789"; int n = 0; int counter = 10; int check = 0; int w = 1; if(!present.startsWith("978")) return "nelze"; //System.out.println(present.length()); //System.out.println(present.length()!=16); if((present.length()!=16) && (present.length()!=13)) return "nelze"; for (int i = 0; i<present.length();i++) { if(present.charAt(i)!='-' && !digits.contains(""+present.charAt(i))) return "nelze"; } for (int i = 0; i <present.length();i++) { if(present.charAt(i)!='-') { check+= w*Integer.parseInt(""+present.charAt(i)); if(w==1) w = 3; else w=1; } } if(check%10!=0) return "nelze"; present = present.substring(3, present.length()-1); if (present.startsWith("-")) present = present.substring(1); for(int i = 0; i < present.length();i++) { if(present.charAt(i)!='-') { n+= counter*Integer.parseInt(""+present.charAt(i)); counter--; } } int m = n%11; m = 11 - m; if (m==10) { present = present + "X"; } if(m==11) { present = present +"0"; } else if(m!=11 && m!=10) present = present + m; return present; } }

Přístupové karty

  1. Pro každý testovací případ načíst šířku a výšku plánu budovy a jeho jednotlivé znaky. Pokud jsou šířka i výška rovny 0, skončit.
  2. Délku nejkratší budovy určit modifikovaným prohledáváním do šířky, kdy jednotlivá políčka mohou být navštívena vícekrát, pro daný stav karet však pouze jednou. Připravit si frontu pro prozkoumávaná políčka a tabulku pro uložení vzdáleností políček pro dané souřadnice a daný stav sebraných karet.
  3. Do fronty vložit počáteční políčko s žádnou kartou a uložit si jeho vzdálenost od počátku 0. V cyklu vybírat políčka z fronty, dokud není nalezen východ, nebo dokud fronta není prázdná.
  4. V každé obrátce cyklu vybrat políčko z fronty i s aktuálním stavem karet, z tabulky zjistit jeho vzdálenost od počátku. Zpracovat s využitím aktuálních karet a vzdálenosti políčka od začátku všechna vertikálně a horzintálně sousedící políčka, pokud tato políčka existují a jsou přístupná.
  5. Pro každé sousední políčko aktualizovat stav karet (pokud políčko obsahuje kartu) a/nebo uložit o 1 větší vzdálenost pro aktuální stav karet (pokud již nebyla uložena).
  6. Pokud je sousední políčko východ, cyklus ukončit a vypsat aktuální vzdálenost. Pokud není východ nalezen, vypsat -1.

Příklad zdrojového kódu:

#include <iostream> #include <queue> #include <set> #define f first #define s second #define coor std::pair<int,int> #define stav std::pair<long long,coor> bool hasKey(long long c, int door) { door=-door-2; c/=(1<<door); return c%2; } long long addKey(long long c, int key) { if(hasKey(c,-key)) return c; key-=2; c+= (1 << key); return c; } int main() { //std::cout << addKey(0,4) << std::endl; //std::cout << hasKey(4,-4) << std::endl; int r,s; while(std::cin >> r >> s) { if(r==0 && s ==0) return 0; coor p; int map[r][s]; for(int i=0;i<r;i++) { for(int j=0;j<s;j++) { char ch; std::cin >> ch; switch(ch){ case '#': map[i][j]=-1; break; case '.': map[i][j]=0; break; case '+': map[i][j]=1; break; default: if(ch == '*') { map[i][j]=0; p.f=i;p.s=j; } if(int(ch)>96) map[i][j]=(int(ch)-int('a')+2); else map[i][j] = -(int(ch)-int('A')+2); break; } } } std::queue<std::pair<stav,int> > q; std::set<stav> was; stav beg; beg.f=0; beg.s=p; q.push({beg,0}); was.insert(beg); bool end = false; while(!q.empty()) { stav cur = q.front().first; int dist = q.front().second; q.pop(); //std::cout << dist << " diii" << std::endl; int &x=cur.s.f; int &y=cur.s.s; //std::cout << x << " " << y << " - "; //for(int i=0;i<26;i++) std::cout << hasKey(cur.f,i+1) << " "; //std::cout << std::endl; if(map[x][y]==1) { end = true; std::cout << dist << std::endl; break; } if(x>0) { if(map[x-1][y]!= -1) { stav nstav=cur; nstav.s.f--; if(map[x-1][y] > 1) { nstav.f=addKey(nstav.f,map[x-1][y]); } if(map[x-1][y] < -1) { if(hasKey(nstav.f,map[x-1][y])) { if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } else if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } if(x<r-1) { if(map[x+1][y]!= -1) { stav nstav=cur; nstav.s.f++; if(map[x+1][y] > 1) { nstav.f=addKey(nstav.f,map[x+1][y]); } if(map[x+1][y] < -1) { if(hasKey(nstav.f,map[x+1][y])) { if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } else if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } if(y>0) { if(map[x][y-1]!= -1) { stav nstav=cur; nstav.s.s--; if(map[x][y-1] > 1) { nstav.f=addKey(nstav.f,map[x][y-1]); } if(map[x][y-1] < -1) { if(hasKey(nstav.f,map[x][y-1])) { if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } else if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } if(y<s-1) { if(map[x][y+1]!= -1) { stav nstav=cur; nstav.s.s++; //std::cout << "tadyy " << map[x][y+1] << " " << was.count(nstav) << std::endl; if(map[x][y+1] > 1) { nstav.f=addKey(nstav.f,map[x][y+1]); } if(map[x][y+1] < -1) { if(hasKey(nstav.f,map[x][y+1])) { if(!was.count(nstav)) { was.insert(nstav); q.push({nstav,dist+1}); } } } else if(was.count(nstav)==0) { //std::cout << "jsem tu" << std::endl; was.insert(nstav); q.push({nstav,dist+1}); } } } } if(!end) std::cout << -1 << std::endl; } }

Lišák

  1. Určit si počty tahů z cílového stavu hry do všech možných stavů hry pomocí prohledávání do šířky - hledat délku cesty z cílového stavu do všech ostaních stavů, délka cesty odpovídá počtu tahů. Stavů je jen 9! = 362880.
  2. Jednotlivé stavy si ukládat do pole s délkou cesty z cílového stavu (inicializovat na -1) a indikací, zda už byl stav navštíven. Index stavu lze spočítat z permutace čísel, která ho definuje, jako 8!a + 7!b + ... + 2!g + 1!h, pričemž koeficienty ah udávají počet menších čísel vpravo od odpovídající pozice v permutaci (tedy a za pocicí 0, b za pozicí 1, atd.).
  3. Koncový stav vložit do fronty, nastavit jeho vzdálenost na 0 a indikaci, že byl navštíven. Dále v cyklu vybírat z fronty stavů, dokud není prázdná.
  4. Pro každý aktuální stav vybraný z fronty najít platné nenavštívené sousedy (dané posunutím 0 o jednu pozici nahoru, dolu, doleva, nebo doprava), uložit si do nich inkrementovanou délku cesty z koncového do aktuálního stavu, označit je jako navštívené a přidat je do fronty.
  5. Načíst si počet her. Pro každou hru načíst tři řádky s čísly a uložit jednotlivé číslice např. do pole - tyto číslice reprezenují počáteční stav.
  6. Pro načtený počáteční stav spočítat index do pole stavů a vypsat předpočítanou délku cesty z koncového stavu (odpovídá počtu tahů potřebných k dosažení koncového stavu).

Příklad zdrojového kódu:

#include <iostream> #include <vector> #include <queue> #include <map> std::vector<int> v(9); int x;int y; int toNum() { int num=0; int krat=1; for(int i=0;i<v.size();i++) { num+=v[i]*krat; krat*=10; } return num; } void fromNum(long long num) { for(int i=0;i<9;i++) { v[i]=num%10; if(num%10==0) { x=i%3; y=i/3; } num/=10; } } int mup() { if(y==0) return -1; std::swap(v[x+3*y],v[x+3*(y-1)]); return 0; } int mdown() { if(y==2) return -1; std::swap(v[x+3*y],v[x+3*(y+1)]); return 0; } int mleft() { if(x==0) return -1; std::swap(v[x+3*y],v[x-1+3*y]); return 0; } int mright() { if(x==2) return -1; std::swap(v[x+3*y],v[x+1+3*y]); return 0; } int main() { int vs = 12345678; fromNum(vs); std::queue<std::pair<int,int>> q; std::map<int,int> was; q.push({toNum(),0}); was[toNum()]=0; bool end = false; while(!q.empty()) { int cur; cur = q.front().first; int dist = q.front().second; q.pop(); fromNum(cur); if(mup()!=-1) { int ne = toNum(); if(!was.count(ne)) { was[ne]=dist+1; q.push({ne,dist+1}); } fromNum(cur); } if(mdown()!=-1) { int ne = toNum(); if(!was.count(ne)) { was[ne]=dist+1; q.push({ne,dist+1}); } fromNum(cur); } if(mleft()!=-1) { int ne = toNum(); if(!was.count(ne)) { was[ne]=dist+1; q.push({ne,dist+1}); } fromNum(cur); } if(mright()!=-1) { int ne = toNum(); if(!was.count(ne)) { was[ne]=dist+1; q.push({ne,dist+1}); } fromNum(cur); } } int T; std::cin >> T; while(T--) { for(int i=0;i<9;i++) { char tmp; std::cin >> tmp; int add; switch(tmp){ case '0': add=0; break; case '1': add=1; break; case '2': add=2; break; case '3': add=3; break; case '4': add=4; break; case '5': add=5; break; case '6': add=6; break; case '7': add=7; break; case '8': add=8; break; case '9': add=9; break; } v[i] = add; } int cur = toNum(); if(was.count(cur)) std::cout << was[cur] << std::endl; else std::cout << -1 << std::endl; } }

Sirky

  1. Určit si výhru prvního hráče pro každý možný počáteční počet sirek a uložit výsledek do pole. Index pole odpovídá počátečnímu počtu sirek. Pro 0 a 1 první hráč vždy prohraje. Pro více sirek nutno spočítat.
  2. Pro počáteční počet sirek určit počet jedniček v jeho binární reprezentaci. Od počtu postupně zkoušet odečíst všechny menší mocniny 2 (obsahují jen jednu jedničku ve svém binárním zápisu). Pokud ve výsledném rozdílu (počet sirek po tahu hráče) zůstal zachován počet jedniček a počet sirek rovný vypočtenému rozdílu je prohrávající, nastavit výhru prvního hráče.
  3. Načíst počet her. Pro každou hru načíst počáteční počet sirek a tuto hodnotu použít jako index do předpočítaného pole výher prvního hráče. Pokud je na daném indexu výhra, vypsat 1, jinak vypsat 2.

Příklad zdrojového kódu:

#include <iostream> #include <string> #include <vector> using namespace std; int indexOfZero(vector<int> &coll, int init) { for (int i = coll.size() - 1 - init; i >= 0; --i) { if (coll[i] == 0) return i; } return -1; } void solve() { int x; cin >> x; /*int y = x; int size = 0; while (y != 0) { y /= 2; size++; }*/ vector<int> binar; while (x != 0) { binar.push_back(x % 2); x /= 2; } int init = 0; int count = 0; while (true) { int ind = indexOfZero(binar, init); if (ind == -1) { break; } if (ind == binar.size()-2-init) { ++init; } binar[ind] = 1; binar[ind + 1] = 0; ++count; } if (count % 2 == 0) { cout << "2\n"; } else { cout << "1\n"; } } int main() { int count; cin >> count; for (int i = 0; i < count; ++i) { solve(); } return 0; }