Codigo-C.com.ar

Problemas ACM – Volumen I – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen I:

• 100 – The 3n + 1 problem: Enunciado
• 101 – The Blocks Problem: Enunciado
• 102 – Ecological Bin Packing: Enunciado
• 103 – Stacking Boxes: Enunciado
• 104 – Arbitrage: Enunciado
• 105 – The Skyline Problem: Enunciado
• 106 – Fermat vs. Pythagoras: Enunciado
• 107 – The Cat in the Hat: Enunciado
• 108 – Maximum Sum: Enunciado
• 109 – SCUD Busters: Enunciado
• 110 – Meta-Loopless Sorts: Enunciado
• 111 – History Grading: Enunciado
• 112 – Tree Summing: Enunciado
• 113 – Power of Cryptography: Enunciado
• 114 – Simulation Wizardry: Enunciado
• 115 – Climbing Trees: Enunciado
• 116 – Unidirectional TSP: Enunciado
• 117 – The Postal Worker Rings Once: Enunciado
• 118 – Mutant Flatworld Explorers: Enunciado
• 119 – Greedy Gift Givers: Enunciado
• 120 – Stacks of Flapjacks: Enunciado
• 121 – Pipe Fitters: Enunciado
• 122 – Trees on the level: Enunciado
• 123 – Searching Quickly: Enunciado
• 124 – Following Orders: Enunciado
• 125 – Numbering Paths: Enunciado
• 126 – The Errant Physicist: Enunciado
• 127 – ”Accordian” Patience: Enunciado
• 128 – Software CRC: Enunciado
• 129 – Krypton Factor: Enunciado
• 130 – Roman Roulette: Enunciado
• 131 – The Psychic Poker Player: Enunciado
• 132 – Bumpy Objects: Enunciado
• 133 – The Dole Queue: Enunciado
• 134 – Loglan-A Logical Language: Enunciado
• 135 – No Rectangles: Enunciado
• 136 – Ugly Numbers: Enunciado
• 137 – Polygons: Enunciado
• 138 – Street Numbers: Rectangles and Circles: Enunciado
• 139 – Telephone Tangles: Rectangles, Circles, and Triangles: Enunciado
• 140 – Bandwidth: Enunciado
• 141 – The Spot Game: Enunciado
• 142 – Mouse Clicks: Enunciado
• 143 – Orchard Trees: Enunciado
• 144 – Student Grants: Enunciado
• 145 – Gondwanaland Telecom: Enunciado
• 146 – ID Codes: Enunciado
• 147 – Dollars: Enunciado
• 148 – Anagram checker: Enunciado
• 151 – Power Crisis: Enunciado
• 152 – Tree’s a Crowd: Enunciado
• 153 – Permalex: Enunciado
• 154 – Recycling: Enunciado
• 155 – All Squares: Enunciado
• 156 – Ananagrams: Enunciado
• 159 – Word Crosses : Enunciado
• 160 – Factors and Factorials: Enunciado
• 161 – Traffic Lights: Enunciado
• 162 – Beggar My Neighbour: Enunciado
• 164 – String Computer: Enunciado
• 165 – Stamps: Enunciado
• 166 – Making Change: Enunciado
• 167 – The Sultan’s Successors: Enunciado
• 168 – Theseus and the Minotaur: Enunciado
• 170 – Clock Patience: Enunciado
• 172 – Calculator Language: Enunciado
• 183 – Bit Maps: Enunciado
• 184 – Laser Lines: Enunciado
• 186 – Trip Routing: Enunciado
• 187 – Transaction Processing: Enunciado
• 188 – Perfect Hash: Enunciado
• 191 – Intersection: Enunciado
• 193 – Graph Coloring: Enunciado
• 195 – Anagram: Enunciado
• 196 – Spreadsheet: Enunciado

Problemas ACM – Volumen II – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen II:

