1011 Sphere

URI Online Judge | 1011

Sphere

Adapted by Neilor Tonin, URI Brazil

Timelimit: 1

Make a program that calculates and print the volume of a sphere given the radius (R) of the circle. The formula to calculate the volume is: 4/3 * pi * R³. For the purposes of this problem the value of pi is 3.14159.

Input

The input file contain an integer number.

Output

The output file will contain a message like the following example. Remember the space before and after the equal signal. The value must be printed with 3 digits after the decimal point.

Sample Input	Sample Output
3	VOLUME = 113.097

 


Solution:

#include <stdio.h>

int main(){

    register int R;

    scanf("%d", &R);

    printf("VOLUME = %.3f\n", 4.188786*R*R*R);

    return 0;

}

1005 Average 1

URI Online Judge | 1005

Average 1

Adapted by Neilor Tonin, URI Brazil

Timelimit: 1

Make a simple program that read two floating numbers corresponding to two tests for a student. After, calculate the average between them, considering that the first number has 3.5 weight and the second one have 7.5 weight. Each number can be from zero to ten, always with one digit after the decimal point. Don’t forget to print end line after the result otherwise you will get “Presentation Error”. Don’t forget the space before and after the equal sign.

Input

The input file will contain 2 floating-point numbers with one digit after the decimal point.

Output

Print MEDIA(average in portuguese) according to the following example, with 5 digits after the decimal point and a blank space before and after the equal signal.

Sample Input	Sample Output
5.0 7.1	MEDIA = 6.43182

Solution:

#include <stdio.h>

int main(){

    float x,y;

    scanf("%f %f", &x, &y);

    printf("MEDIA = %.5f\n", (x*3.5+y*7.5)/(3.5+7.5));

    return 0;

}

Advanced Sorting Algorithm

#include <stdio.h> 
void sort(int a[], int n) {
   int i, j, t, p;
   re: if(n < 32) {
      for(i = 1; i < n; i++){
         for(t = a[i], j = i - 1; j >= 0 && a[j] > t; j--)
            a[j + 1] = a[j];
         a[j + 1] = t;
      }
      return;
   }
   p = a[(n + 1) >> 1];
   for(i = -1, j = n;;) {
      while(a[++i] < p);
      while(a[--j] > p);
      if(i >= j) break;   
      t = a[i];
      a[i] = a[j];
      a[j] = t;
   }
   if((n - i) > 1)
      sort(a + i, n - i);
   n = i;
   goto re;
}

int main() {
   int a[512], n = 512;         
   sort(a, n); 
   return 0;
}

Advanced Seive Algorithm

#include <stdio.h>
#include <string.h>
static char sieve[131072];
#define PRIMEP(n) (((sieve[(n) >> 3] >> ((n) & 7)) & 1) == 0)

static void mksieve() {
    register int i, j;
    memset(sieve, 0x55, sizeof(sieve));
    for(sieve[0] = 0x53, i = 3; i < 1024; i += 2)
        if(PRIMEP(i))
            for(j = i * i; j < 1048576; j += i)
                 sieve[j >> 3] |= 1 << (j & 7);               
       
}

int main() {
    mksieve();
    int k;
    for(k = 2; k <= 100; k++)
       if(PRIMEP(k))
          printf("%d ", k);
    return 0;
}

Seive Algorithm

#include <stdio.h>
#include <math.h>
#define N 1000000

static char P[N];

int main() {
    int  n, s, t, SQR = sqrt(N);                    
 
    P[0] = P[1] = 0; 
    for(n = 2; n <= N; n++)      
       P[n] = 1;

    for(n = 2; n <= SQR; n++)       
       if(P[n])                    
          for(s = 2, t = N/n; s <= t; s++) 
             P[s*n] = 0;

    for(n = 2, t = 0; n <= 100; n++)
       if(P[n])
          printf("%d ", n);

    return 0;
}

113 - Power of Cryptography

Power of Cryptography

Background

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers modulo functions of these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be of only theoretical interest.
This problem involves the efficient computation of integer roots of numbers.

The Problem

