Creació d'un BST diferència de dos BSTs X19540

Statement

html

Donada la classe dicc que permet gestionar diccionaris on només hi guardem claus úniques usant arbres binaris de cerca (BST), cal implementar el mètode

void diferencia(const dicc<Clau> &d2, dicc<Clau> &dr) const; // Pre: El diccionari dr està buit // Post: dr conté les claus de la diferència del p.i. amb d2

Les claus són del tipus Clau que admet una relació d’ordre total, és a dir, tenim una operació de comparació < entre claus.

Cal enviar a jutge.org la següent especificació de la classe dicc i la implementació del mètode dins del mateix fitxer. La resta de mètodes públics i privats ja estan implementats. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements n1 del diccionari del p.i. i nombre d’elements n2 del diccionari d2.

#include <iostream> using namespace std; typedef unsigned int nat; template <typename Clau> class dicc { public: // Constructora per defecte. Crea un diccionari buit. dicc(); // Destructora ~dicc(); // Insereix la clau k en el diccionari. Si ja hi era, no fa res. void insereix(const Clau &k); // Imprimeix els elements del diccionari ordenats de menor a major void print() const; // Retorna la mida del BST que implementa el diccionari nat mida() const; // Retorna l’altura del BST que implementa el diccionari nat altura() const; void diferencia(const dicc<Clau> &d2, dicc<Clau> &dr) const; // Pre: El diccionari dr està buit // Post: dr conté les claus de la diferència del p.i. amb d2 private: struct node { Clau _k; // Clau node* _esq; // fill esquerre node* _dret; // fill dret node(const Clau &k, node* esq = NULL, node* dret = NULL); }; node *_arrel; static void esborra_nodes(node* m); static node* insereix_bst(node *n, const Clau &k); static void print(node *n); static nat mida(node *n); static nat altura(node *n); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació dels mètodes públics i privats

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació del mètode diferencia (el que normalment estarien separats en els fitxers .hpp i .cpp).

Per testejar la classe disposes d’un programa principal que llegeix dos diccionaris d’enters, desprès crida el mètode diferencia i finalment mostra el contingut del diccionari amb la diferència dels dos diccionaris inicials. També s’indica si el BST del diccionari resultant està suficientment balancejat.

Entrada

L’entrada conté dues línies formades per seqüències d’enters, són els elements que tindran els dos diccionaris inicials.

Sortida

A la sortida apareixen ordenats i separats per espais, els elements del diccionari resultant que conté la diferència dels dos diccionaris inicials. A la segona línia apareix el text "BST poc balancejat" o "BST suficient balancejat", depenen de si l’altura del BST resultant supera o no min (mida, log₂(mida) * 10), sent mida el nombre de nodes de l’arbre resultant.

Observació

Només cal enviar l’especificació de la classe dicc, la implementació del mètode diferencia i el seu cost en funció del nombre d’elements n1 i n2 dels dos diccionaris inicials. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Primer cal crear un BST amb el resultat correcte. Posteriorment cal obtenir un BST més balancejat si no ho està suficientment. Hi ha diferents tècniques per aconseguir-ho, una d’elles és alternar de forma aleatòria l’ordre en que es recorren els BSTs inicials (esquerra-dreta o dreta-esquerra), et pot ser d’utilitat l’expressió rand() % 2 que simula el cara/creu d’una moneda llançada a l’aire, el seu resultat és 0 o 1.

Els primers tres exemples mostren la diferència de dos diccionaris buits o un de buit i un que no ho és.

Public test cases

Input

Output

BST suficient balancejat

Input

5 -3 8 2 -1 7 -7 -6

Output

-7 -6 -3 -1 2 5 7 8 
BST suficient balancejat

Input

 
7 -2 9 5 -3 2 -7

Output

BST suficient balancejat

Input

5 -3 8 2 -1 7 -7 -6
7 -2 9 5 -3 2 -7

Output

-6 -1 8 
BST suficient balancejat

Input

5 -5 -3 9 -9 2 -2 1 -1 7 -7 0 4 -4 8 -8 6
2 10 4 12 8 14 0 10 14 6

Output

-9 -8 -7 -5 -4 -3 -2 -1 1 5 7 9 
BST suficient balancejat

Input

