10000 - Longest Paths

Time limit: 3.000 seconds
                                      Longest Paths
It is a well known fact that some people do not have their social abilities completely enabled. One example is the lack of talent for calculating distances and intervals of time. This causes some people to always choose the longest way to go from one place to another, with the consequence that they are late to whatever appointments they have, including weddings and programming contests. This can be highly annoying for their friends.
César has this kind of problem. When he has to go from one point to another he realizes that he has to visit many people, and thus always chooses the longest path. One of César's friends, Felipe, has understood the nature of the problem. Felipe thinks that with the help of a computer he might be able to calculate the time that César is going to need to arrive to his destination. That way he could spend his time in something more enjoyable than waiting for César.

Your goal is to help Felipe developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (César's residence). You can assume that the graph has no cycles (there is no path from any node to itself), so César will reach his destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves.
Input
The input consists of a number of cases. The first line on each case contains a positive number n ( ) that specifies the number of points that César might visit (i.e., the number of nodes in the graph).
A value of n = 0 indicates the end of the input.

After this, a second number s is provided, indicating the starting point in César's journey ( ). Then, you are given a list of pairs of places p and q, one pair per line, with the places on each line separated by white-space. The pair `` " indicates that César can visit q after p.
A pair of zeros (``0 0") indicates the end of the case.

As mentioned before, you can assume that the graphs provided will not be cyclic.
Output
For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.

Print a new line after each test case.

Sample Input
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0

Sample Output
Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

=====================================================

#include <stdio.h>
#include <stdlib.h>

// function prototype
void DFS(int data_num, int from, int step);

// data structure
struct FromTo
{
　int p;
　int q;
};

struct FromTo FromTo[100];
int longest_path;
int finish_point;

int main()
{
　freopen("Input.txt", "r", stdin);
　freopen("Output.txt", "w", stdout);
   
　int start_point;
　int point_num;
　int p, q;
　int case_num = 1;
   
　while(1)
　{  
　　int data_num = 0;
　　scanf("%d", &point_num);
　　if(!point_num)
　　　break;
　　for(int i=0; i<100; i++)
　　　FromTo[i].p = FromTo[i].q = -1;
　　scanf("%d", &start_point);
　　for(int i=0; scanf("%d %d", &p, &q) == 2; i++)
　　{
　　　if(!p && !q)
　　　　break;
　　　FromTo[i].p = p;
　　　FromTo[i].q = q;
　　　data_num++;
　　}
　　longest_path = 0;
　　DFS(data_num, start_point, 0);
   
　　printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",
　　　　　　case_num++, start_point, longest_path, finish_point);
　}
   
　return 0;
}

void DFS(int data_num, int from, int step)
{
　for(int i=0; i<data_num; i++)
　　if(FromTo[i].p == from)
　　{
　　　if(++step > longest_path)
　　　{
　　　　longest_path = step;
　　　　finish_point = FromTo[i].q;
　　　}
　　　DFS(data_num, FromTo[i].q, step);
　　　--step;
　　}
}

371 - Ackermann Functions ( Time limit exceeded )

Time limit: 3.000 seconds

Ackermann Functions

An Ackermann function has the characteristic that the length of the sequence of numbers generated by the function cannot be computed directly from the input value. One particular integer Ackermann function is the following:

This Ackermann has the characteristic that it eventually converges on 1. A few examples follow in which the starting value is shown in square brackets followed by the sequence of values that are generated, followed by the length of the sequence in curly braces:

     [10] 5 16 8 4 2 1 {6}
    [13] 40 20 10 5 16 8 4 2 1 {9}
    [14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}
    [19] 58 29 88 44 22 ... 2 1 {20}
    [32] 16 8 4 2 1 {5}
    [1] 4 2 1 {3}

Input and Output

Your program is to read in a series of pairs of values that represent the first and last numbers in a closed sequence. For each closed sequence pair determine which value generates the longest series of values before it converges to 1. The largest value in the sequence will not be larger than can be accomodated in a 32-bit Pascal LongInt or C long. The last pair of values will be 0, 0. The output from your program should be as follows:

Between L and H, V generates the longest sequence of S values.

Where:

L = the lower boundary value in the sequence

H = the upper boundary value in the sequence

V = the first value that generates the longest sequence, (if two or more values generate the longest sequence then only show the lower value) S = the length of the generated sequence.

In the event that two numbers in the interval should both produce equally long sequences, report the first.

Sample Input

  1 20
35 55
 0 0

Sample Output

Between 1 and 20, 18 generates the longest sequence of 20 values.
Between 35 and 55, 54 generates the longest sequence of 112 values.

=======================================================

#include <stdio.h>
#include <stdlib.h>

/* function prototype */

void Ackermann(const int,const int);
int find_length(const int);

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　int L,H;
　while(scanf("%d%d",&L,&H)==2)
　　if(L|H)
　　　Ackermann(L,H);
　return 0;
}