Given an integer and an integer you are to write a program that determines , the positive root of p. In this problem, given such integers n and p, p will always be of the form for an integer k (this integer is what your program must find).

The Input

The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs , and there exists an integer k, such that .

The Output

For each integer pair n and p the value should be printed, i.e., the number k such that .

Sample Input

2
16
3
27
7
4357186184021382204544

Sample Output

4
3
1234

Solution: 

#include <stdio.h>
#include <math.h>
int main() {
    double n, P;
    while(scanf("%lf %lf", &n, &P) == 2)
        printf("%.lf\n", pow(P, 1/n));
    return 0;
}

11547 - Automatic Answer

Problem A

AUTOMATIC ANSWER

Last month Alice nonchalantly entered her name in a draw for a Tapmaster 4000. Upon checking her mail today, she found a letter that read:
“Congratulations, Alice! You have won a Tapmaster 4000. To claim your prize, you must answer the following skill testing question.”
Alice’s initial feelings of surprised joy turned quickly to those of dismay. Her lifetime record for skill testing questions is an abysmal 3 right and 42 wrong.
Mad Skills, the leading skill testing question development company, was hired to provide skill testing questions for this particular Tapmaster 4000 draw. They decided to create a different skill testing question to each winner so that the winners could not collaborate to answer the question.
Can you help Alice win the Tapmaster 4000 by solving the skill testing question?
Program Input
The input begins with t (1 ≤ t ≤ 100), the number of test cases. Each test case contains an integer n (-1000 ≤ n ≤ 1000) on a line by itself. This n should be substituted into the skill testing question below.
Program Output
For each test case, output the answer to the following skill testing question on a line by itself: “Multiply n by 567, then divide the result by 9, then add 7492, then multiply by 235, then divide by 47, then subtract 498. What is the digit in the tens column?”
Sample Input & Output
INPUT

2
637
-120

OUTPUT

1
3

---

Calgary Collegiate Programming Contest 2008

Solution:  

#include <stdio.h>
int main() {
    int n, T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        n = (n*63+7492)*5-498;
        printf("%d\n", n < 0 ? (-n/10)%10 : (n/10)%10);
    }   
    return 0;
}

11541 - Decoding

Problem D
Decoding
Input: Standard Input

Output: Standard Output

Encoding is the process of transforming information from one format into another. There exist several different types of encoding scheme. In this problem we will talk about a very simple encoding technique; Run-Length Encoding.

Run-length encoding is a very simple and easy form of data compression in which consecutive occurrences of the same characters are replaced by a single character followed by its frequency. As an example, the string ‘AABBBBDAA’ would be encoded to ‘A2B4D1A2’, quotes for clarity.

In this problem, we are interested in decoding strings that were encoded using the above procedure.

Input

The first line of input is an integer T(T<50) that indicates the number of test cases. Each case is a line consisting of an encoded string. The string will contain only digits [0-9] and letters [A-Z]. Every inputted string will be valid. That is, every letter will be followed by 1 or more digits.

Output

For each case, output the case number followed by the decoded string. Adhere to the sample for exact format.

You may assume the decoded string won’t have a length greater than 200 and it will only consist of upper case alphabets.

Sample Input                              Output for Sample Input

3 A2B4D1A2 A12 A1B1C1D1

Case 1: AABBBBDAA Case 2: AAAAAAAAAAAA Case 3: ABCD

Problemsetter: Sohel Hafiz

Special Thanks to: Mohammad Mahmudur Rahman

Solution:

#include <stdio.h>
#include <ctype.h>
#define MAX 201
int main(){
    static int T, t, i, j, k, K, f;
    static char c,d, S[MAX], R[MAX];
    /*freopen("in11541.txt", "r", stdin);*/
    scanf("%d\n", &T);
    for(t = 1; t <= T; t++){      
        scanf("%s", S);      
        for(i = 0, f = k = K = 0; (c = S[i]) != '\0'; i++){
            if(isalpha(c)){
                if(f == 2){
                    for(j = 0; j < k; j++)
                        R[K++] = d;
                    k = 0;                  
                }
                f = 1;  
                d = c;                              
            }else{
                k = k*10+(c-'0');
                f = 2;
            }          
        }  
        if(k)
            for(j = 0; j < k; j++)
                R[K++] = d;
        R[K] = '\0';      
        printf("Case %d: %s\n", t, R);
    }
    return 0;
}

