[shkola] Polska NOI - Zadachi + Resheniq

Towa sa zadachite ot Polskata olimpiada, za koito goworih dnes!
Chetiri zadachi + 3 resheniq na C.

Chetwxrtoto(towa na "Game") reshih da ne wi go izprashtam ponezhe 
hwashta samo 4 ot 11 testa, a i poluchih predloveniq za podobrqwane.

Slovih dopxlnitelno nqkoi komentari kxm sorsowete. Wsichki tezi 
resheniq rabotqt i hwashtat wsichki testowa za sxotwetnata zadacha!
Ako ima wxprosi pishete!

Pozdrawi,
        Ivo

P.S. Ako nqkoi zhelae mozhe da mu pratq link kxm testowete na 
zadachite!

P.S.S. Shte wi pratq i zadachite ot proletniq turnir Shumen 2001 za 
9-10 klas kogato napisha i ostanalite dwe

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

        Ivaylo Riskov    <ivaylo_riskov@xxxxxxx>

        "Stenderup's Law:
           The sooner you fall behind, the more time you will have to 
catch up"

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



/* Polish National Olympiad 2000/2001 Stage 1 */
/* Antiprime Numbers */
#include <stdio.h>

#define NUMBER(x, y) number[x]*primes[y]

int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
long long number[100];
int num_divs[100];
int powers[100][10];
int found;

int main() {
        FILE *f;
        int i, j, besti, bestj, first;
        int new_divs, n, best_divs;

        f = fopen("ant.in", "rt");
        fscanf(f, "%i", &n);
        fclose(f);
        
        //first anti-prime number is 1
        found = 0;
        number[0] = 1;
        num_divs[0] = 1;
        for (i = 0; i < 10; i++)
                powers[0][i] = 0;

        //find next anti-prime number
        do {
                first = 1;
                //for each number found so far try to increase each one of its 
powers
                for (i = 0; i <= found; i++)
                        for (j = 0; j < 10; j++) {
                                //get new number of dividers
                                new_divs = num_divs[i]*(powers[i][j] + 
2)/(powers[i][j] + 1);
                                //should be greater then the number of dividers 
of the
                                //last anti-prime and it should be the lowest 
number
                                //with that property
                                if (new_divs > num_divs[found] &&
                                    (first || NUMBER(i, j) < NUMBER(besti, 
bestj)))
                                        besti = i,
                                        bestj = j,
                                        first = 0,
                                        best_divs = new_divs;
                        }
                        
                //we've found it - add it to the list
                number[++found] = NUMBER(besti, bestj);
                num_divs[found] = best_divs;
                for (i = 0; i < 10; i++)
                        powers[found][i] = powers[besti][i];
                powers[found][bestj]++;
                //if our number is greater than n - stop
        } while (number[found] <= n);

        f = fopen("ant.out", "wt");
        fprintf(f, "%Li\n", number[found - 1]);
        fclose(f);
        
        return 0;
}


/* Polish National Olympiad 2000/2001 Stage 1 */
/* Density Map */
#include <stdio.h>

int map[250][250];
int n, r;

int main() {
        FILE *f;
        int i, j;
        int left[250];
        int right[250];
        
        f = fopen("map.in", "rt");
        fscanf(f, "%i %i", &n, &r);
        for (j = 0; j < n; j++)
                for (i = 0; i < n; i++)
                        fscanf(f, "%i", map[i] + j);
        fclose(f);

        n--;
        for (j = 0; j <= n; j++) {
                //fill left values for the given row
                for (left[0] = 0, i = 1; i <= n; i++) {
                        left[i] = left[i - 1] + map[i - 1][j];
                        if (i > r)
                                left[i] -= map[i - r - 1][j];
                }
                //fill right values for the given row
                for (right[n] = 0, i = n - 1; i >= 0; i--) {
                        right[i] = right[i + 1] +  map[i + 1][j];
                        if (n - i > r)
                                right[i] -= map[i + r + 1][j];
                }
                //add up these values to our initial values
                for (i = 0; i <= n; i++)
                        map[i][j] += right[i] + left[i];
        }


        //do this vertically as well
        for (i = 0; i <= n; i++) {
                //fill up values for a column
                for (left[0] = 0, j = 1; j <= n; j++) {
                        left[j] = left[j - 1] + map[i][j - 1];
                        if (j > r)
                                left[j] -= map[i][j - r - 1];
                }
                
                //fill down values for a column
                for (right[n] = 0, j = n - 1; j >= 0; j--) {
                        right[j] = right[j + 1] +  map[i][j + 1];
                        if (n - j > r)
                                right[j] -= map[i][j + r + 1];
                }
                //add up and down values
                for (j = 0; j <= n; j++)
                        map[i][j] += right[j] + left[j];
        }

        f = fopen("map.out", "wt");
        for (j = 0; j <= n; j++)
                for (i = 0; i <= n; i++)
                        fprintf(f, "%i%s", map[i][j], (i == n ? "\n" : " "));
        fclose(f);
        
        return 0;
}