/* scan from lower bound to upper bound */
void Ackermann(const int L,const int H)
{
　int i,max_len=L,max_num=find_length(L);
　for(i=L+1;i<=H;i++)
　{
　　int temp=find_length(i);
　　if(max_num<temp)
　　{
　　　max_len=i;
　　　max_num=temp;
　　}
　}
　printf("Between %d and %d, %d generates the longest sequence of %d values.\n",L,H,max_len,max_num);
}

/* return the sequence number of value "V" */
int find_length(const int V)
{
　int count=0,x=V;
　do
　{
　　count++;
　　x=(!x%2)?(x/2):(3*x+1);
　}while(x!=1);
　return count;
}

369 - Combinations

Time limit: 3.000 seconds

Combinations

Computing the exact number of ways that N things can be taken M at a time can be a great challenge when N and/or M become very large. Challenges are the stuff of contests. Therefore, you are to make just such a computation given the following:

GIVEN:

Compute the EXACT value of:

You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.

For the record, the exact value of 100! is:

     93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
       468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,
       697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000

Input and Output

The input to this program will be one or more lines each containing zero or more leading spaces, a value for N, one or more spaces, and a value for M. The last line of the input file will contain a dummy N, M pair with both values equal to zero. Your program should terminate when this line is read.

The output from this program should be in the form:

N things taken M at a time is C exactly.

Sample Input

     100  6
     20  5
     18  6
      0  0

Sample Output

100 things taken 6 at a time is 1192052400 exactly.
20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.

===========================================

#include <stdio.h>
#include <stdlib.h>

int gcd(int,int);
void combi(const int,const int);

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　int N,M;
　while(scanf("%d%d",&N,&M)==2)
　　if(N|M)
　　　combi(N,M);
　return 0;
}

/* calculate the combinition number */
void combi(const int N,const int M)
{
　int A[M],B[M];
　int i,j;
　for(i=0;i<M;i++)
　{
　　A[i]=N-i;
　　B[i]=i+1;
　}
　for(j=1;j<M;j++)
　　for(i=0;i<M;i++)
　　{
　　　/* find the GCD of each pair when B[] is not 1 */
　　　int GCD=gcd(A[i],B[j]);
　　　if(GCD>1)
　　　{
　　　　A[i]/=GCD;
　　　　B[j]/=GCD;
　　　}
　　　if(B[j]==1)
　　　　break;
　　}
　/* when all elements in B[] are 1 then multiply every element in A[] */
　long ans=1;
　for(i=0;i<M;i++)
　　ans*=A[i];
　printf("%d things taken %d at a time is %d exactly.\n",N,M,ans);
}

/* return (x,y) by recursive */
int gcd(int x,int y)
{
　return (!y)?x:gcd(y,x%y);
}

350 - Pseudo-Random Numbers

Time limit: 3.000 seconds

Pseudo-Random Numbers

Computers normally cannot generate really random numbers, but frequently are used to generate sequences of pseudo-random numbers. These are generated by some algorithm, but appear for all practical purposes to be really random. Random numbers are used in many applications, including simulation.