• 200 – Rare Order: Enunciado
• 201 – Squares: Enunciado
• 202 – Repeating Decimals: Enunciado
• 216 – Getting in Line: Enunciado
• 218 – Moth Eradication: Enunciado
• 227 – Puzzle: Enunciado
• 231 – Testing the CATCHER: Enunciado
• 232 – Crossword Answers: Enunciado
• 253 – Cube Painting: Enunciado
• 254 – Towers of Hanoi: Enunciado
• 256 – Quirksome Squares: Enunciado
• 259 – Software Allocation: Enunciado
• 260 – Il Gioco dell’X: Enunciado
• 263 – Number Chains: Enunciado
• 264 – Count on Cantor: Enunciado
• 270 – Lining Up: Enunciado
• 271 – Simply Syntax: Enunciado
• 272 – TeX Quotes: Enunciado
• 275 – Expanding Fractions: Enunciado
• 278 – Chess: Enunciado
• 280 – Vertex: Enunciado
• 288 – Arithmetic Operations With Large Integers: Enunciado
• 290 – Palindroms: Enunciado
• 291 – The House Of Santa Claus: Enunciado
• 294 – Divisors: Enunciado
• 297 – Quadtrees: Enunciado
• 299 – Train Swapping: Enunciado

Problemas ACM – Volumen III – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen III:

• 300 – Maya Calendar: Enunciado
• 301 – Transportation: Enunciado
• 302 – John’s trip: Enunciado
• 303 – Pipe: Enunciado
• 305 – Joseph: Enunciado
• 306 – Cipher: Enunciado
• 308 – Tin Cutter: Enunciado
• 310 – L-system: Enunciado
• 311 – Packets: Enunciado
• 313 – Intervals: Enunciado
• 314 – Robot: Enunciado
• 315 – Network: Enunciado
• 320 – Border: Enunciado
• 324 – Factorial Frequencies: Enunciado
• 325 – Identifying Legal Pascal Real Constants: Enunciado
• 326 – Extrapolation Using a Difference Table: Enunciado
• 327 – Evaluating Simple C Expressions: Enunciado
• 331 – Mapping the Swaps: Enunciado
• 332 – Rational Numbers from Repeating Fractions: Enunciado
• 333 – Recognizing Good ISBNs: Enunciado
• 336 – A Node Too Far: Enunciado
• 337 – Interpreting Control Sequences: Enunciado
• 340 – Master-Mind Hints: Enunciado
• 341 – Non-Stop Travel: Enunciado
• 343 – What Base Is This?: Enunciado
• 344 – Roman Digititis: Enunciado
• 347 – Run, Run, Runaround Numbers: Enunciado
• 348 – Optimal Array Multiplication Sequence: Enunciado
• 350 – Pseudo-Random Numbers: Enunciado
• 352 – The Seasonal War: Enunciado
• 353 – Pesky Palindromes: Enunciado
• 355 – The Bases Are Loaded: Enunciado
• 356 – Square Pegs And Round Holes: Enunciado
• 357 – Let Me Count The Ways: Enunciado
• 361 – Cops and Robbers: Enunciado
• 362 – 18,000 Seconds Remaining: Enunciado
• 369 – Combinations: Enunciado
• 371 – Ackermann Functions: Rectangles: Enunciado
• 374 – Big Mod: Rectangles and Circles: Enunciado
• 377 – Cowculations: Rectangles, Circles, and Triangles: Enunciado
• 378 – Intersecting Lines: Enunciado
• 382 – Perfection: Enunciado
• 383 – Shipping Routes: Enunciado
• 384 – Slurpys: Enunciado
• 386 – Perfect Cubes: Enunciado
• 389 – Basically Speaking: Enunciado
• 392 – Polynomial Showdown: Enunciado
• 394 – Mapmaker: Enunciado

Problemas ACM – Volumen IV – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen IV:

• 400 – Unix ls: Enunciado
• 401 – Palindromes: Enunciado
• 402 – M*A*S*H: Enunciado
• 406 – Prime Cuts: Enunciado
• 408 – Uniform Generator: Enunciado
• 409 – Excuses, Excuses!: Enunciado
• 412 – Pi: Enunciado
• 413 – Up and Down Sequences: Enunciado
• 414 – Machined Surfaces: Enunciado
• 417 – Word Index: Enunciado
• 422 – Word-Search Wonder: Enunciado
• 423 – MPI Maelstrom: Enunciado
• 424 – Integer Inquiry: Enunciado
• 436 – Arbitrage (II): Enunciado
• 437 – The Tower of Babylon: Enunciado
• 438 – The Circumference of the Circle: Enunciado
• 439 – Knight Moves: Enunciado
• 440 – Eeny Meeny Moo: Enunciado
• 441 – Lotto: Enunciado
• 442 – Matrix Chain Multiplication: Enunciado
• 443 – Humble Numbers: Enunciado
• 444 – Encoder and Decoder: Enunciado
• 445 – Marvelous Mazes: Enunciado
• 446 – Kibbles `n’ Bits `n’ Bits `n’ Bits: Enunciado
• 448 – OOPS!: Enunciado
• 450 – Little Black Book: Enunciado
• 453 – Intersecting Circles: Enunciado
• 455 – Periodic Strings: Enunciado
• 457 – Linear Cellular Automata: Enunciado
• 458 – The Decoder: Enunciado
• 459 – Graph Connectivity: Enunciado
• 460 – Overlapping Rectangles: Enunciado
• 465 – Overflow: Enunciado
• 466 – Mirror, Mirror: Enunciado
• 469 – Wetlands of Florida: Enunciado
• 473 – Raucous Rockers: Enunciado
• 474 – Heads / Tails Probability: Enunciado
• 476 – Points in Figures: Rectangles: Enunciado
• 477 – Points in Figures: Rectangles and Circles: Enunciado
• 478 – Points in Figures: Rectangles, Circles, and Triangles: Enunciado
• 481 – What Goes Up: Enunciado
• 482 – Permutation Arrays: Enunciado
• 483 – Word Scramble: Enunciado
• 484 – The Department of Redundancy Department: Enunciado
• 485 – Pascal’s Triangle of Death: Enunciado
• 486 – English-Number Translator: Enunciado
• 488 – Triangle Wave: Enunciado
• 489 – Hangman Judge: Enunciado
• 490 – Rotating Sentences: Enunciado
• 492 – Pig-Latin: Enunciado
• 494 – Kindergarten Counting Game: Enunciado
• 495 – Fibonacci Freeze: Enunciado
• 496 – Simply Subsets: Enunciado
• 497 – Strategic Defense Initiative: Enunciado
• 498 – Polly the Polynomial: Enunciado
• 499 – What’s The Frequency, Kenneth?: Enunciado

Problemas ACM – Volumen V – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen V:

• 507 – Jill Rides Again: Enunciado
• 514 – Rails: Enunciado
• 515 – King: Enunciado
• 516 – Prime Land: Enunciado
• 517 – Word: Enunciado
• 523 – Minimum Transport Cost: Enunciado
• 524 – Prime RIng Problem: Enunciado
• 530 – Binomial Showdown: Enunciado
• 531 – Compromise: Enunciado
• 532 – Dungeon Master: Enunciado
• 533 – Equation Solver: Enunciado
• 534 – Frogger: Enunciado
• 535 – Globetrotter: Enunciado
• 536 – Tree Recovery: Enunciado
• 537 – Artificial Intelligence?: Enunciado
• 539 – The Settlers of Catan: Enunciado
• 541 – Error Correction: Enunciado
• 542 – France ‘98: Enunciado
• 543 – Goldbach’s Conjecture: Enunciado
• 544 – Heavy Cargo: Enunciado
• 547 – DDF: Enunciado
• 555 – Bridge Hands: Enunciado
• 558 – Wormholes: Enunciado
• 562 – Dividing Coins: Enunciado
• 563 – Crimewave: Enunciado
• 565 – Pizza Anyone?: Enunciado
• 567 – Risk: Enunciado
• 568 – Just the Facts: Enunciado
• 571 – Jugs: Enunciado
• 572 – Oil Deposits: Enunciado
• 573 – The Snail: Enunciado
• 574 – Sum It Up: Enunciado
• 575 – Skew Binary: Enunciado
• 576 – Haiku Review: Enunciado
• 579 – ClockHands: Enunciado
• 580 – Critical Mass: Enunciado
• 583 – Prime Factors: Enunciado
• 585 – Triangles: Enunciado
• 587 – There’s Treasure Everywhere!: Enunciado
• 590 – Always on the Run: Enunciado
• 591 – Box of Bricks: Enunciado
• 594 – One Little, Two Little, Three Little Endians: Enunciado

Problemas ACM – Volumen VI – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen VI:

• 600 – A Duckpin Tournament: Enunciado
• 601 – The Path: Enunciado
• 602 – What Day Is It?: Enunciado
• 603 – Parking Lot: Enunciado
• 604 – The Boggle Game: Enunciado
• 607 – Scheduling Lectures: Enunciado
• 608 – Counterfeit Dollar: Enunciado
• 610 – Street Directions: Enunciado
• 612 – DNA Sorting: Enunciado
• 613 – Numbers that Count: Enunciado
• 615 – Is It A Tree: Enunciado
• 616 – Coconuts, Revisited: Enunciado
• 619 – Numerically Speaking: Enunciado
• 620 – Cellular Structure: Enunciado
• 621 – Secret Research: Enunciado
• 623 – 500!: Enunciado
• 624 – CD: Enunciado
• 628 – Passwords: Enunciado
• 634 – Polygon: Enunciado
• 636 – Squares: Enunciado
• 637 – Booklet Printing: Enunciado
• 639 – Don’t Get Rooked: Enunciado
• 640 – Self Numbers: Enunciado
• 641 – Do the Untwist: Enunciado
• 642 – Word Amalgamation: Enunciado
• 644 – Immediate Decodability: Enunciado
• 656 – Optimal Programs: Enunciado
• 657 – The Die is Cast: Enunciado
• 661 – Blowing Fuses: Enunciado
• 663 – Sorting Slides: Enunciado
• 670 – The Dog Task: Enunciado
• 673 – Parentheses Balance: Enunciado
• 674 – Coin Change: Enunciado
• 679 – Dropping Balls: Enunciado
• 681 – Convex Hull Finding: Enunciado
• 684 – Integral Determinant: Enunciado
• 686 – Goldbach’s Conjecture (II): Enunciado
• 694 – The Collatz Sequence: Enunciado
• 696 – How Many Knights: Enunciado
• 699 – The Falling Leaves: Enunciado

Problemas ACM – Volumen VII – Enunciados

Desde este artículo hay un link a los enunciados de los Problemas del Volumen VII:

• 700 – Date Bugs: Enunciado
• 701 – The Archeologists’ Dilemma: Enunciado
• 702 – The Vindictive Coach: Enunciado
• 703 – Triple Ties: The Organizer’s Nightmare: Enunciado
• 705 – Slash Maze: Enunciado
• 707 – Robbery: Enunciado
• 709 – Formatting Text: Enunciado
• 711 – Dividing up: Enunciado
• 714 – Copying Books: Enunciado
• 718 – Skyscraper Floors: Enunciado
• 719 – Glass Beads: Enunciado
• 725 – Division: Enunciado
• 727 – Equation: Enunciado
• 729 – The Hamming Distance Problem: Enunciado
• 737 – Gleaming the Cubes: Enunciado
• 739 – Soundex Indexing: Enunciado
• 740 – Baudot Data Communication Code: Enunciado
• 741 – Burrows Wheeler Decoder: Enunciado
• 748 – Exponentiation: Enunciado
• 750 – 8 Queens Chess Problem: Enunciado
• 753 – A Plug for UNIX: Enunciado
• 755 – 487-3279: Enunciado
• 756 – Biorhythms: Enunciado
• 762 – We Ship Cheap: Enunciado
• 763 – Fibinary Numbers: Enunciado
• 784 – Maze Exploration: Enunciado
• 787 – Maximum Sub-sequence Product: Enunciado
• 793 – Network Connections: Enunciado
• 796 – Critical Links: Enunciado

Código C solución problema The 3n+1 problem (ACM 100) – Ver. 1

En esta solución del problema “The 3 n+1 Problem“, se utiliza un vector para cada numero posible de los generados en las secuencias, donde se almacena la longitud del ciclo para cada uno de esos números.

El vector se inicializa con ceros. La primera vez que se calcula la longitud del ciclo para un número determinado, se almacena dicho valor en el vector, y todas las veces siguientes que se necesita dicha longitud, se la recupera directamente desde el vector, lo cual acelera el tiempo necesario para encontrar la respuesta.

#include<stdio.h>
 
/* Problema 3n + 1 de uva.es - version 01*/
 
long int n1, n2, maximo, t, i;
static int longitudes[27114424];
 
long int longitudciclo(long int);
int desorden;
 
int main() {
	for (i=0; i<27114424; i++) longitudes[i]=0;
 
	while (scanf("%ld",&n1) !=EOF) {		
		scanf("%ld",&n2);
		maximo=1;
		desorden=0;
 
		if (n1>n2) {
			t=n1;
			n1=n2;
			n2=t; 
			desorden=1;}
 
		for (i=n1; i<=n2; i++){
			if (longitudes[i] == 0) 
				longitudes[i] = longitudciclo(i);
		    if (longitudes[i]>maximo) maximo=longitudes[i];
		}
 
		if (desorden==0)
		 printf ("%ld %ld %ld\n", n1,n2,maximo);
		else
		 printf ("%ld %ld %ld\n", n2,n1,maximo);
	}
 
	return 0;
}
 
long int longitudciclo(long int num){
	long int longitud=1;
 
	while (num!=1){
		if (num % 2==1) {
			num = num * 3 + 1;
			if (longitudes[num]!=0) return longitudes[num]+longitud;
		}
		   else {
			    num = num / 2;
				if (longitudes[num]!=0) return longitudes[num]+longitud;
		   }
		longitud++;
	}
	return longitud;
}

Código C solución problema The 3n+1 problem (ACM 100) – Ver. 0

Abajo, el código de una primer solución (simple, haciendo uso de una función iterativa para el cálculo de la longitud del ciclo), para el problema “The 3 n+1 Problem“.

En el código, además, se lleva el registro del valor más grande alcanzado, para saber de que tamaño dimensionar el arreglo, que se utiliza para implementar una solución mas eficiente en la versión 1.

 
#include<stdio.h>
 
// Problema 3n + 1 de uva.es 
 
// con calculo del numero mas grande que se genera en el proceso, 
// para dimensionar el array usado en la version 01 
 
long int n1, n2, longitud, maximo, t, i;
 
static long int valormasgrande=1;
 
long int longitudciclo(long int);
 
int desorden;
 
int main() {
 
	while (scanf("%ld",&n1) !=EOF) {
 
		scanf("%ld",&n2);
		maximo=1;
		desorden=0;
 
		// si el primer numero es mayor que el segundo
		// los invierto, y pongo desorden=1 para despues
		// imprimir como corresponde.
		if (n1>n2) {
			t=n1;
			n1=n2;
			n2=t; 
			desorden=1;}
 
		for (i=n1; i<=n2; i++){
			longitud = longitudciclo(i);
		    if (longitud>maximo) maximo=longitud;
		}
 
		if (desorden==0)
		 printf ("%ld %ld %ld\n", n1,n2,maximo);
		else
		 printf ("%ld %ld %ld\n", n2,n1,maximo);
 
		printf("%ld", valormasgrande);
	}
 
	return 0;
}
 
long int longitudciclo(long int num){
	int longitud=1;
 
	if (num>valormasgrande) valormasgrande=num;
 
	while (num!=1){
		if (num % 2==1) num = num * 3 + 1;
		   else num = num / 2;
		longitud++;
		if (num>valormasgrande) valormasgrande=num;
	}
	return longitud;
}

Problema ACM 706 – LC Display

LC – Display

A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

Input

The input file contains several lines, one for each number to be displayed. Each line contains two integers s, n (1 <= s <= 10, 0 <= n <= 99 999 999), where n is the number to be displayed and s is the size in which it shall be displayed.

The input file will be terminated by a line containing two zeros. This line should not be processed.

Output

Output the numbers given in the input file in an LC-display-style using s “-” signs for the horizontal segments and s “|” signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.

Output a blank line after each number. (You will find a sample of each digit in the sample output.)

Sample Input

2 12345
3 67890
0 0

Sample Output

      --   --        --
   |    |    | |  | |
   |    |    | |  | |
      --   --   --   --
   | |       |    |    |
   | |       |    |    |
      --   --        -- 

 ---   ---   ---   ---   ---
|         | |   | |   | |   |
|         | |   | |   | |   |
|         | |   | |   | |   |
 ---         ---   ---
|   |     | |   |     | |   |
|   |     | |   |     | |   |
|   |     | |   |     | |   |
 ---         ---   ---   --- 

Autor: Miguel Revilla