-191 427 -13 -2 -11 353 10 -333 -85 -4763 400 1 -29 4 -3 3 33 39 573 -447 453 -4743 15 -2713 151 240 -4 29 -159 -1 481 113 -31 250 2 262 273 4853 443 483 143 99 -81 -4313 49 -430 1033 -23 -33 -30 -494 48 -1663 -345 403 -59 -32 457 43 -44 -473 433 -399 -19 4753 -9 30 103 474 16 233 20 -233 473 -25 -405 -203 -215 -41 -119 -442 -15 40 489 -4543 27 223 53 14 -43 -213 -171 -40 133 9 36 -492 -73 -47 -64 423 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216
-440 -330 -4 3 -113 2 -1 60 44 17 -12 -16 -2 351 20 -3 -10 23 -280 29 52 340 438 142 229 -59 -20 493 4 -49 -9 189 43 -32 59 -392 49 303 1 15 158 -84 41 -13 22 42 -211 -30 -250 9 44 -212 -401 -109 -342 231 193 40 32 -141 13 -19 400 41 -36 -333 -29 -43 47 219 179 -21 -75 -190 173 16 -23 -25 -33 -129 -24 11 -15 423 12 -4733 -40 61 74 -90 -414 443 -35 -370 19 -83 -42 325 -5 -461 -22 -39 -329 -182 114 6 -421 -45 291 -46 5 141 -67 -380 -254 130 62 -328 212 449 -351 -1043 90 -3263 -8 454 -34 435 220 323 -149 -17 -276 -4623 96 459 -31 -220 282 24 -126 -399 -189 359 73 119 440 -493 341 -441 -143 -420 -203 -463 483 -3833 -379 102 45 379 370 -181 -7 -26 -63 14 -293 -73 213 -263 413 -152 482 10 280 437 -183 -14 -6 99 -209 -233 181 1983 331 195 -450 -480 -92 -53 -415 1023 -403 434 140 245 27 -257 361 -4453 439 375 186 2823 -100 279 35 -99 104 -323 883 471 -122 243 465 210 39 -3433 -443 36 1443 63 7 2849 322 -472 422 -230 -79 3313 123 363 34 38 147 409 495 -156 -2313 -153 333 -310 -1293 473 -243 -2749 26 91 -2063 30 -242 -413 -418 -93 25 50 -101 -2303 -361 -353 -273 -341 374 3273 429 103 -321 -473 447 4423 33 283 -4913 -2203 4799 -263 431 21 -270 -106 410 403 53 -322 4493 343 479 390 -55 -269 -124 132 230 -383 -70 563 -411 384 -283 -3963 3483 2163 252 -489 -470 -4593 -27 415 623 -179 -299 1773 101 -344 -315 -483 -4333 -97 -471 46 593 470 -274 -4983 311 -873 -281 1123 -38 329 -11 3283 3003 2333 -81 89 -324 -389 -1343 -2923 -343 -1559 4343 -260 199 -4113 381 -432 4383 -336 -4133 402 -4979 -239 -1279 -114 1833 -423 113 -163 293 -133 779 1633 -191 249 -234 -253 139 -303 -444 1213 -300 -3293 -469 -284 -2769 2043 261 366 -246 -37 723 269 -481 -3403 241 -47 -175 233 4743 -4473 1363 150 -1673 204 -266 477 -252 -115 372 421 330 -393 -123 -222 190 18 121 153 1569 -4033 -319 2123 533 79 404 334 -275 893 -28 -61 349 -653 -200 -2103 -1483 -249 433 -60 183 543 460 203 -395 4813 3053 95 -3063 -430 3093 -117 -237 453 159 -180 -439 81 -433 -4273 4363 463 1583 273 -479 120 4523 -1433 -308 1803 -373 3443 3593 4303 143 -289 294 336 -199 -82 240 344 3763 -491 373 -18 1643 3119 180 -314 3343 4279 125 -374 1723 170 2983 270 -1553 -131 360 2433 174 -69 -169 -573 -1013 442 426 420 1853 94 -1593 -451 -412 492 1873 156 -304 -240 37 109 185 3463 3823 112 1159 -453 -3373 -160 -279239 -3693 419 -378 -130 145 -184 1663 -1063 93 -4413 -2683 124 1433 -2143 490 4143 -390 -384 -449 -3033 -4543 2393 301 -206 163 335 451 -1643 -264 67 160 4613 393 369 -196 -485 -391 -210 1113 424 485 1423 -219 -394 253 1289 -2193 462 -409 -2423 1413 214 55 -2979 -1223 3423 -2443 -173 313 -142 2603 162 371 -282 226 221 -144 -2033 484 3713 4659 -339 -185 -176 271 3473 -139 -903 2153 129 111 4463 -350 -51 -377 2869 110 -3383 209 -1353 309 -352 259 92 -523 1249 4033 -1759 -1753 227 -385 4833 683 -386 -4089 151 -3129 1383 1703 276 -4163 208 -356 -221 1373 -2219 467 4733 223 350 -2963 383 232 -434 -78 1483 70 133 -3239 -112 -192 -103 -159 -349 194 -452 3293 -255 392 -464 354 -119 290 -943 -309 4359 -162 -261 339 430 353 3673 -235 3123 -340 -2399 -2393 -410 -245 -1079 843 -187 394 4223 -793 4723 184 -54 -402 -2129 254 -292 299 -223 152 763 -362 2993 -360 -3339 -359 1963 4453 8 3149 2449 -2113 -1973 2209 77 -823 -3743 4763 -365 -66 2973 -86 -1309 3223 285 48 -863 2553 175 -405 -487 1903 873 -127 -1083 -174 -80 -85 -446 -2243 168 -332 889 -313 -193 310 256 -683 -2003 -4223 -166 376 346 -983 -2183 100 -4283 -201 -4783 -484 -4909 -366 -2763 -334 65 4739 83 -91 3573 -3823 -52 1473 -1189 2673 -121 -1583 4273 -4523 28 236 405 80 1819 487 72 122 2119 -267 -663 -198 -312 171 -347 337 191 300 743 -4993 -2893 -140 202 275 3643 -2043 -94 -3423 -425 -202 -478 -613 320 362 -476 3709 -225 -95 3883 131 3303 -204 -294 2803 -229 693 446 -354 211 2753 -679 -110 321 367 -241 -4583 -71 -893 -513 -424 -404 3143 441 -291 1273 -2719 2853 -4943 3333 456 -3203 -1139 -104 3323 -161 1193 4013 260 -228 -262 -1543 -1853 86 382 -1449 -2983 -4953 302 4993 -3283 -2333 -442 272 469 -1339 -3453 -3643 -456 -4529 -72 1293 -4503 -4773 115 1783 -4653 -381 391 472 4893 -4719 -455 -316 -301 -2433 3243 -431 3369 -3889 -4713 -733 75 -3253 -326 -400 -306 224 793 1203 -1163 476 -2713 -164 -3953 2793 324 -4353 2023 -703 250 2423 225 -89 481 408 823 2653 3603 913 182 306 -2883 -271 -2083 -64 -4883 -763 -2509 494 703 933 -459 -2619 2573 317 2083 -490 -50 -2263 753 -298 251 461 4393 -2233 -1423 82 167 235 3633 -3363 679 -603 -1253 -417 312 813 200 1459 -2023 -3473 4793 1843 -2799 155 -416 69 2293 169 1893 783 -48 -244 -2533 -132 274 455 1173 395 1513 295 -1883 318 3103 2669 -4513 289 -125 -460 -3803 281 164 -3673 237 450 116 -277 -4263 107 176 314 -492 -1033 1763 357 -226 -2539 -4683 2203 -2253 -633 -3029 425 51 4873 -364 -406 1449 192 -2173 -1443 -435 416 196 432 2359 -232 -468 264 217 97 -3243 411 -1933 -214 161 4123 4909 -1743 3913 287 126 -3379 1523 -2943 4263 -2553 242 399 -369 -3533 -272 -296 1233 -120 -224 3963 -4083 3769 4399 445 2259 3193 -357 -2239 4413 262 -331 64 -719 3419 3893 2693 -302 -3309 -3593 177 -116 -286 -372 2763 -4323 -172 1323 -375 973 -355 -1943 3513 -290 1299 -4723 -3193 569 288 284 -171 -1803 -3983 76 -2673 -2903 -376 84 117 -76 206 993 4353 414 -205 -3413 -1199 999 -1873 -1779 427 -4093 1043 -3023 -3213 -251 -407 -165 -454 1333 -543 1573 643 4069 -2009 -77 -445 -429 345 365 -268 -155 255 -265 266 -1993 863 2529 -482 -1173 -2073 -150 1353 342 -2053 2863 -1413 -2493 -4613 172 4443 -2733 2033 -749 2383 3653 -151 2723 -475 144 -154 -396 188 364 315 4113 -819 292 -465 -146 56 -191 427 -13 -2 -11 353 10 -333 -85 1 -29 4 -3 3 33 39 15 -4 29 -159 -1 -87 -81 -64 -51 -47 -44 -41 -37 -27 -11 18 31 46 48