A common pseudo-random number generation technique is called the linear congruential method. If the last pseudo-random number generated was L, then the next number is generated by evaluating ( , where Z is a constant multiplier, I is a constant increment, and M is a constant modulus. For example, suppose Z is 7, I is 5, and M is 12. If the first random number (usually called the seed) is 4, then we can determine the next few pseudo-random numbers are follows:

As you can see, the sequence of pseudo-random numbers generated by this technique repeats after six numbers. It should be clear that the longest sequence that can be generated using this technique is limited by the modulus, M.

In this problem you will be given sets of values for Z, I, M, and the seed, L. Each of these will have no more than four digits. For each such set of values you are to determine the length of the cycle of pseudo-random numbers that will be generated. But be careful: the cycle might not begin with the seed!

Input

Each input line will contain four integer values, in order, for Z, I, M, and L. The last line will contain four zeroes, and marks the end of the input data. L will be less than M.

Output

For each input line, display the case number (they are sequentially numbered, starting with 1) and the length of the sequence of pseudo-random numbers before the sequence is repeated.

Sample Input

7 5 12 4
5173 3849 3279 1511
9111 5309 6000 1234
1079 2136 9999 1237
0 0 0 0

Sample Output

Case 1: 6
Case 2: 546
Case 3: 500
Case 4: 220

============================================

#include <stdio.h>
#include <stdlib.h>

/* function prototype */
int random_length(const int,const int,const int,int);

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　int Z,I,M,L,data_num=0;
　while(scanf("%d%d%d%d",&Z,&I,&M,&L)==4)
　　if(Z|I|M|L)
　　　printf("Case %d: %d\n",++data_num,random_length(Z,I,M,L));
　return 0;
}

/* return the length of the random number cycle */
int random_length(const int Z,const int I,const int M,int L)
{
　/* record the random numbers */
　/* module 4-digit number only get 0~9998 */
　int array[9999];
　int i,j,count,ap;
　for(ap=0,count=1;;count++)
　{
　　array[ap++]=L;
　　L=(Z*L+I)%M;
　　for(j=0;j<ap;j++)
　　　if(L==array[j])
　　　　/* find the begin of the cycle */
　　　　return count-j;
　}
}

344 - Roman Digititis

Time limit: 3.000 seconds

Roman Digititis

Many persons are familiar with the Roman numerals for relatively small numbers. The symbols ``i", ``v", ``x", ``l", and ``c" represent the decimal values 1, 5, 10, 50, and 100 respectively. To represent other values, these symbols, and multiples where necessary, are concatenated, with the smaller-valued symbols written further to the right. For example, the number 3 is represented as ``iii", and the value 73 is represented as ``lxxiii". The exceptions to this rule occur for numbers having units values of 4 or 9, and for tens values of 40 or 90. For these cases, the Roman numeral representations are ``iv" (4), ``ix" (9), ``xl" (40), and ``xc" (90). So the Roman numeral representations for 24, 39, 44, 49, and 94 are ``xxiv", ``xxxix", ``xliv", ``xlix", and ``xciv", respectively.

The preface of many books has pages numbered with Roman numerals, starting with ``i" for the first page of the preface, and continuing in sequence. Assume books with pages having 100 or fewer pages of preface. How many ``i", ``v", ``x", ``l", and ``c" characters are required to number the pages in the preface? For example, in a five page preface we歓l use the Roman numerals ``i", ``ii", ``iii", ``iv", and ``v", meaning we need 7 ``i" characters and 2 ``v" characters.

Input

The input will consist of a sequence of integers in the range 1 to 100, terminated by a zero. For each such integer, except the final zero, determine the number of different types of characters needed to number the prefix pages with Roman numerals.

Output

For each integer in the input, write one line containing the input integer and the number of characters of each type required. The examples shown below illustrate an acceptable format.

Sample Input

1
2
20
99
0

Sample Output

1: 1 i, 0 v, 0 x, 0 l, 0 c
2: 3 i, 0 v, 0 x, 0 l, 0 c
20: 28 i, 10 v, 14 x, 0 l, 0 c
99: 140 i, 50 v, 150 x, 50 l, 10 c

================================================

#include <stdio.h>
#include <stdlib.h>

/* function prototype */
void digit_change(int,int [5]);

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　int num,i,count[5];
　while(scanf("%d",&num)==1)
　　if(num!=0)
　　{
　　　/* reset the number counting array */
　　　for(i=0;i<5;i++)
　　　　count[i]=0;
　　　for(i=1;i<=num;i++)
　　　　digit_change(i,count);
　　　printf("%d: %d i, %d v, %d x",num,count[0],count[1],count[2]);
　　　printf(", %d l, %d c\n",count[3],count[4]);
　　}
　return 0;
}

