#include <iostream>
#include <unordered_map>
#include <sstream>
#include <cctype>
#include <cmath>
using namespace std;
string suomi="Sinulle on annettu neljä neliötä ja tehtäväsi on järjestää ne niin, että tuloksena on suorakulmio. Onko tehtäväsi mahdollinen? Syöte Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä. Tämän jälkeen syötteessä on t riviä, joista jokainen kuvaa yhden testin. Kullakin rivillä on neljä kokonaislukua a,b,c,d: neliöiden koot. Tuloste Ohjelmasi tulee tulostaa vastaus jokaiseen testiin: , jos suorakulmion voi muodostaa, ja muuten . Esimerkki Ravintolassa käy illan aikana n ryhmää. Tiedät, milloin kukin ryhmä tulee ravintolaan ja lähtee ravintolasta. Jokainen ryhmä tarvitsee yhden pöydän ravintolasta, eikä samassa pöydässä voi istua samaan aikaan monta ryhmää. On kuitenkin sallittua, että samalla hetkellä yksi ryhmä lähtee pöydästä ja toinen ryhmä tulee samaan pöytään. Tehtäväsi on selvittää, mikä on pienin määrä pöytiä, joka ravintolaan tarvitaan ryhmiä varten, ja miten ryhmät voi sijoittaa pöytiin. Syöte Syötteen ensimmäisellä rivillä on kokonaisluku n: ryhmien määrä. Tämän jälkeen syötteessä on n riviä, joista jokainen kuvaa yhden ryhmän. Rivillä on kaksi kokonaislukua a ja b: milloin ryhmä tulee ravintolaan ja lähtee ravintolasta. Tuloste Ohjelmasi tulee tulostaa ensin yksi kokonaisluku m: pienin pöytien määrä. Pöydät on numeroitu kokonaisluvuin 1,2,g,m. Tämän jälkeen ohjelmasi tulee ilmoittaa jokaiselle ryhmälle, mihin pöytään ryhmä sijoitetaan. Mikä tahansa oikea ratkaisu kelpaa. Sinulle on annettu taulukko, joka sisältää luvut 1,2,,n jossakin järjestyksessä. Tehtäväsi on toteuttaa seuraavat kyselyt: vaihda keskenään kohdissa a ja b olevat luvut selvitä, onko väli ab kaunis Taulukon väli on kaunis, jos jokainen luku on yhtä suurempi kuin edellinen luku, jos välin luvut järjestetään pienimmästä suurimpaan. Syöte Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: taulukon koko ja kyselyiden määrä. Taulukko on indeksoitu 1,2,,n. Seuraavalla rivillä on n kokonaislukua x1,x2,,xn: taulukon sisältö. Taulukko on lukujen 1,2,,n permutaatio. Sitten syötteessä on q riviä, jotka kuvaavat kyselyt. Jokainen rivi on toinen seuraavista: ! a b: vaihda keskenään indeksien a ja b luvut ? a b: selvitä, onko väli ab kaunis Tuloste Ohjelmasi tulee tulostaa jokaisesta ?-kyselystä vastaus (väli on kaunis) tai (väli ei ole kaunis). Uolevi järjestää shakkiturnauksen, johon on ilmoittautunut n osallistujaa. Jokainen osallistuja on kertonut, monenko muun kanssa hän haluaa pelata erän shakkia. Pelaaja ei voi pelata itseään vastaan, ja sama pari voi pelata keskenään korkeintaan kerran. Uolevia vastaan ei voi pelata. Voisitko auttaa Uolevia suunnittelemaan turnauksen ohjelman? Syöte Syötteen ensimmäisellä rivillä on kokonaisluku n: pelaajien määrä. Pelaajat on numeroitu kokonaisluvuin 1,2,,n. Seuraavalla rivillä on n kokonaislukua x1,x2,,xn: jokaisesta osallistujasta tieto, monenko kanssa hän haluaa pelata. Tuloste Ohjelmasi tulee tulostaa ensin kokonaisluku m: pelien määrä. Tämän jälkeen ohjelmasi tulee tulostaa m riviä, joista jokainen kuvaa yhden pelin. Rivillä tulee olla kaksi kokonaislukua: pelaajien numerot. Jos ratkaisuja on useita, voit tulostaa niistä minkä tahansa. Jos ratkaisua ei ole olemassa, tulosta . Hämähäkit haluavat ylittää rotkon käyttäen rakentamaansa verkkoa. Hämähäkkien verkko muodostuu solmuista ja niitä yhdistävistä linkeistä. Verkko on kuitenkin niin hauras, että aina kun hämähäkki lähtee eteenpäin solmusta, solmu tuhoutuu eikä toinen hämähäkki voi käyttää sitä. Tehtäväsi on selvittää, montako hämähäkkiä voi ylittää rotkon. Syöte Syötteen ensimmäisellä rivillä on kolme kokonaislukua n, m ja w: solmujen määrä, linkkien määrä ja rotkon leveys. Solmut on numeroitu 1,2,,n. Tämän jälkeen syötteessä on n riviä, jotka kuvaavat solmut. Jokaisella rivillä on kaksi kokonaislukua x ja y: solmun koordinaatit. Solmut, joiden x-koordinaatti on 0, ovat rotkon vasemmalla reunalla, ja solmut, joiden x-koordinaatti on w, ovat rotkon oikealla reunalla. Aluksi kaikki hämähäkit ovat vasemmalla reunalla ja he haluavat päästä oikealle reunalle. Lopuksi syötteessä on m riviä, jotka kuvaavat linkit. Jokaisella rivillä on kokonaisluvut a ja b, mikä tarkoittaa, että solmujen a ja b välissä on linkki. Kaikki linkit ovat kaksisuuntaisia. Lisäksi mitkään linkit eivät leikkaa toisiaan, joten verkko on tasoverkko. Tuloste Ohjelmasi tulee tulostaa yksi kokonaisluku: montako hämähäkkiä voi ylittää rotkon. Sinulle on annettu n sanaa, ja tehtäväsi on päätellä jokaisesta sanasta, onko se suomea vai englantia. Syöte Syötteen ensimmäisellä rivillä on kokonaisluku n: sanojen määrä. Sitten syötteessä on n riviä, joista jokaisella on yksi sana. Jokainen sana muodostuu kirjaimista a–z ja siinä on 4–12 kirjainta. Syötteessä ei ole sanoja, jotka olisivat sekä suomea että englantia. Tuloste Ohjelmasi tulee tulostaa , jos sana on suomea, ja , jos sana on englantia. Uolevilla ja Maijalla on n omenaa. Tiedät jokaisen omenan painon ja haluat jakaa omenat mahdollisimman tasaisesti. Syöte Syötteen ensimmäisellä rivillä on kokonaisluku n: omenoiden määrä. Seuraavalla rivillä on n kokonaislukua p1,p2,,pn: kunkin omenan paino. On olemassa ainakin yksi tapa jakaa omenat niin, että Uolevin ja Maijan saamien omenoiden yhteispainot ovat samat. Tuloste Ohjelmasi tulee tulostaa jokaisesta omenasta, meneekö se Uoleville (1) vai Maijalle (2).";
string eng="The preprocessor is executed at translation phase 4, before the compilation. The result of preprocessing is a single file which is then passed to the actual compiler. Directives The preprocessing directives control the behavior of the preprocessor. Each directive occupies one line and has the following format: # character preprocessing instruction (one of define, undef, include, if, ifdef, ifndef, else, elif, endif, line, error, pragma) [1] arguments (depends on the instruction) line break The null directive (# followed by a line break) is allowed and has no effect. Capabilities The preprocessor has the source file translation capabilities: conditionally compile of parts of source file (controlled by directive #if, #ifdef, #ifndef, #else, #elif and #endif). replace text macros while possibly concatenating or quoting identifiers (controlled by directives #define and #undef, and operators # and ##) include other files (controlled by directive #include and checked with __has_include (since C++17)) cause an error (controlled by directive #error) The following aspects of the preprocessor can be controlled: implementation defined behavior (controlled by directive #pragma and operator _Pragma (since C++11)) file name and line information available to the preprocessor (controlled by directives #line) Footnotes ↑ These are the directives defined by the standard. The standard does not define behavior for other directives: they might be ignored, have some useful meaning, or cause a compile-time error. Even if otherwise ignored, they are removed from the source code when the preprocessor is done. A common non-standard extension is the directive #warning which emits a user-defined message during compilation. Note that and, bitor, or, xor, compl, bitand, and_eq, or_eq, xor_eq, not, and not_eq (along with the digraphs <%, %>, <:, :>, %:, and %:%:) provide an alternative way to represent standard tokens. In addition to keywords, there are two identifiers with special meaning, which may be used as names of objects or functions, but have special meaning in certain contexts. override (C++11) final (C++11) Also, all identifiers that contain a double underscore __ in any position and each identifier that begins with an underscore followed by an uppercase letter is always reserved and all identifiers that begin with an underscore are reserved for use as names in the global namespace. See identifiers for more details. The namespace std is used to place names of the standard C++ library. See Extending namespace std for the rules about adding names to it. The name posix is reserved for a future top-level namespace. The behavior is undefined if a program declares or defines anything in that namespace. (since C++11) The following tokens are recognized by the preprocessor when in context of a preprocessor directive: if elif else endif defined ifdef ifndef define undef include line error pragma The following tokens are recognized by the preprocessor outside the context of a preprocessor directive: When parsing an expression, an operator which is listed on some row of the table above with a precedence will be bound tighter (as if by parentheses) to its arguments than any operator that is listed on a row further below it with a lower precedence. For example, the expressions std::cout << a & b and *p++ are parsed as (std::cout << a) & b and *(p++), and not as std::cout << (a & b) or (*p)++. Operators that have the same precedence are bound to their arguments in the direction of their associativity. For example, the expression a = b = c is parsed as a = (b = c), and not as (a = b) = c because of right-to-left associativity of assignment, but a + b - c is parsed (a + b) - c and not a + (b - c) because of left-to-right associativity of addition and subtraction. Associativity specification is redundant for unary operators and is only shown for completeness: unary prefix operators always associate right-to-left (delete ++*p is delete(++(*p))) and unary postfix operators always associate left-to-right (a[1][2]++ is ((a[1])[2])++). Note that the associativity is meaningful for member access operators, even though they are grouped with unary postfix operators: a.b++ is parsed (a.b)++ and not a.(b++). Operator precedence is unaffected by operator overloading. Notes Precedence and associativity are compile-time concepts and are independent from order of evaluation, which is a runtime concept. The standard itself doesn't specify precedence levels. They are derived from the grammar. const_cast, static_cast, dynamic_cast, reinterpret_cast, typeid, sizeof..., noexcept and alignof are not included since they are never ambiguous. Some of the operators have alternate spellings (e.g., and for &&, or for ||, not for !, etc.). Relative precedence of the ternary conditional and assignment operators differs between C and C++: in C, assignment is not allowed on the right-hand side of a ternary conditional operator, so e = a < d a++ : a = d cannot be parsed. Many C compilers use a modified grammar where : has higher precedence than =, which parses that as e = ( ((a < d) (a++) : a) = d ) (which then fails to compile because : is never lvalue in C and = requires lvalue on the left). In C++, : and = have equal precedence and group right-to-left, so that e = a < d a++ : a = d parses as e = ((a < d) (a++) : (a = d)). See also Common operators assignment increment decrement arithmetic logical comparison member access other a = b a += b a -= b a *= b a /= b a %= b a &= b a |= b a ^= b a <<= b a >>= b ++a --a a++ a-- +a -a a + b a - b a * b a / b a % b ~a a & b a | b a ^ b a << b a >> b !a a && b a || b a == b a != b a < b a > b a <= b a >= b a[b] *a &a a->b a.b a->*b a.*b a(...) a, b : Special operators static_cast converts one type to another related type dynamic_cast converts within inheritance hierarchies const_cast adds or removes cv qualifiers reinterpret_cast converts type to unrelated type C-style cast converts one type to another by a mix of static_cast, const_cast, and reinterpret_cast new allocates memory delete deallocates memory sizeof queries the size of a type sizeof... queries the size of a parameter pack (since C++11) typeid queries the type information of a type noexcept checks if an expression can throw an exception (since C++11) alignof queries alignment requirements of a type (since C++11) Notes Of the octal escape sequences, 0 is the most useful because it represents the terminating null character in null-terminated strings. The new-line character n has special meaning when used in text mode I/O: it is converted to the OS-specific newline byte or byte sequence. Octal escape sequences have a limit of three octal digits, but terminate at the first character that is not a valid octal digit if encountered sooner. Hexadecimal escape sequences have no length limit and terminate at the first character that is not a valid hexadecimal digit. If the value represented by a single hexadecimal escape sequence does not fit the range of values represented by the character type used in this string literal (char, char16_t, char32_t, or wchar_t), the result is unspecified. A universal character name in a narrow string literal or a 16-bit string literal may map to more than one character, e.g. U0001f34c is 4 char code units in UTF-8 (xF0x9Fx8Dx8C) and 2 char16_t code units in UTF-16 (uD83CuDF4C)). The question mark escape sequence is used to prevent trigraphs from being interpreted inside string literals: a string such as g/ is compiled as , but if the second question mark is escaped, as in Void type void - type with an empty set of values. It is an incomplete type that cannot be completed (consequently, objects of type void are disallowed). There are no arrays of void, nor references to void. However, pointers to void and functions returning type void (procedures in other languages) are permitted. std::nullptr_t Boolean type bool - type, capable of holding one of the two values: true or false. Character types signed char - type for signed character representation. unsigned char - type for unsigned character representation. Also used to inspect object representations (raw memory). char - type for character representation which can be most efficiently processed on the target system (has the same representation and alignment as either signed char or unsigned char, but is always a distinct type). Multibyte characters strings use this type to represent code units. The character types are large enough to represent 256 different values (in order to be suitable for storing UTF-8 encoded data) (since C++14) wchar_t - type for wide character representation (see wide strings). Required to be large enough to represent any supported character code unit (32 bits on systems that support Unicode. A notable exception is Windows, where wchar_t is 16 bits) It has the same size, signedness, and alignment as one of the integral types, but is a distinct type. char16_t - type for UTF-16 character representation, required to be large enough to represent any UTF-16 code unit (16 bits). It has the same size, signedness, and alignment as std::uint_least16_t, but is a distinct type. char32_t - type for UTF-32 character representation, , required to be large enough to represent any UTF-32 code unit (32 bits). It has the same size, signedness, and alignment as std::uint_least32_t, but is a distinct type. (since C++11) Integer types int - basic integer type. The keyword int may be omitted if any of the modifiers listed below are used. If no length modifiers are present, it's guaranteed to have a width of at least 16 bits. However, on 32/64 bit systems it is almost exclusively guaranteed to have width of at least 32 bits (see below). Properties Floating-point types may support special values: infinity (positive and negative), see INFINITY the negative zero, -0.0. It compares equal to the positive zero, but is meaningful in some arithmetic operations, e.g. 1.0/0.0 == INFINITY, but 1.0/-0.0 == -INFINITY) not-a-number (NaN), which does not compare equal with anything (including itself). Multiple bit patterns represent NaNs, see std::nan, NAN. Note that C++ takes no special notice of signalling NaNs other than detecting their support by std::numeric_limits::has_signaling_NaN, and treats all NaNs as quiet. Real floating-point numbers may be used with arithmetic operators + - / * and various mathematical functions from cmath. Both built-in operators and library functions may raise floating-point exceptions and set errno as described in math_errhandling Floating-point expressions may have greater range and precision than indicated by their types, see FLT_EVAL_METHOD. Floating-point expressions may also be contracted, that is, calculated as if all intermediate values have infinite range and precision, see #pragma STDC FP_CONTRACT. Some operations on floating-point numbers are affected by and modify the state of the floating-point environment (most notably, the rounding direction) Implicit conversions are defined between real floating types and integer types. See Limits of floating point types and std::numeric_limits for additional details, limits, and properties of the floating-point types. Range of values The following table provides a reference for the limits of common numeric representations. As the C++ Standard allows any signed integer representation, the table gives both the minimum guaranteed requirements (which correspond to the limits of one's complement or sign-and-magnitude) and the limits of the most commonly used implementation, two's complement. All popular data models (including all of ILP32, LP32, LP64, LLP64) use two's complement representation, though.";
typedef unordered_map<string,int> M;
string clean(string w) {
int n=w.size();
for(int i=0; i<n; ++i) {
char c = w[i];
w[i] = tolower(c);
if (w[i] == toupper(c)) {
return w.substr(0,i);
}
}
return w;
}
double fun(int c) {
return pow(c, 0.2);
}
M create(string data, int K, double& cnt) {
istringstream iss(data);
string w;
M res;
while(iss>>w) {
w = clean(w);
int n=w.size();
for(int i=0; i+K <= n; ++i) {
res[w.substr(i, K)]++;
}
}
for(const auto& x: res) {
cnt += fun(x.second);
}
return res;
}
double eval(const M& m, double mc, const string& s, int K) {
int n=s.size();
double sum = 0;
for(int i=0; i+K <= n; ++i) {
string w = s.substr(i,K);
auto it = m.find(w);
if (it != m.end()) {
int c = it->second;
sum += fun(c);
}
}
// cout<<"eval "<<s<<" : "<<sum<<"/"<<mc<<" = "<<sum/mc<<'\n';
return sum / mc;
}
const int K=5;
double cs[K];
double ce[K];
M ms[K];
M me[K];
double weight[K];
int main() {
weight[1]=1;
for(int i=2; i<K; ++i) weight[i]=weight[i-1]*4;
for(int k=1; k<K; ++k) {
ms[k] = create(suomi, k, cs[k]);
me[k] = create(eng, k, ce[k]);
}
int t;
cin>>t;
while(t--) {
string s;
cin>>s;
double xs=0, xe=0;
for(int k=1; k<K; ++k) {
xs += weight[k] * eval(ms[k], cs[k], s, k);
xe += weight[k] * eval(me[k], ce[k], s, k);
}
cout<<(xs>xe ? "10-4" : "QAQ")<<'\n';
}
}