Output

-4963 -4919 -4903 -4893 -4889 -4853 -4833 -4803 -4763 -4753 -4749 -4743 -4643 -4633 -4553 -4533 -4463 -4439 -4433 -4363 -4313 -4293 -4253 -4233 -4203 -4153 -4149 -4123 -4063 -4059 -4053 -4003 -3993 -3973 -3943 -3933 -3923 -3919 -3893 -3873 -3843 -3813 -3773 -3753 -3733 -3723 -3713 -3669 -3663 -3653 -3613 -3609 -3579 -3563 -3553 -3513 -3483 -3399 -3393 -3353 -3329 -3303 -3279 -3273 -3249 -3183 -3173 -3153 -3143 -3123 -3113 -3103 -3089 -3083 -3073 -3069 -3003 -2973 -2919 -2913 -2873 -2833 -2819 -2813 -2789 -2783 -2723 -2679 -2653 -2643 -2623 -2593 -2563 -2543 -2523 -2513 -2503 -2483 -2463 -2413 -2403 -2383 -2373 -2343 -2329 -2323 -2319 -2309 -2273 -2269 -2213 -2189 -2163 -2153 -2123 -2093 -2049 -2029 -1983 -1963 -1953 -1929 -1923 -1909 -1863 -1823 -1819 -1813 -1789 -1749 -1713 -1693 -1683 -1663 -1653 -1633 -1623 -1523 -1493 -1463 -1453 -1393 -1333 -1323 -1299 -1283 -1273 -1263 -1216 -1203 -1153 -1143 -1129 -1123 -1113 -1073 -1053 -993 -929 -913 -883 -879 -833 -783 -713 -699 -693 -643 -623 -589 -563 -533 -509 -499 -496 -495 -494 -488 -486 -474 -462 -457 -447 -437 -436 -427 -422 -419 -382 -371 -363 -358 -346 -345 -327 -325 -320 -311 -305 -295 -288 -285 -279 -259 -256 -236 -231 -217 -216 -215 -213 -197 -195 -186 -170 -167 -145 -137 -136 -135 -111 -107 -105 -96 -74 -65 -62 54 57 66 71 88 105 134 135 136 137 149 154 157 165 201 205 215 222 228 234 239 244 247 257 263 265 278 297 304 305 319 326 332 348 352 355 356 358 380 386 387 389 398 401 406 412 444 452 457 464 474 475 480 489 491 496 499 519 523 529 573 669 673 719 869 923 963 983 1009 1033 1073 1153 1163 1263 1303 1313 1343 1403 1493 1543 1553 1603 1653 1683 1713 1719 1733 1753 1793 1813 1839 1863 1883 1943 1953 1989 1993 2003 2013 2099 2113 2133 2143 2223 2263 2269 2273 2283 2299 2303 2313 2343 2353 2413 2453 2463 2563 2613 2623 2633 2683 2733 2743 2769 2833 2873 2899 2903 2913 2923 2933 3023 3043 3063 3083 3113 3133 3173 3203 3213 3219 3233 3253 3263 3279 3353 3409 3453 3503 3523 3533 3563 3583 3623 3703 3723 3733 3743 3753 3773 3779 3793 3833 3843 3853 3863 3873 3903 3923 3943 3973 3983 3993 4053 4063 4133 4149 4163 4173 4203 4213 4233 4243 4249 4253 4293 4313 4349 4373 4379 4503 4543 4549 4553 4563 4573 4623 4643 4649 4653 4663 4683 4693 4709 4753 4769 4773 4803 4809 4843 4853 4913 4933 4943 4953 4963 
BST suficient balancejat

