fork(2) download 
  1. <?php
  2.  
  3. /********************************
  4. *** FACEBOOK HACKER CUP -2012 ***
  5. ***    QUALIFICATION ROUND    ***
  6. ***     BillBoard Problem     ***
  7. ***     C0DER: WHIZZZKID      ***
  8. ***  http://n...content-available-to-author-only...a.in/  ***
  9. ********************************/
  10.  
  11. $ip = fopen('php://stdin', "r");		//input resource can be a file
  12. $op = fopen('php://stdout',"w");		//output resource can be a file
  13. $test_cases = trim(fgets($ip));			//first line
  14. $c = 0;
  15.  
  16. while($c < $test_cases){
  17. 	$cc = $c+1;				//just for outputting correct case #n
  18. 	$input = trim(fgets($ip));
  19. 	$vals = explode(" ", $input);
  20. 	$w = array_shift($vals);
  21. 	$h = array_shift($vals);
  22. 	$string = trim(implode(" ",$vals));
  23. 	$type = (string)$string;		//dealing with numbers in the input string
  24. 	$str = str_replace(" ","",$type);
  25. 	unset($vals);				//to make sure of garbage vals
  26. 	$vals = explode(" ", $type);
  27. 	$words = count($vals);			//word count
  28. 	$bill_area = $w * $h;
  29. 	$chars = strlen($str);
  30. 	$max_size = floor(sqrt($bill_area / $chars));
  31. 	if($max_size < 1){			//last minute optimization improved performance
  32. 		$status = 1;
  33. 	}else{
  34. 		$rows = floor($h / $max_size);
  35. 		$cols = floor($w / $max_size);
  36. 	}
  37. 	while(($rows * $cols) < $chars){	//optimizing... this was a winner!...
  38. 		$max_size--;
  39. 		$rows = floor($h / $max_size);
  40. 		$cols = floor($w / $max_size);
  41. 	}
  42. 	while($status !== 1){
  43. 		$c_cl = $cols;			//it is basically current_columns
  44. 		for($i=0; $i<$words; $i++){
  45. 			//if we decremented the max_size to 0 there is no point checking further... last minute addition
  46. 			if($max_size < 1){
  47. 				$status =1;
  48. 				break 2;
  49. 			}
  50. 			//checking if the i th word cannot be accomodated in a single line 
  51. 			if($cols < (strlen($vals[$i]))){
  52. 				$max_size = floor($w / (strlen($vals[$i])));
  53. 				$rows = floor($h / $max_size);
  54. 				$cols = floor($w / $max_size);
  55. 				break;
  56. 			}
  57. 			//accomodating the new word
  58. 			if($c_cl == $cols){
  59. 				$c_cl = $c_cl - (strlen($vals[$i])); //if it is a new line
  60. 			}else{
  61. 				$c_cl = $c_cl - (strlen($vals[$i])) -1; //-1 is the space between the new and the old word
  62. 			}
  63.  
  64. 			//backtracking if we made a wrong accommodation
  65. 			if($c_cl < 0){
  66. 				$rows--;
  67. 				$c_cl = $cols - (strlen($vals[$i]));
  68. 			}
  69. 			//if we are out of rows
  70. 			if($rows < 1){		//had to be placed here after error generated by backtracking in the last row
  71. 				$max_size--;
  72. 				$rows = floor($h / $max_size);
  73. 				$cols = floor($w / $max_size);
  74. 				break;
  75. 			}
  76. 			if($i == ($words-1)){
  77. 				$status =1;
  78. 				break 2;
  79. 			}
  80. 		}
  81. 	}
  82. 	if($status ==1){
  83. 		fwrite($op, sprintf("Case #%d: %d\n", $cc, $max_size));
  84. 		$status = 0;
  85. 	}
  86. 	$c++;					//incrementing the while loop
  87. }
  88. ?>
Success #stdin #stdout 0.02s 13112KB
comments (?)
stdin 
6
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup
4 4 Ab Cd
stdout 
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7
Case #6: 2
https://ideone.com/8PXz1
language:
PHP (php 7.3.5)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!