10696 - f91

Problem A - f91

Time Limit: 1 second

Background

McCarthy is a famous theorician of computer science. In his work, he defined a recursive function, called f91, that takes as input a positive integer N and returns a positive integer defined as follows:

• If N ≤ 100, then f91(N) = f91(f91(N+11));
• If N ≥ 101, then f91(N) = N-10.

The Problem

Write a program, that computes McCarthy's f91.

The Input

The input tests will consist of a series of positive integers, each integer is at most 1,000,000. There will be at most 250,000 test cases. Each number is on a line on its own. The end of the input is reached when the number 0 is met. The number 0 shall not be considered as part of the test set.

Output

The program shall output each result on a line by its own, following the format given in the sample output.

Sample input

500
91
0

Sample output

f91(500) = 490
f91(91) = 91

Solution:

#include <stdio.h>
int main(){ 
   static int n;
   while(scanf("%d", &n) && n){
      printf("f91(%d) = %d\n", n, n < 102 ? 91 : n-10); 
   } 
   return 0;
}
 

136 - Ugly Numbers

Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.

Input and Output

There is no input to this program. Output should consist of a single line as shown below, with <number> replaced by the number computed.

Sample output

The 1500'th ugly number is <number>.

Solution:
#include<stdio.h>
int main() {
   static int X, Y, Z, N;
   static long A[1501], x, y, z;
   A[1] = X = Y = Z = N = 1;
   while(N++ != 1500) {
       x = 2*A[X];
       y = 3*A[Y];
       z = 5*A[Z];

       if(x < y){
        if(x < z)
        A[N] = x;
       else
        A[N] = z;
       
       }else if(y < z)      
      A[N] = y;      
       else
        A[N] = z;
       if(A[N] == x) X++;
       if(A[N] == y) Y++;
       if(A[N] == z) Z++;
   }
   printf("The 1500'th ugly number is %ld.\n", A[1500]);
   return 0;
} 

424 - Integer Inquiry

Integer Inquiry

One of the first users of BIT's new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers.
``This supercomputer is great,'' remarked Chip. ``I only wish Timothy were here to see these results.'' (Chip moved to a new apartment, once one became available on the third floor of the Lemon Sky apartments on Third Street.)

Input

The input will consist of at most 100 lines of text, each of which contains a single VeryLongInteger. Each VeryLongInteger will be 100 or fewer characters in length, and will only contain digits (no VeryLongInteger will be negative).
The final input line will contain a single zero on a line by itself.

Output

Your program should output the sum of the VeryLongIntegers given in the input.

Sample Input

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0

Sample Output

370370367037037036703703703670

Solution:

#include <stdio.h>
#include <string.h>
#define MAX 100
int main() {
   static char S[MAX+1];
   static int T, I, J, L, C, V, A[MAX][MAX], R[MAX];
   memset(A, 0, sizeof A);
   for(T = 0, L = 0; gets(S) != NULL && strcmp(S, "0") != 0; T++){
      for(I = strlen(S)-1, J = 0; I >= 0; I--)
         A[T][J++] = S[I]-48;
      L = L < J ? J : L;
   }
 
   for(I = 0, C = 0; I < L; I++){
      for(J = 0, V = 0; J < T; J++)
         V += A[J][I];
      V += C;
      C = V/10;
      R[I] =  V%10;  
   }
   if(C)
      printf("%d", C);
   for(I = L-1; I >= 0; I--)
      printf("%d", R[I]); 
   printf("\n"); 
   return 0;
}
 

591 - Box of Bricks

Box of Bricks

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. ``Look, I've built a wall!'', he tells his older sister Alice. ``Nah, you should make all stacks the same height. Then you would have a real wall.'', she retorts. After a little con- sideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?

Input 

The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights h_i of the n stacks. You may assume and . The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.
The input is terminated by a set starting with n = 0. This set should not be processed.

Output 

For each set, first print the number of the set, as shown in the sample output. Then print the line ``The minimum number of moves is k.'', where k is the minimum number of bricks that have to be moved in order to make all the stacks the same height. Output a blank line after each set.

Sample Input 

6
5 2 4 1 7 5
0

Sample Output 

Set #1
The minimum number of moves is 5.

---

Miguel A. Revilla
1998-03-10

 

Solution:  

#include <stdio.h>
#define MAX 50
int main(){
    static int B[MAX], i, n, T = 1, s, M;
    while(scanf("%d", &n) == 1 && n != 0) {
        for(i = 0; i < n; i++)
            scanf("%d", &B[i]);
        for(i = 0, s = 0; i < n; i++)
            s += B[i];
        s /= n;
        for(i = 0, M = 0; i < n; i++)
           if(B[i] < s) M += s - B[i];
        printf("Set #%d\nThe minimum number of moves is %d.\n\n", T++, M);
    }
    return 0;
}
 

String manipulation

#include <stdio.h>
#include <string.h>
#define MAX 100

int main(){
    int I, J, K;
    char A[MAX][MAX];
    K = 0;
    while(gets(A[K]) != NULL && strcmp(A[K++], "0") != 0);
    K--;
    for(I = 0; I < strlen(A[0]); I++){
        for(J = 0; J < K; J++)
            printf("%c", A[J][I]);
           printf("\n");
    }  
    return 0;
}

10783 - Odd Sum

Odd Sum

Given a range [a, b], you are to find the summation of all the odd integers in this range. For example, the summation of all the odd integers in the range [3, 9] is 3 + 5 + 7 + 9 = 24.

Input 

There can be at multiple test cases. The first line of input gives you the number of test cases, T ( 1T100). Then T test cases follow. Each test case consists of 2 integers a and b ( 0ab100) in two separate lines.

Output 

For each test case you are to print one line of output - the serial number of the test case followed by the summation of the odd integers in the range [a, b].

Sample Input 

2
1
5
3
5

Sample Output 

Case 1: 9
Case 2: 8

---

Miguel Revilla 2004-12-02 

 

Solution:

#include <stdio.h>
int main() {
    static int T, t, a, b;
    scanf("%d", &T);
    for(t = 1; t <= T; t++){
        scanf("%d%d", &a, &b);
        a = a%2 == 0 ? a+1 : a;
        b = b%2 == 0 ? b-1 : b;                     
        printf("Case %d: %d\n", t, ((a+b)/2)*((b/2 + b%2)-(a/2)));
    }
    return 0;
}

1000 - Greetings from LightOJ [Light OJ]

You are one of the most talented programmers and like to solve challenging problems. And my task is to make your life a bit complex by setting some easy looking hard brain storming problems such that you can sharpen your skills by practicing here. So, I wrote a code which shows a message like the following line:

Greetings from LightOJ

After that the code will select a random problem for you from my problems database based on your previously solved problems, your skills and your weaknesses. But while I was coding for implementing this great idea, I found that, all of my problems are scattered in 2 computers. So, I have to merge them before running my code.

Now you are given the number of problems in each of the computers, you have to find the total number of problems. You can safely assume that no problem is stored in multiple computers. So, all the problems are distinct.

Input

Input starts with an integer T (≤ 125), denoting the number of test cases.

Each case starts with a line containing two integers a and b. a denotes the number of problems in the first computer and b denotes the number of problems in the second computer. You can safely assume that a and b will be non-negative and not greater than 10.

Output

For each case, print the case number and the total number of problems. See the samples for exact formatting.

Sample Input	Output for Sample Input
2 1 7 9 8	Case 1: 8 Case 2: 17

---

Problem Setter: Jane Alam Jan

Solution:

#include <stdio.h>
int main(){
    static int T, t, A, B;
    scanf("%d", &T);
    for(t = 1; t <= T; t++){
        scanf("%d%d", &A, &B);
        printf("Case %d: %d\n", t, A+B);
    }
    return 0;
}