/* return every elements of Roman digit from 1 to num */
void digit_change(int num,int count[5])
{
　/* handle the exception "100" */
　if(num==100)
　{
　　count[4]++;
　　return;
　}
　/* the representations of units and tens are the same, */
　/* just differenct at count[] index shift */
　int i,n,k,times=1;
　if(num>9)
　　times=2;
　for(i=0,k=0,n=num%10;i<times;i++,k+=2,n=num/10)
　　if(n!=0)
　　　/* separate one digit to three phases */
　　　if(n>0&&n<4)
　　　　count[0+k]+=n;
　　　else if(n>3&&n<9)
　　　{
　　　　count[1+k]++;
　　　　count[0+k]+=abs(n-5);
　　　}
　　　else
　　　{
　　　　count[0+k]++;
　　　　count[2+k]++;
　　　}
}

352 - The Seasonal War

Time limit: 3.000 seconds

The Seasonal War

The inhabitants of Tigerville and Elephantville are engaged in a seasonal war. Last month, Elephantville successfully launched and orbited a spy telescope called the Bumble Scope. The purpose of the Bumble Scope was to count the number of War Eagles in Tigerville. The Bumble Scope, however, developed two problems because of poor quality control during its construction. Its primary lens was contaminated with bugs which block part of each image, and its focusing mechanism malfunctioned so that images vary in size and sharpness.

The computer programmers, who must rectify the Bumble Scope's problems are being held hostage in a Programming Contest Hotel in Alaland by elephants dressed like tigers. The Bumble Scope's flawed images are stored by pixel in a file called Bumble.in. Each image is square and each pixel or cell contains either a 0 or a 1. The unique Bumble Scope Camera (BSC) records at each pixel location a 1 if part or all of a war eagle is present and a 0 if any other object, including a bug, is visible. The programmers must assume the following:

a)

A war eagle is represented by at least a single binary one.

b)

Cells with adjacent sides on common vertices, which contain binary ones, comprise one war eagle. A very large image of one war eagle might contain all ones.

c)

Distinct war eagles do not touch one another. This assumption is probably flawed, but the programmers are desperate.

d)

There is no wrap-around. Pixels on the bottom are not adjacent to the top and the left is not adjacent to the right (unless, of course, there are only 2 rows or 2 columns)

Input and Output

Write a program that reads images of pixels from the input file (a text file), correctly counts the number of war eagles in the images and prints the image number and war eagle count for that image on a single line in the output file (also a text file).

Use the format in the sample output. Do this for each image in the input file. Each image will be preceded by a number indicating its square dimension. No dimension will exceed 25.

Sample input

6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000

Sample output

Image number 1 contains 3 war eagles.
Image number 2 contains 6 war eagles.

=========================================================

#include <stdio.h>
#include <stdlib.h>

#define MAX_DIM 25

/* functions prototype */
int find_eagle(int);
void DFS(int,int,int,int);

/* global variables */
int map[MAX_DIM+2][MAX_DIM+2];
int map2[MAX_DIM+2][MAX_DIM+2];

int main()
{
  freopen("Input.txt","r",stdin);
  freopen("Output.txt","w",stdout);
  int dimention,data_num=0;
  while(scanf("%d",&dimention)==1)
  {
      char row[dimention];
      int i,j;
      for(i=1;i<=dimention;i++)
      {
          scanf("%s",row);
          for(j=1;j<=dimention;j++)
              map[i][j]=row[j-1]-'0';
      }
      printf("Image number %d contains %d war eagles.\n",++data_num,find_eagle(dimention+2));
  }
  return 0;
}

/* return how many eagles */
int find_eagle(int dim)
{
  int i,j,label=1;
  /* map2 is the object label image map */
  for(i=0;i<MAX_DIM+2;i++)
      for(j=0;j<MAX_DIM+2;j++)
          map2[i][j]=0;
  /* if there's a point is 1 then find it's connected points */
  for(i=1;i<dim-1;i++)
      for(j=1;j<dim-1;j++)
          if(map[i][j]==1&&map2[i][j]==0)
              DFS(i,j,label++,dim);
  return label-1;
}