Input

-191 427 -13 -2 -11 353 10 -333 -85 -4763 400 1 -29 4 -3 3 33 39 573 -447 453 -4743 15 -2713 151 240 -4 29 -159 -1 481 113 -31 250 2 262 273 4853 443 483 143 99 -81 -4313 49 -430 1033 -23 -33 -30 -494 48 -1663 -345 403 -59 -32 457 43 -44 -473 433 -399 -19 4753 -9 30 103 474 16 233 20 -233 473 -25 -405 -203 -215 -41 -119 -442 -15 40 489 -4543 27 223 53 14 -43 -213 -171 -40 133 9 36 -492 -73 -47 -64 423 -1223 382 703 201 -130 25 23 -27 -163 3193 492 18 1123 44 -189 -10 -312 -353 -313 206 179 199 169 -6 -37 4549 35 5 1813 -470 19 -423 -414 -39 93 -21 263 373 45 -266 -2819 -2433 -51 -20 2873 294 -14 -4653 1763 -793 -443 12 -490 -461 -410 719 -362 22 -103 -3353 -223 593 -325 -302 191 -431 -17 120 -24 163 -3069 47 173 -322 -101 -3433 46 13 392 -475 172 -99 -380 -87 -433 -439 38 4933 -122 211 459 -319 31 255 -280 -26 295 -4803 42 -310 -36 -479 -271 -411 -362 333 -166 -283 -3243 -35 237 162 369 -469 -4463 11 -360 4543 -60 100 380 -424 869 -179 -5 -493 -323 3213 -45 21 2633 -46 3523 -420 102 -320 -92 83 -219 -499 -4363 -183 231 -236 -150 -86 383 -355 94 -403 89 161 -245 278 4833 -2543 37 -22 6 -42 230 -131 -391 204 41 -263 3943 80 -169 -393 183 -3253 51 461 -149 -89 3233 24 -109 -1013 34 449 499 4349 17 -3943 -300 -210 26 281 -342 -229 -432 1023 2113 -260 -49 440 1963 -369 -273 129 -28 309 302 376 -913 -220 -274 -226 -4893 203 360 -270 -195 342 391 -82 -141 -4063 -382 -1129 -400 -346 -390 -489 215 282 -16 2133 -440 -2193 351 252 421 -261 401 -38 243 -112 4913 170 999 189 413 -100 -573 -3643 -463 -407 -12 2033 208 -291 -422 -409 -279 -193 -133 519 -330 -239 387 1009 -143 270 4273 393 303 472 225 -435 -450 109 2933 3733 -184 -4633 -48 490 2003 2353 283 430 -4263 241 4163 -4533 236 -365 4253 4063 -4553 -361 -173 -153 4573 -481 1683 493 7 284 381 3293 253 356 432 62 -241 434 123 -84 1313 119 180 389 150 -2493 261 359 140 195 -1543 -383 -72 -395 1363 -2233 -129 299 4843 -4033 -299 4149 -379 -61 450 2563 2413 -372 402 352 -91 683 480 469 -491 -2463 1303 -340 363 -170 -436 -160 -2483 91 -482 -370 305 -243 -4643 121 2849 455 293 3263 3243 1993 4813 -135 372 -93 2333 181 -373 -321 -50 -4919 -343 -3723 313 -1983 110 -1043 -34 -324 -8 3763 -253 4243 131 -3393 -69 1203 -3613 4233 200 79 -2723 395 463 350 -893 -1923 -192 -354 3713 -1693 343 4653 -311 193 -113 -480 -4253 32 -413 254 -196 4873 -392 -341 -351 4249 2453 -3453 2343 73 3853 235 -453 160 220 171 -161 -107 -3773 -217 -74 -1743 -2813 330 -180 -182 -80 -4433 -339 139 -120 291 -3113 -65 280 361 -363 149 -110 -1813 3623 154 -653 -132 -474 167 3053 -415 -123 269 -294 275 184 260 1233 370 -1483 379 339 153 -3473 -1143 913 4453 2299 55 -1423 2013 -293 -371 341 3113 -2113 229 441 -63 -485 92 311 4723 3779 4379 -4623 239 -142 -429 1483 323 -401 -2373 4663 1173 314 135 4503 320 409 -334 -1203 -105 -452 -4833 -199 -421 460 -2163 -543 304 8 479 -1063 -394 355 -221 -2309 -83 -533 -329 3673 2913 219 145 141 -259 -164 -79 -2049 210 -384 -3553 272 -240 1713 190 963 -349 112 -145 -234 257 159 334 -244 -1173 4649 -2523 -2329 301 70 289 3023 -151 -350 142 -465 -2923 2833 -444 -1553 -1623 1513 -3003 72 -381 4553 292 -364 244 -483 415 -419 -3693 -124 -1823 1839 -18 279 63 -3993 2573 192 1703 74 111 3793 -267 -52 -2053 -4123 -4153 130 -4683 3833 399 -4963 -4889 -115 410 329 -1633 259 -139 471 -663 -53 -455 114 3753 76 -3843 249 414 1403 -7 -275 -1263 743 50 -232 3983 -3733 4293 1263 1293 3219 -309 -389 -214 3603 2283 209 344 1543 -3063 -484 -71 274 -2323 673 358 -451 -290 3973 122 -3923 -3273 152 1953 -2973 -4913 -1053 -225 439 -783 -1299 405 3133 -3663 2463 297 -3193 65 -425 2693 2899 452 256 319 226 -3153 -272 -336 -54 470 484 -2383 3883 52 -303 116 -235 371 -4149 -487 -359 4373 -292 4133 -2263 -1333 -96 419 349 -993 1793 -76 -257 221 -3173 -264 3043 643 429 -2733 -211 271 933 -231 -3919 420 -4439 -1863 -256 -3103 -4203 -3803 1573 -366 -464 -4353 -344 494 -70 -106 -2799 1653 -190 -4293 115 82 1433 28 -1683 157 -3413 -643 -434 54 -201 174 59 -3579 125 60 -2903 213 -513 155 326 -2123 -269 354 165 -496 101 234 -254 175 -216 -3143 -304 1523 1883 3279 -306 2673 2753 -285 2263 -563 -137 242 -282 1299 97 442 -347 331 -3483 4773 324 337 -460 -154 4563 4383 -209 105 366 -2943 310 -327 69 -3933 462 4943 -62 -2893 424 -3653 2669 -242 993 -358 -230 437 -140 -181 843 -249 -289 -2029 232 -284 435 -2313 533 3723 -1283 -1113 -2393 -268 398 390 -3329 1603 2269 -1653 -2623 4683 464 1153 4963 1873 315 -863 3453 -3513 251 -1073 186 -1393 3103 290 -252 -4059 406 -251 132 -929 -2513 2683 -2503 136 1753 -386 3903 147 176 265 -441 3503 3703 -1993 64 -2563 -873 2623 -472 456 523 124 -509 2223 -454 -1749 364 411 -352 -2043 1333 2769 -404 -2833 164 1989 543 4623 224 61 431 336 4363 212 -3563 -2303 222 -943 4223 386 -883 -200 -3713 -111 84 -265 -3249 196 3483 2393 -2443 3873 90 -1523 -2343 -4053 -457 -4883 -1453 -1353 -2213 -4233 -308 3303 1773 475 3353 -2913 1863 -1463 -2679 348 -4223 446 -172 -459 4203 2313 -3983 -2553 -3303 444 422 -155 247 -833 -1909 194 -2653 137 4803 -2423 753 -1433 -1713 1553 4709 3563 -374 -3753 -246 -295 -4719 3203 -375 144 287 374 451 3273 -3669 3743 182 312 4809 -763 2273 485 4143 -4283 447 -3123 264 375 -146 -449 -2789 66 -4333 3993 -2919 -1293 -2023 404 -3279 -412 4313 -2643 71 923 345 3633 1163 -1253 -4593 214 -4753 4793 -174 -281 1493 -1153 -2593 -1493 -713 -983 -3089 1833 3533 3143 -3183 1733 340 973 4769 3323 491 -1873 4643 -167 3843 3083 -94 300 -3083 -2273 4763 -1929 202 -162 156 185 -104 -437 67 -288 4173 -90 -446 -693 4053 -2983 -4783 -305 1723 723 -488 2303 454 3063 2993 -2763 4893 -1123 496 -3813 2143 -2103 -152 -2873 4693 -456 482 2853 -3973 -2783 -116 4953 2733 -1953 -2269 205 1983 3863 -4853 3463 1343 276 -2403 529 -144 -2413 2923 -4323 3923 -4749 3253 563 57 3573 -136 -3893 -699 134 -1323 -3873 -495 3343 -1963 3409 -4903 -1273 -3673 -589 -623 -121 983 669 228 -3073 -222 335 3173 1073 -427 -2319 -4993 -224 321 81 3583 332 4733 -1789 -2083 -486 2099 -471 1113 3773 -879 88 4113 -77 -3399 -3609 -2153 -186 3419 -2093 -462 1943 2743 -3963 412 -1819 4213 -197 322 2903 1719 -2189 2613 -4003 -1216
-440 -330 -4 3 -113 2 -1 60 44 17 -12 -16 -2 351 20 -3 -10 23 -280 29 52 340 438 142 229 -59 -20 493 4 -49 -9 189 43 -32 59 -392 49 303 1 15 158 -84 41 -13 22 42 -211 -30 -250 9 44 -212 -401 -109 -342 231 193 40 32 -141 13 -19 400 41 -36 -333 -29 -43 47 219 179 -21 -75 -190 173 16 -23 -25 -33 -129 -24 11 -15 423 12 -4733 -40 61 74 -90 -414 443 -35 -370 19 -83 -42 325 -5 -461 -22 -39 -329 -182 114 6 -421 -45 291 -46 5 141 -67 -380 -254 130 62 -328 212 449 -351 -1043 90 -3263 -8 454 -34 435 220 323 -149 -17 -276 -4623 96 459 -31 -220 282 24 -126 -399 -189 359 73 119 440 -493 341 -441 -143 -420 -203 -463 483 -3833 -379 102 45 379 370 -181 -7 -26 -63 14 -293 -73 213 -263 413 -152 482 10 280 437 -183 -14 -6 99 -209 -233 181 1983 331 195 -450 -480 -92 -53 -415 1023 -403 434 140 245 27 -257 361 -4453 439 375 186 2823 -100 279 35 -99 104 -323 883 471 -122 243 465 210 39 -3433 -443 36 1443 63 7 2849 322 -472 422 -230 -79 3313 123 363 34 38 147 409 495 -156 -2313 -153 333 -310 -1293 473 -243 -2749 26 91 -2063 30 -242 -413 -418 -93 25 50 -101 -2303 -361 -353 -273 -341 374 3273 429 103 -321 -473 447 4423 33 283 -4913 -2203 4799 -263 431 21 -270 -106 410 403 53 -322 4493 343 479 390 -55 -269 -124 132 230 -383 -70 563 -411 384 -283 -3963 3483 2163 252 -489 -470 -4593 -27 415 623 -179 -299 1773 101 -344 -315 -483 -4333 -97 -471 46 593 470 -274 -4983 311 -873 -281 1123 -38 329 -11 3283 3003 2333 -81 89 -324 -389 -1343 -2923 -343 -1559 4343 -260 199 -4113 381 -432 4383 -336 -4133 402 -4979 -239 -1279 -114 1833 -423 113 -163 293 -133 779 1633 -191 249 -234 -253 139 -303 -444 1213 -300 -3293 -469 -284 -2769 2043 261 366 -246 -37 723 269 -481 -3403 241 -47 -175 233 4743 -4473 1363 150 -1673 204 -266 477 -252 -115 372 421 330 -393 -123 -222 190 18 121 153 1569 -4033 -319 2123 533 79 404 334 -275 893 -28 -61 349 -653 -200 -2103 -1483 -249 433 -60 183 543 460 203 -395 4813 3053 95 -3063 -430 3093 -117 -237 453 159 -180 -439 81 -433 -4273 4363 463 1583 273 -479 120 4523 -1433 -308 1803 -373 3443 3593 4303 143 -289 294 336 -199 -82 240 344 3763 -491 373 -18 1643 3119 180 -314 3343 4279 125 -374 1723 170 2983 270 -1553 -131 360 2433 174 -69 -169 -573 -1013 442 426 420 1853 94 -1593 -451 -412 492 1873 156 -304 -240 37 109 185 3463 3823 112 1159 -453 -3373 -160 -279239 -3693 419 -378 -130 145 -184 1663 -1063 93 -4413 -2683 124 1433 -2143 490 4143 -390 -384 -449 -3033 -4543 2393 301 -206 163 335 451 -1643 -264 67 160 4613 393 369 -196 -485 -391 -210 1113 424 485 1423 -219 -394 253 1289 -2193 462 -409 -2423 1413 214 55 -2979 -1223 3423 -2443 -173 313 -142 2603 162 371 -282 226 221 -144 -2033 484 3713 4659 -339 -185 -176 271 3473 -139 -903 2153 129 111 4463 -350 -51 -377 2869 110 -3383 209 -1353 309 -352 259 92 -523 1249 4033 -1759 -1753 227 -385 4833 683 -386 -4089 151 -3129 1383 1703 276 -4163 208 -356 -221 1373 -2219 467 4733 223 350 -2963 383 232 -434 -78 1483 70 133 -3239 -112 -192 -103 -159 -349 194 -452 3293 -255 392 -464 354 -119 290 -943 -309 4359 -162 -261 339 430 353 3673 -235 3123 -340 -2399 -2393 -410 -245 -1079 843 -187 394 4223 -793 4723 184 -54 -402 -2129 254 -292 299 -223 152 763 -362 2993 -360 -3339 -359 1963 4453 8 3149 2449 -2113 -1973 2209 77 -823 -3743 4763 -365 -66 2973 -86 -1309 3223 285 48 -863 2553 175 -405 -487 1903 873 -127 -1083 -174 -80 -85 -446 -2243 168 -332 889 -313 -193 310 256 -683 -2003 -4223 -166 376 346 -983 -2183 100 -4283 -201 -4783 -484 -4909 -366 -2763 -334 65 4739 83 -91 3573 -3823 -52 1473 -1189 2673 -121 -1583 4273 -4523 28 236 405 80 1819 487 72 122 2119 -267 -663 -198 -312 171 -347 337 191 300 743 -4993 -2893 -140 202 275 3643 -2043 -94 -3423 -425 -202 -478 -613 320 362 -476 3709 -225 -95 3883 131 3303 -204 -294 2803 -229 693 446 -354 211 2753 -679 -110 321 367 -241 -4583 -71 -893 -513 -424 -404 3143 441 -291 1273 -2719 2853 -4943 3333 456 -3203 -1139 -104 3323 -161 1193 4013 260 -228 -262 -1543 -1853 86 382 -1449 -2983 -4953 302 4993 -3283 -2333 -442 272 469 -1339 -3453 -3643 -456 -4529 -72 1293 -4503 -4773 115 1783 -4653 -381 391 472 4893 -4719 -455 -316 -301 -2433 3243 -431 3369 -3889 -4713 -733 75 -3253 -326 -400 -306 224 793 1203 -1163 476 -2713 -164 -3953 2793 324 -4353 2023 -703 250 2423 225 -89 481 408 823 2653 3603 913 182 306 -2883 -271 -2083 -64 -4883 -763 -2509 494 703 933 -459 -2619 2573 317 2083 -490 -50 -2263 753 -298 251 461 4393 -2233 -1423 82 167 235 3633 -3363 679 -603 -1253 -417 312 813 200 1459 -2023 -3473 4793 1843 -2799 155 -416 69 2293 169 1893 783 -48 -244 -2533 -132 274 455 1173 395 1513 295 -1883 318 3103 2669 -4513 289 -125 -460 -3803 281 164 -3673 237 450 116 -277 -4263 107 176 314 -492 -1033 1763 357 -226 -2539 -4683 2203 -2253 -633 -3029 425 51 4873 -364 -406 1449 192 -2173 -1443 -435 416 196 432 2359 -232 -468 264 217 97 -3243 411 -1933 -214 161 4123 4909 -1743 3913 287 126 -3379 1523 -2943 4263 -2553 242 399 -369 -3533 -272 -296 1233 -120 -224 3963 -4083 3769 4399 445 2259 3193 -357 -2239 4413 262 -331 64 -719 3419 3893 2693 -302 -3309 -3593 177 -116 -286 -372 2763 -4323 -172 1323 -375 973 -355 -1943 3513 -290 1299 -4723 -3193 569 288 284 -171 -1803 -3983 76 -2673 -2903 -376 84 117 -76 206 993 4353 414 -205 -3413 -1199 999 -1873 -1779 427 -4093 1043 -3023 -3213 -251 -407 -165 -454 1333 -543 1573 643 4069 -2009 -77 -445 -429 345 365 -268 -155 255 -265 266 -1993 863 2529 -482 -1173 -2073 -150 1353 342 -2053 2863 -1413 -2493 -4613 172 4443 -2733 2033 -749 2383 3653 -151 2723 -475 144 -154 -396 188 364 315 4113 -819 292 -465 -146 56 -191 427 -13 -2 -11 353 10 -333 -85 1 -29 4 -3 3 33 39 15 -4 29 -159 -1 -87 -81 -64 -51 -47 -44 -41 -37 -27 -11 18 31 46 48