/* Polish National Olympiad 2000/2001 Stage 1 */
/* Intervals */
#include <stdio.h>
#include <stdlib.h>

int arr[50000][2];
int n;

int fcmp(const void *e1, const void *e2) {
        int diff;

        diff = *(int *)e1 - *(int *)e2;
        if (!diff)
                diff = *((int *)e1 + 1) - *((int *)e2 + 1);
        return diff;
}

int main() {
        int i, j;
        FILE *f;

        f = fopen("prz.in", "rt");
        fscanf(f, "%i", &n);
        for (i = 0; i < n; i++)
                fscanf(f, "%i %i", arr[i], arr[i] + 1);
        fclose(f);

        //sort it by first value
        qsort(arr, n, sizeof(int)*2, fcmp);

        //i - index of the interval being processed
        //j - index of the interval we process against
        for (j = 0, i = 1; i < n; i++)
                if (arr[i][0] > arr[j][1]) {
                        j++;
                        arr[j][0] = arr[i][0];
                        arr[j][1] = arr[i][1];
                }
                else
                        if (arr[i][1] > arr[j][1])
                                arr[j][1] = arr[i][1];

        f = fopen("prz.out", "wt");
        for (i = 0; i <= j; i++)
                fprintf(f, "%i %i\n", arr[i][0], arr[i][1]);
        fclose(f);
        
        return 0;
}
Title: VIII OI, Intervals
VIII Olimpiada Informatyczna 2000/2001
Task: PRZ
Author:
Intervals
I stage contest  


There is given the series of n closed intervals [ai; bi], where i=1,2,...,n. The sum of those intervals may be represented as a sum of closed pairwise non-intersecting intervals. The task is to find such representation with the minimal number of intervals. The intervals of this representation should be written in the output file in acceding order. We say that the intervals [a; b] and [c; d] are in ascending order if, and only if a <= b < c <= d.

Task

Write a program which:

  • reads from the text file PRZ.IN the description of the series of intervals, 
  • computes pairwise non-intersecting intervals satisfying the conditions given above,
  • writes the computed intervals in ascending order into the text file PRZ.OUT. 

Input

In the first line of the text file PRZ.IN there is one integer n, 3 <= n <= 50000. This is the number of intervals. In the (i+1)-st line, 1 <= i <= n, there is a description of the interval [ai; bi] in the form of two integers ai and bi separated by a single space, which are respectively the beginning and the end of the interval, 1 <= ai <= bi <= 1000000.

Output

The text file PRZ.IN should contain descriptions of all computed pairwise non-intersecting intervals. In each line should be written a description of one interval. It should be composed of two integers, separated by a single space, the beginning and the end of the interval respectively. The intervals should be written into the output file in ascending order.

Examlpe

For the input file PRZ.IN:

5
5 6
1 4
10 10
6 9
8 10

the correct answer is the output file PRZ.OUT:

1 4
5 10
Title: VIII OI, Antiprime numbers
VIII Olimpiada Informatyczna 2000/2001
Task: ANT
Author:
Antiprime numbers
I stage contest  

A positive integer n is an antiprime number, when it has more divisors than any positive integer, that is less thann.  These are examples of antiprime numbers: 1, 2, 4, 6, 12 and 24. 

Task

Write a program which:

  • reads from the text file ANT.IN a positive integer n,
  • finds the greatest antiprime integer not greater than n,
  • writes this number in the text file ANT.OUT.

Input

In the only line of the input file ANT.IN there is one integer n, 1 <= n <= 2 000 000000. 

Output

In the only line of the output file ANT.OUT your program should write exactly one integer - the greatest antiprime number not greater than n.

 

Example

For the input file ANT.IN: 

1000

the correct answer is the output file ANT.OUT:

840
Title: VIII OI, Green game
VIII Olimpiada Informatyczna 2000/2001
Task: GRA
Author:
Green game
I stage contest  

"Green game" is a game for two players, say Ann and Billy. Their task is to shift a pawn on the board. 
Some fields of the board are green, the rest is white. All of them are numbered by integers from the interval1...(a+b). The fields with integers from the interval 1...a belong to Ann, the fields with numbers(a+1)...(a+b) to Billy. 
For each field there is given a set of successors, containing the fieldsone can get to from this field in one move. These sets were chosen in such a way that from the field belonging to Ann one can get in one move to the Billy's fieldsonly, and vice versa. All the fields have non-empty sets of successors, thus one can always make a move.

At the beginning of the game we put a pawn on the arbitrarily chosen start fieldP, then players shiftthe pawn by turns from their field to any successor of this field (we knowit belongs to the opponent). The game is started by an owner of the start field P. The game is finished whenthe pawn stays for the second time on the same field, say the fieldQ. If in the sequence of moves from the field Q to the field Q taken for the second time, the pawn was put at least once on the green field, Ann wins the game,otherwise Billy wins. We say that Ann has a winning strategy for the given start field P in case when there is such a method, which guarantees that she wins the game beginning from thisfield, no matter what movesBilly makes.

Task

Write a program which:

  • reads from the text file GRA.IN the description of the board,
  • computes the set of fields for which Ann has a winning strategy,
  • writes the result in the text file GRA.OUT. 

Input

In the first line of the text file GRA.IN there are written two positive integersa, b, separated by a single space, meaning respectively: the number of fields belonging to Ann, the number of fields belonging to Billy. Integersa, b satisfy the condition: 1 <= a+b <= 3000. In the followinga+b lines there are descriptions of the fields of the board: first,descriptions of fields belonging to Ann, and then, of ones belonging to Billy. The(i+1)-st line, for 1 <= i <= a+b, begins withintegers z, k meaning respectively the colour of the field i (0 means white, 1 - green) and the number of successors of this field. Then k integers (1 <= k < a+b) are written (stillin the same line). They are the numbers denoting the successors of the i-th field. Theintegers in each line are separated by single spaces. The number of green fields on the board is not greater than 100.The total number of successors of all the fields on the board is not grater than 30000. 

Output

The first line of the text file GRA.OUT should contain exactly one integer l, which indicates the number of fields for which Ann hasa winning strategy. The following l lines should contain numbers of these fields written in ascending order - each integer should be written in a separate line.

Example

For the input file GRA.IN:

5 3
0 2 6 7
0 3 6 7 8
0 1 8
1 1 7
1 1 8
1 2 1 2
0 2 1 2
0 2 3 4

the correct answer is the output file GRA.OUT:

5
1
2
4
6
7
Title: VIII OI, Density map
VIII Olimpiada Informatyczna 2000/2001
Task: MAP
Author:
Density map
I stage contest  

There are given:

  • integers n > r >= 0,
  • F - the table n x n with the numbers from the set {0,1}; columns and lines of the table are numbered from 1 to n; the number in i-th column and j-th line of the table is denoted by F[i, j].

If [i, j] and [i', j'] are two positions in the tableF, thedistance between them is max(|i - i'|, |j -j'|). 

The table W, n x n, should be computed, where W[i, j](the number in i-th column and j-th line of the table W) is equalto the sum of all the numbers F[x,y], such that the distance between[x,y] and [i,j] is not greater than r.

Task

Write a program, which:

  • reads integers n, r and the table F from the text file MAP.IN,
  • computes the table W,
  • writes the table W into the text file MAP.OUT. 

Input

In the first line of the text file MAP.IN there are two positive integersseparated by a single space: n and r, where 0 <= r < n <= 250. In the following n lines the table F is described. Each of these lines contains n integers from the set {0,1}, separated by single spaces. The i-th number written in(j+1)-st line is equal to F[i, j]. 

Output

The text file MAP.OUT should contain exactly n lines. In the j-th linethe values W[1, j]...W[n, j] should be written respectively;they should be separated by single spaces. 

Example

For the input file MAP.IN: 

5 1
1 0 0 0 1
1 1 1 0 0 
1 0 0 0 0 
0 0 0 1 1
0 1 0 0 0

The correct answer is the output file MAP.OUT: 

3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2

Other related posts: