/*------------------------------------------------------------------------------
File name:      POJ_3517_And_Then_There_Was_One.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/13/2007
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=3517

And Then There Was One
Time Limit: 5000MS        Memory Limit: 65536K
Total Submissions: 725        Accepted: 342

Description

Let’s play a stone removing game.

Initially, n stones are arranged on a circle and numbered 1, …, n clockwise
(Figure 1). You are also given two numbers k and m. From this state, remove
stones one by one following the rules explained below, until only one remains.
In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from
m and remove it. In subsequent steps, start from the slot of the stone removed
in the last step, make k hops clockwise on the remaining stones and remove the
one you reach. In other words, skip (k ?? 1) remaining stones clockwise and
remove the next one. Repeat this until only one stone is left and answer its
number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown
in Figure 1.

Initial state   
Step 1   
Step 2   
Step 3   
Step 4

Step 5   
Step 6   
Step 7   
Final state   
Figure 1: An example game

Initial state: Eight stones are arranged on a circle.

Step 1: Stone 3 is removed since m = 3.

Step 2: You start from the slot that was occupied by stone 3. You skip four
stones 4, 5, 6 and 7 (since k = 5), and remove the next one, which is 8.

Step 3: You skip stones 1, 2, 4 and 5, and thus remove 6. Note that you only
count stones that are still on the circle and ignore those already removed.
Stone 3 is ignored in this case.

Steps 4–7: You continue until only one stone is left. Notice that in later
steps when only a few stones remain, the same stone may be skipped multiple
times. For example, stones 1 and 4 are skipped twice in step 7.

Final State: Finally, only one stone, 1, is on the circle. This is the final
state, so the answer is 1.

Input

The input consists of multiple datasets each of which is formatted as follows.

n k m

The last dataset is followed by a line containing three zeros. Numbers in a line
are separated by a single space. A dataset satisfies the following conditions.

2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ m ≤ n

The number of datasets is less than 100.

Output

For each dataset, output a line containing the stone number left in the final
state. No extra characters such as spaces should appear in the output.

Sample Input

8 5 3
100 9999 98
10000 10000 10000
0 0 0

Sample Output

1
93
2019

Source
Japan 2007

------------------------------------------------------------------------------*/
//code that returns WA
#include <stdio.h>
#include <malloc.h>

struct node
{
    int data;
    struct node* next;
};

struct node* Creat( int len )
{
    struct node * head, *p;
    int cnt;
    head = p = ( struct node *) malloc( sizeof (struct node) );
    head -> data = 1;
    for ( cnt = 2 ; cnt<=len ; ++cnt )
    {
        p->next = (struct node*) malloc( sizeof (struct node));
        p = p->next;
        p->data = cnt;
    }   
    p->next = head;
    return head;
}   

struct node * GetPosition( struct node * head, int m )
{
    int cnt;
    for ( cnt = 0; cnt<m ; ++cnt )
    {
        head = head->next;
    }   
    return head;
}   

void Delete( struct node * p )
{
    struct node * q = p -> next ;
//   printf( "%d", p->data);
    p -> next = q -> next;
    p->data = q->data;
    free(q);
}   

int main()
{
    int n,k,m;
    while ( scanf( "%d%d%d", &n,&k,&m) == 3 )
    {
        struct node* head = NULL;
        int temp;
        if ( n==0 && k == 0 && m == 0 )
        {
            break;
        }   
        temp = k%n;
        m = (m%n==0)?m:m%n;
        if ( n == 1 )
        {
            printf( "1\n");
            continue;
        }   
        if ( k == 1 )
        {
            printf( "%d\n", (m==1)?n:(m-1) );
            continue;
        }   
       
        head = Creat( n );
        head = GetPosition( head, m-1 );
        Delete( head );
        --n;
        while ( head->next != head )
        {
            temp = (k%n == 0)?k:k%n;
            head = GetPosition( head, temp-1 );
            Delete( head );
            --n;
        }   
        printf( "%d\n", head->data );
        free( head );
    }   
   
    system( "PAUSE" );
    return 0;
}   

/*------------------------------------------------------------------------------
File name:      POJ_3518_SPrime_Gap.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/12/2007
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=3518

SPrime Gap
Time Limit: 5000MS        Memory Limit: 65536K
Total Submissions: 589        Accepted: 377

Description

The sequence of n ?? 1 consecutive composite numbers (positive integers that
are not prime and not equal to 1) lying between two successive prime numbers p
and p + n is called a prime gap of length n. For example, ??24, 25, 26, 27,
28?? between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k,
the length of the prime gap that contains k. For convenience, the length is
considered 0 in case no prime gap contains k.

Input

The input is a sequence of lines each of which contains a single positive
integer. Each positive integer is greater than 1 and less than or equal to the
100000th prime number, which is 1299709. The end of the input is indicated by a
line containing a single zero.

Output

The output should be composed of lines each of which contains a single
non-negative integer. It is the length of the prime gap that contains the
corresponding positive integer in the input if it is a composite number, or 0
otherwise. No other characters should occur in the output.

Sample Input

10
11
27
2
492170
0

Sample Output

4
0
6
0
114

Source
Japan 2007
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>
#define MAX 1299709

int tag[MAX+1];

int IsPrime( int number )
{
    int i;
    int sqrt_number = (int) sqrt( number );
    if ( number%2 == 0 )
    {
        return 0;
    }   
    for ( i = 3 ; i <= sqrt_number ; i+=2 )
    {
        if ( number %i == 0 )
        {
            return 0;
        }   
    }   
    return 1;
}   

int Find( int number )
{
    int answer;
    int cnt;
   
    for ( cnt = number; tag[cnt] == 0; ++cnt );
    answer = cnt;
    for ( cnt = number; tag[cnt] == 0; --cnt );
    answer -= cnt;
   
    return answer;
}   

int main()
{
    int input ;
    int i;
    tag[1] = 1;tag[2] = 1;tag[3] = 1;
    for ( i = 4 ; i <= MAX ; ++i )
    {
            tag[i] = IsPrime( i );
    }   
    while ( scanf( "%d", &input ) == 1 && input != 0 )
    {
        printf( "%d\n", Find( input ) );
    }   
   
    system( "PAUSE" );
    return 0;
}   

/*------------------------------------------------------------------------------
File name:      ZOJ_1241_Geometry Made Simple.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/11/2008
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.zju.edu.cn/show_problem.php?pid=1241

Geometry Made Simple
Time limit: 1 Seconds   Memory limit: 32768K
Total Submit: 7563   Accepted Submit: 2401

Mathematics can be so easy when you have a computer. Consider the following
example. You probably know that in a right-angled triangle, the length of the
three sides a, b, c (where c is the longest side, called the hypotenuse)
satisfy the relation a*a+b*b=c*c. This is called Pythagora's Law.

Here we consider the problem of computing the length of the third side, if two
are given.

Input

The input contains the descriptions of several triangles. Each description
consists of a line containing three integers a, b and c, giving the lengths of
the respective sides of a right-angled triangle. Exactly one of the three
numbers is equal to -1 (the 'unknown' side), the others are positive (the
'given' sides).

A description having a=b=c=0 terminates the input.


Output

For each triangle description in the input, first output the number of the
triangle, as shown in the sample output. Then print "Impossible." if there is no
right-angled triangle, that has the 'given' side lengths. Otherwise output the
length of the 'unknown' side in the format "s = l", where s is the name of the
unknown side (a, b or c), and l is its length. l must be printed exact to three
digits to the right of the decimal point.

Print a blank line after each test case.


Sample Input

3 4 -1
-1 2 7
5 -1 3
0 0 0


Sample Output

Triangle #1
c = 5.000

Triangle #2
a = 6.708

Triangle #3
Impossible.
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>

int main()
{
    double a,b,c;
    int tag = 0;
    while ( scanf("%lf%lf%lf", &a,&b,&c) )
    {
        if ( a == 0 && b == 0 && c == 0 )
        {
            break;
        }   
        if ( a*b*c>0 )
        {
            printf( "Triangle #%d\nImpossible.\n\n", ++tag );
        }   
        else if ( a == -1 )
        {
            if ( b>=c )
            {
                printf( "Triangle #%d\nImpossible.\n\n", ++tag );
            }   
            else
            {
                printf( "Triangle #%d\na = %.3lf\n\n", ++tag, sqrt( c*c-b*b ) );
            }   
        }   
        else if ( b == -1 )
        {
            if ( a>=c )
            {
                printf( "Triangle #%d\nImpossible.\n\n", ++tag );
            }   
            else
            {
                printf( "Triangle #%d\nb = %.3lf\n\n", ++tag, sqrt( c*c-a*a ) );
            }   
        }  
        else if ( c == -1 )
        {
                printf( "Triangle #%d\nc = %.3lf\n\n", ++tag, sqrt( a*a+b*b ) );
        }    
       
    }   
   
    system( "PAUSE" );
    return 0;
}   

/*------------------------------------------------------------------------------
File name:      TOJ_1112_Integer_Inquiry.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/11/2007
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.tju.edu.cn/toj/showp1112.html

1112.   Integer Inquiry
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 1430   Accepted Runs: 433    Multiple test files


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


Source: East Central North America 1996
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define MAXLEN 200

int sum[MAXLEN];

int GetLen( int* a )
{
    int i = MAXLEN;
    while ( a[--i] == 0 );
    return i+1;
}   

int main()
{
    char c_num[MAXLEN];
    int i_num[MAXLEN];
    int len;
    int i,j;
   
    while ( scanf( "%s", c_num ) )
    {
        len = strlen( c_num );
        if ( len == 1 && c_num[0] == '0')
        {
            break;
        }   
        for ( i = len-1, j = 0 ; i >= 0 ; --i,++j )
        {
            i_num[j] = c_num[i]-'0';
        }   
        while ( j < MAXLEN )
        {
            i_num[j++] = 0;
        }   
        for ( i = 0 ; i < MAXLEN ; ++i )
        {
            sum[i] += i_num[i];
        }   
    }   
    len = GetLen(sum);
    for ( i = 0 ; i < len-1 ; ++i )
    {
        sum[i+1] += sum[i]/10;
        sum[i] %= 10;
    }
    while ( i >= 0 )  
    {
        printf( "%d", sum[i--]);
    }   
    printf( "\n");
   
    system( "PAUSE" );
    return 0;
}   

/*------------------------------------------------------------------------------
File name:      POJ_1218_THE DRUNK JAILER.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/4/2007
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.cn/JudgeOnline/problem?id=1218

THE DRUNK JAILER
Time Limit: 1000MS        Memory Limit: 10000K
Total Submissions: 6613        Accepted: 4420

Description
A certain prison contains a long hall of n cells, each right next to each other. Each cell has a prisoner in it, and each cell is locked.
One night, the jailer gets bored and decides to play a game. For round 1 of the game, he takes a drink of whiskey,and then runs down the hall unlocking each cell. For round 2, he takes a drink of whiskey, and then runs down the
hall locking every other cell (cells 2, 4, 6, ?). For round 3, he takes a drink of whiskey, and then runs down the hall. He visits every third cell (cells 3, 6, 9, ?). If the cell is locked, he unlocks it; if it is unlocked, he locks it. He
repeats this for n rounds, takes a final drink, and passes out.
Some number of prisoners, possibly zero, realizes that their cells are unlocked and the jailer is incapacitated. They immediately escape.
Given the number of cells, determine how many prisoners escape jail.

Input
The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines contains a single integer between 5 and 100, inclusive, which is the number of cells n.

Output
For each line, you must print out the number of prisoners that escape when the prison has n cells.

Sample Input

2
5
100

Sample Output

2
10

Source
Greater New York 2002
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>
int main()
{
    int amount ;
    scanf( "%d", &amount );
    while ( amount-- )
    {
        int number ;
        scanf( "%d", &number );
        printf( "%d\n", (int)sqrt(number) );
    }   
   
    system( "PAUSE" );
    return 0;
}   

/*------------------------------------------------------------------------------
File name:      POJ_2390_Bank Interest.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     3/3/2007
Environment:    Microsoft Windows XP Service Pack 2 [Build 5.1.2600] CHN Pro
                Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=2390

Bank Interest
Time Limit: 1000MS        Memory Limit: 65536K
Total Submissions: 4571        Accepted: 2816

Description
Farmer John made a profit last year! He would like to invest it well but wonders
how much money he will make. He knows the interest rate R (an integer between 0
and 20) that is compounded annually at his bank. He has an integer amount of
money M in the range 100..1,000,000. He knows how many years Y (range: 0..400)
he intends to invest the money in the bank. Help him learn how much money he
will have in the future by compounding the interest for each year he saves.
Print an integer answer without rounding. Answers for the test data are
guaranteed to fit into a signed 32 bit integer.

Input
* Line 1: Three space-separated integers: R, M, and Y

Output
* Line 1: A single integer that is the number of dollars FJ will have after Y
years.

Sample Input

5 5000 4

Sample Output

6077

Hint
INPUT DETAILS:

5% annual interest, 5000 money, 4 years

OUTPUT DETAILS:

Year 1: 1.05 * 5000 = 5250
Year 2: 1.05 * 5250 = 5512.5
Year 3: 1.05 * 5512.50 = 5788.125
Year 4: 1.05 * 5788.125 = 6077.53125
The integer part of 6077.53125 is 6077.

Source
USACO 2004 November
------------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>
int main()
{
    double R, N, Y;
    int temp;
   
    scanf( "%lf%lf%lf", &R, &N, &Y );
    N *= pow( R/100+1, Y );
    printf( "%d\n", (int)N );
   
    system( "PAUSE" );
    return 0;
}   

sigh。。。我总是这么依赖师父。我什么时候才能独立。
/*------------------------------------------------------------------------------
File name:      POJ_3400_Dropping the stones.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     12/19/2007
Environment:    Microsoft Windows XP Service Pack 2 [Build 5.1.2600] CHN Pro
                Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=3400

Dropping the stones
Time Limit: 2000MS        Memory Limit: 65536K
Total Submissions: 668        Accepted: 194

Description

You have N stones (1 ≤ N ≤ 10), each stone is characterized by weight pi and
cost vi (i = 1, ... , N). You should drop these stones by a gutter into one of
the two bunkers: A or В.

The mechanism of receiving bunkers switching works as follows. The stones are
dropping into one of the bunkers until the weight of this bunker’s content will
exceed the weight of stones in other bunker by more than D. Then the gutter
switches to the other bunker. At the beginning both bunkers are empty, and the
first stone falls into the bunker А.

The task is to collect stones with maximum total cost in bunker B after all
stones have been dropped.

Input

The input consists of N + 1 lines. The first line contains values N and D
separated by one or several spaces. The next lines contain values pi and vi,
also separated by spaces. All input data (except N) are integers from 0 to 10000.

Output

The output contains a single line with total cost of stones in the bunker B.

Sample Input

4 2
2 2
2 2
1 1
1 1

Sample Output

3

Source
Northeastern Europe 2001, Western Subregion
------------------------------------------------------------------------------*/
#include <stdio.h>

struct Stone
{
    int weight;
    int price;
    int visited;
}stone[10];

int d;
int result = 0;     //这组数据的最终结果

struct Bunker
{
    int price;
    int weight;
}a = {0,0},b = {0,0};

struct Bunker *p = &a, *q = &b; //当前和另一个的指针

void Drop( int amount, int depth )
{
    int i;
   
    if ( depth == amount )
    {
        if ( result < b.price )
        {
            result = b.price;
        }
        return ;
    }   
   
    for ( i = 0 ; i < amount ; ++i )
    {
        if ( stone[i].visited == 0 )
        {
            struct Bunker *p_temp = p,*q_temp = q;
            stone[i].visited = 1;
            if ( p->weight > q->weight + d )
            {
                struct Bunker *temp = p;
                p = q;
                q = temp;
            }   
            p->weight += stone[i].weight;
            p->price += stone[i].price;
            Drop( amount, depth+1 );
            p->weight -= stone[i].weight;
            p->price -= stone[i].price;
            p = p_temp;
            q = q_temp;
            stone[i].visited = 0;
        }   
    }   
}   

int main()
{
    int amount;
    int i;
   
    scanf( "%d%d", &amount, &d );
   
    for ( i = 0 ; i < amount ; ++i )
    {
        scanf( "%d%d", &stone[i].weight, &stone[i].price );
        stone[i].visited = 0;
    }   

    Drop( amount, 0 );
   
    printf( "%d\n", result );
   
    system( "PAUSE" );
    return 0;
}

师父。。。您可知。。。10分钟AC一道题是多么快乐。。。/*-------------------------------------------------------------------------
File name:      POJ_World Cup Noise.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     2/4/2008
Environment:    WinXPSP2 CHN + VC++6.0

Problem statement:
---------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=1953

World Cup Noise
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 3625 Accepted: 1828

Description
Background
"KO-RE-A, KO-RE-A" shout 54.000 happy football fans after their team has
reached the semifinals of the FIFA World Cup in their home country. But
although their excitement is real, the Korean people are still very
organized by nature. For example, they have organized huge trumpets (that
sound like blowing a ship's horn) to support their team playing on the
field. The fans want to keep the level of noise constant throughout the
match.
The trumpets are operated by compressed gas. However, if you blow the
trumpet for 2 seconds without stopping it will break. So when the trumpet
makes noise, everything is okay, but in a pause of the trumpet,the fans
must chant "KO-RE-A"!
Before the match, a group of fans gathers and decides on a chanting pattern.
The pattern is a sequence of 0's and 1's which is interpreted in the
following way: If the pattern shows a 1, the trumpet is blown. If it shows
a 0, the fans chant "KO-RE-A". To ensure that the trumpet will not break,
the pattern is not allowed to have two consecutive 1's in it.
Problem
Given a positive integer n, determine the number of different chanting
patterns of this length, i.e., determine the number of n-bit sequences that
contain no adjacent 1's. For example, for n = 3 the answer is 5 (sequences
000, 001, 010, 100, 101 are acceptable while 011, 110, 111 are not).

Input
The first line contains the number of scenarios.
For each scenario, you are given a single positive integer less than 45 on
a line by itself.

Output
The output for every scenario begins with a line containing "Scenario #i:",
where i is the number of the scenario starting at 1. Then print a single line
containing the number of n-bit sequences which have no adjacent 1's.
Terminate the output for the scenario with a blank line.

Sample Input

2
3
1

Sample Output

Scenario #1:
5

Scenario #2:
2

Source
TUD Programming Contest 2002, Darmstadt, Germany

-------------------------------------------------------------------------*/
#include <stdio.h>

int main()
{
int ans[46];
int amount;
int number;
int i;
int times;

ans[1] = 2;
ans[2] = 3;

for ( i = 3 ; i <= 45 ; ++i )
{
   ans[i] = ans[i-1] + ans[i-2];
}

scanf( "%d", &amount );
for ( times = 1 ; times <= amount ; ++times )
{
   scanf( "%d", &number );
   printf( "Scenario #%d:\n%d\n\n", times, ans[number] );
}

return 0;
}

/*------------------------------------------------------------------------------
File name:      POJ_2000_Gold_Coins.c
Author:         wtthappy (email: wtthappy@hotmail.com )
Created on:     1/9/2008
Environment:    WinXPSP2 CHN Pro + Dev-C++ 4.9.9.0

Problem statement:
--------------------------------------------------------------------------------
http://acm.pku.edu.cn/JudgeOnline/problem?id=2000

Gold Coins
Time Limit: 1000MS        Memory Limit: 30000K
Total Submissions: 6391        Accepted: 4172

Description
The king pays his loyal knight in gold coins. On the first day of his service,
the knight receives one gold coin. On each of the next two days (the second and
third days of service), the knight receives two gold coins. On each of the next
three days (the fourth, fifth, and sixth days of service), the knight receives
three gold coins. On each of the next four days (the seventh, eighth, ninth, and
tenth days of service), the knight receives four gold coins. This pattern of
payments will continue indefinitely: after receiving N gold coins on each of N
consecutive days, the knight will receive N+1 gold coins on each of the next N+1
consecutive days, where N is any positive integer.

Your program will determine the total number of gold coins paid to the knight in
any given number of days (starting from Day 1).

Input
The input contains at least one, but no more than 21 lines. Each line of the
input file (except the last one) contains data for one test case of the problem,
consisting of exactly one integer (in the range 1..10000), representing the
number of days. The end of the input is signaled by a line containing the number
0.

Output
There is exactly one line of output for each test case. This line contains the
number of days from the corresponding line of input, followed by one blank space
and the total number of gold coins paid to the knight in the given number of
days, starting with Day 1.

Sample Input

10
6
7
11
15
16
100
10000
1000
21
22
0

Sample Output

10 30
6 14
7 18
11 35
15 55
16 61
100 945
10000 942820
1000 29820
21 91
22 98

Source
Rocky Mountain 2004
------------------------------------------------------------------------------*/
#include <stdio.h>
#define MAX 10000

int array[MAX+1][2];

int main()
{
    int input;
    int coin = 1,total;
    int day = 0;
   
    while ( day < MAX )
    {
        int i = coin;
        while ( i-- )
        {
            array[++day][0] = coin;
            array[day][1] = array[day-1][1]+coin;
            if ( day == MAX )
            {
                break;
            }   
        }   
        ++coin;
    }
   
    while ( scanf( "%d", &input ), input != 0 )
    {
        printf( "%d %d\n", array[input][0], array[input][1] );
    }   
   
    system( "PAUSE" );
    return 0;
}