District 9

Problem D: Beat the Spread!

Superbowl Sunday is nearly here. In order to pass the time waiting for the half-time commercials and wardrobe malfunctions, the local hackers have organized a betting pool on the game. Members place their bets on the sum of the two final scores, or on the absolute difference between the two scores.
Given the winning numbers for each type of bet, can you deduce the final scores?

The first line of input contains n, the number of test cases. n lines follow, each representing a test case. Each test case gives s and d, non-negative integers representing the sum and (absolute) difference between the two final scores. For each test case, output a line giving the two final scores, largest first. If there are no such scores, output a line containing "impossible". Recall that football scores are always non-negative integers.

Sample Input
2
40 20
20 40

Output for Sample Input
30 10
impossible

解題思考:
根據題易比賽只有勝負，可以不考慮平手情況，因此勝方的分數必定是大於敗方。
假設勝方分數為x，敗方分數為y。 ( x, y >= 0; x >= y 且各為整數)
令分數總和為: sum; 分數差為diff。
sum = x + y;
diff = x - y;

=> x = ( sum + diff ) / 2
=> y = ( sum - diff ) / 2
根據題意可知x, y >= 0 故sum >= diff
且x, y皆為正整數，故 兩者皆為偶數(可被2整除)

解題:

/*
* 2009.4.11
* UVa Online Judge
* Root :: Contest Volumes :: Volume CVIII 
* 10812
* Problem D: Beat the Spread!
*/

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int case_no;
    
    while( ( cin >> case_no ) != 0 )
    {          
           for (int counter = 0; counter != case_no; counter++)
           {
               int sum, diff;
               cin >> sum >> diff;
               
               if( sum >= diff && (sum - diff) % 2 == 0)
                   cout << (sum + diff) / 2 << 
                   " " << (sum - diff) / 2 << endl;
               
               else
                   cout << "impossible" << endl;
           }
    }
               
    system("PAUSE");
    return EXIT_SUCCESS;
}

昨天開啟iGoogle發現原本安裝的氣象widget (由weather.com提供)

Solve It - 10341

/*
*2009.4.7 Revised
*UVa Online Judge
*Root :: Contest Volumes :: Volume CIII
*10341
*Solve It
*/

#include <iostream>
#include <cmath>

#define e 2.7182818285      
#define error 0.0000000001 //margin of error

using namespace std;

double p, q, r, s, t, u; // Global Variables

double function( double x );
double bisectionMethod(double a, double b);   
       
int main()
{
       
    while( cin >> p >> q >> r >> s >> t >> u )
    {
           if( function(0) * function(1) > 0 )
               cout << "No solution" << endl;
           
           else
               printf("%.4lf\n", bisectionMethod(0, 1));
    }
    
    return 0;
}
    
double function( double x )
{
       return p * pow(e, -x) + q * sin(x) + r * cos(x)   
              + s * tan(x) + t * pow(x, 2) + u;
}

double bisectionMethod(double a, double b)
{
       
       if( function(a) == 0 )
           return a;
           
       if( function(b) == 0 )
           return b;
           
       double z = ( a + b ) / 2;
       
       if( abs( a - b ) < error ) // | a - b | < 0.0000000001
           return z;
           
       else
       {
           if( function(a) * function(z) < 0 )
               return bisectionMethod(a, z);
           
           else
               return bisectionMethod(z, b);
       }
}

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 ( 1<= T <= 100). Then T test cases follow. Each test case consists of 2 integers a and b ( 0 <= a <= b <= 100) 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

/*
2009.4.6 Revised
Root :: Contest Volumes :: Volume CVII
Odd Sum
10783
UVa Online Judge
*/

#include <iostream>
#include <vector>

using namespace std;

int oddSum( int x, int y );

int main()
{
    int caseNumberInput;
    
    while( (cin >> caseNumberInput) != 0 )
    {
           
           vector<int> iv;
           
           for ( vector<int>::size_type caseLoopCounter = 0; 
               caseLoopCounter != caseNumberInput; 
                 caseLoopCounter )
           {
               int oddRangeOne, oddRangeTwo;
               cin >> oddRangeOne;
               cin >> oddRangeTwo;
               
               int oddRangeTemp;
               if ( oddRangeOne > oddRangeTwo )
               {
                    oddRangeTemp = oddRangeTwo;
                    oddRangeTwo = oddRangeOne;
                    oddRangeOne = oddRangeTemp;
               }
               
               iv.push_back(oddRangeOne);
               iv.push_back(oddRangeTwo);
           
           }
           
           
           vector<int> ivec;
           for ( vector<int>::size_type caseLoopCounter = 0; 
               caseLoopCounter != iv.size(); 
                 caseLoopCounter )
           {
                  //cout << iv[caseLoopCounter] << " ";
                  if( caseLoopCounter % 2 == 0 )
                         ivec.push_back 
                         ( oddSum(iv[caseLoopCounter], 
                                        iv[caseLoopCounter 1]) );
                  
           }
           
           for ( vector::size_type counter = 0; 
               counter != ivec.size();   counter)
           {
               cout << "Case " << counter 1 << ": " << 
                    ivec[counter] << endl;
               
           }
           
           
    }
    
    return 0;
           
}

int oddSum( int x, int y )
{
    int sum = 0;
    for(int loopCounter = x ; loopCounter <= y;   loopCounter )
    {
         if( loopCounter % 2 != 0 )
             sum = sum   loopCounter;
    }
    
    return sum;
}

The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:


1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n ← 3n + 1

5. else n ← n/2

6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < style="font-weight: bold;">The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).


Sample Input

1 10
100 200
201 210
900 1000


Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

/*
*UVa Online Judge
*Problem Set Volumes
*Volumes 1
*100
*The 3n + 1 problem
*/

#include <iostream>

using namespace std;

int maxLoopFunc(int x );

int main()
{
    int i, j, inputA, inputB, inputTemp;
    
    while( (cin >> inputA >> inputB) != 0)
    {
           i = inputA;
           j = inputB;

           if(i > j)
           {
                   inputTemp = j;
                   j = i;
                   i = inputTemp;
           }
           
           int maxLoop = 0;
           int maxLoopTemp;
                   
           for(int counter = i ; counter <= j; counter   )
           {
                   maxLoopTemp = maxLoopFunc(counter);
                   
                   if( maxLoopTemp > maxLoop)
                       maxLoop = maxLoopTemp;
           }
           
           cout << inputA << " " << inputB << " " 
                  << maxLoop << endl;
           
    }
    
    return 0;
              
}

int maxLoopFunc( int x )
{
    int maxLoopCounter = 1;

    while( x != 1)
    {
           if( x % 2 != 0 )
               x = 3*x   1;

           else
               x = x/2;
               
           maxLoopCounter  ;

    }
    
    return maxLoopCounter;
}