Output

-4963 -4919 -4903 -4893 -4889 -4853 -4833 -4803 -4763 -4753 -4749 -4743 -4643 -4633 -4553 -4533 -4463 -4439 -4433 -4363 -4313 -4293 -4253 -4233 -4203 -4153 -4149 -4123 -4063 -4059 -4053 -4003 -3993 -3973 -3943 -3933 -3923 -3919 -3893 -3873 -3843 -3813 -3773 -3753 -3733 -3723 -3713 -3669 -3663 -3653 -3613 -3609 -3579 -3563 -3553 -3513 -3483 -3399 -3393 -3353 -3329 -3303 -3279 -3273 -3249 -3183 -3173 -3153 -3143 -3123 -3113 -3103 -3089 -3083 -3073 -3069 -3003 -2973 -2919 -2913 -2873 -2833 -2819 -2813 -2789 -2783 -2723 -2679 -2653 -2643 -2623 -2593 -2563 -2543 -2523 -2513 -2503 -2483 -2463 -2413 -2403 -2383 -2373 -2343 -2329 -2323 -2319 -2309 -2273 -2269 -2213 -2189 -2163 -2153 -2123 -2093 -2049 -2029 -1983 -1963 -1953 -1929 -1923 -1909 -1863 -1823 -1819 -1813 -1789 -1749 -1713 -1693 -1683 -1663 -1653 -1633 -1623 -1523 -1493 -1463 -1453 -1393 -1333 -1323 -1299 -1283 -1273 -1263 -1216 -1203 -1153 -1143 -1129 -1123 -1113 -1073 -1053 -993 -929 -913 -883 -879 -833 -783 -713 -699 -693 -643 -623 -589 -563 -533 -509 -499 -496 -495 -494 -488 -486 -474 -462 -457 -447 -437 -436 -427 -422 -419 -382 -371 -363 -358 -346 -345 -327 -325 -320 -311 -305 -295 -288 -285 -279 -259 -256 -236 -231 -217 -216 -215 -213 -197 -195 -186 -170 -167 -145 -137 -136 -135 -111 -107 -105 -96 -74 -65 -62 54 57 66 71 88 105 134 135 136 137 149 154 157 165 201 205 215 222 228 234 239 244 247 257 263 265 278 297 304 305 319 326 332 348 352 355 356 358 380 386 387 389 398 401 406 412 444 452 457 464 474 475 480 489 491 496 499 519 523 529 573 669 673 719 869 923 963 983 1009 1033 1073 1153 1163 1263 1303 1313 1343 1403 1493 1543 1553 1603 1653 1683 1713 1719 1733 1753 1793 1813 1839 1863 1883 1943 1953 1989 1993 2003 2013 2099 2113 2133 2143 2223 2263 2269 2273 2283 2299 2303 2313 2343 2353 2413 2453 2463 2563 2613 2623 2633 2683 2733 2743 2769 2833 2873 2899 2903 2913 2923 2933 3023 3043 3063 3083 3113 3133 3173 3203 3213 3219 3233 3253 3263 3279 3353 3409 3453 3503 3523 3533 3563 3583 3623 3703 3723 3733 3743 3753 3773 3779 3793 3833 3843 3853 3863 3873 3903 3923 3943 3973 3983 3993 4053 4063 4133 4149 4163 4173 4203 4213 4233 4243 4249 4253 4293 4313 4349 4373 4379 4503 4543 4549 4553 4563 4573 4623 4643 4649 4653 4663 4683 4693 4709 4753 4769 4773 4803 4809 4843 4853 4913 4933 4943 4953 4963 
BST suficient balancejat

Information

Author: Jordi Esteve
Language: Catalan
Official solutions: C++
User solutions: C++