/* mark the connected points with same label with eight directions */
void DFS(int x,int y,int lab,int dim)
{
  /* if this point (x,y) hasn't been marked */
  if(map2[x][y]==0)
  {
      map2[x][y]=lab;
      if(map[x+1][y+1]==1)
          DFS(x+1,y+1,lab,dim);
      if(map[x+1][y]==1)
          DFS(x+1,y,lab,dim);
      if(map[x+1][y-1]==1)
          DFS(x+1,y-1,lab,dim);
      if(map[x][y-1]==1)
          DFS(x,y-1,lab,dim);
      if(map[x-1][y-1]==1)
          DFS(x-1,y-1,lab,dim);
      if(map[x-1][y]==1)
          DFS(x-1,y,lab,dim);
      if(map[x-1][y+1]==1)
          DFS(x-1,y+1,lab,dim);
      if(map[x][y+1]==1)
          DFS(x,y+1,lab,dim);
  }
}

343 - What Base Is This? (Wrong Answer)

Time limit: 3.000 seconds

What Base Is This?

In positional notation we know the position of a digit indicates the weight of that digit toward the value of a number. For example, in the base 10 number 362 we know that 2 has the weight , 6 has the weight , and 3 has the weight , yielding the value , or just 300 + 60 + 2. The same mechanism is used for numbers expressed in other bases. While most people assume the numbers they encounter everyday are expressed using base 10, we know that other bases are possible. In particular, the number 362 in base 9 or base 14 represents a totally different value than 362 in base 10.

For this problem your program will presented with a sequence of pairs of integers. Let�'s call the members of a pair X and Y. What your program is to do is determine the smallest base for X and the smallest base for Y (likely different from that for X) so that X and Y represent the same value.

Consider, for example, the integers 12 and 5. Certainly these are not equal if base 10 is used for each. But suppose 12 was a base 3 number and 5 was a base 6 number? 12 base 3 = , or 5 base 10, and certainly 5 in any base is equal to 5 base 10. So 12 and 5 can be equal, if you select the right bases for each of them!

Input

On each line of the input data there will be a pair of integers, X and Y, separated by one or more blanks; leading and trailing blanks may also appear on each line, are are to be ignored. The bases associated with X and Y will be between 1 and 36 (inclusive), and as noted above, need not be the same for X and Y. In representing these numbers the digits 0 through 9 have their usual decimal interpretations. The uppercase alphabetic characters A through Z represent digits with values 10 through 35, respectively.

Output

For each pair of integers in the input display a message similar to those shown in the examples shown below. Of course if the two integers cannot be equal regardless of the assumed base for each, then print an appropriate message; a suitable illustration is given in the examples.

Sample Input

12   5
   10     A
12 34
 123   456
 1    2
 10   2

Sample Output

12 (base 3) = 5 (base 6)
10 (base 10) = A (base 11)
12 (base 17) = 34 (base 5)
123 is not equal to 456 in any base 2..36
1 is not equal to 2 in any base 2..36
10 (base 2) = 2 (base 3)

=====================================================================

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int length(char *,int);
int base_test(char *,int,int);
int find(char *,char *);

/* flag of least bases */
int max[2];

int main()
{
　freopen("Input.txt","r",stdin);
　freopen("Output.txt","w",stdout);
　char s1[100],s2[100];
　while(scanf("%s%s",s1,s2)==2)
　　if(find(s1,s2)==0)
　　　printf("%s is not equal to %s in any base 2..36\n",s1,s2);
　return 0;
}

/* return string length and set the minimum base */
int length(char *str,int key)
{
　int i,base=str[0];
　for(i=1;str[i]!='\0';i++)
 　　if(base<str[i])
     　　base=str[i];
　base=(base-'0'>9)?(base-'A'+10+1):(base-'0'+1);
　max[key]=base;
　return i;
}

/* count the sumation in base "base" to decimal number */
int base_test(char *str,int len,int base)
{
　int i,sum=0,weight;
　for(i=0;i<len;i++)
　{
　　weight=(str[len-i-1]-'0'>9)?(str[len-i-1]-'A'+10):(str[len-i-1]-'0');
　　sum+=weight*(int)pow(base,i);
　}
　return sum;
}

/* return 0 if they are not equal at any base, 1 otherwise  */
int find(char *s1,char *s2)
{
　int i,j;
　int len1=length(s1,0);
　int len2=length(s2,1);
　for(i=max[0];i<=36;i++)
　　for(j=max[1];j<=36;j++)
　　　if((base_test(s1,len1,i))==(base_test(s2,len2,j)))
　　　{
　　　　printf("%s (base %d) = %s (base %d)\n",s1,i,s2,j);
　　　　return 1;
　　　}
　return 0;
}