HINTS solution OLP EXAM STUDENTS NEWS ICTU 2017

Here's Threads, guide the, explanation of exam. The code is written in C language, other languages ​​do the same. All posts are entered using the standard output (typing, output to the screen).

Download PDF File

Posts 1: Revenue (50 point)

Threads:

REVENUE

Runtime: 1 cause

Point: 50

The world economy is doing a statistics on sales of businesses globally. They surveyed a random national business and record sales (calculated by $). The problem is there are a lot of businesses surveyed and the money of many businesses is enormous (can come 1000 billion $) make economists confused. Your task is to help the economy filter out the largest revenue and the smallest revenue of businesses surveyed.

Input:

– The first line consists of 1 integer n is the number of businesses surveyed ( 5 <= n <= 10⁵ ).

– The second line contains n integers a_in with a_in Enterprise revenue was ith, each number separated by a space
( |the_in| <= 10¹² ).

Output:

Including 2 number, each number is located on a line and revenue respectively the largest and the smallest found.

Example:

DOANHTHU.INP	DOANHTHU.OUT
10 1 2 8 8 3 4 11 6 6 7	11 1

Suggestions, The answer:

The essence of the problem is to enter the integer n, find and print the largest number, Our smallest. We use an array the to save some. Max and min variables used to store the largest value and the smallest. However it should be noted:

• Initially assigned max and min value is a[0] should not be labeled as 0 or any other some.

• The data type of the array a and max, min should be long long for |the_in| <= 10¹²_. You can refer to limit the magnitude of the type on the network. when used long long, Import-export format is %LLD.

Code: file name: DOANHTHU.c

#include <stdio.h>

int main()
{
	int n, i;
	scanf("%d", &n);
	
	long long a[n], max, min;

	for (i = 0; i < n; i++) 
	{
		scanf("%lld", &a[i]);	
	}

	max = min = a[0];

	for(i = 0; i < n; i++) 
	{
		if(max < a[i]) max = a[i];
		if(min > a[i]) min = a[i];
	}

	printf("%lld\n%lld", max, min);

	return 0;
}

Posts 2: Sim beautiful (30 point)

Threads:

simsodep

Runtime: 2 seconds

Point: 30

To celebrate the birthday of strength so parents have decided to buy an iPhone enhance X. Of course comes with the device is a number of beautiful sim. His powers want to look for some of their own beautiful way. Parents gave strength to a sim some nice shops, Intensity would prefer a sim satisfy conditions 5 end of both of symmetry and as a prime number.

Symmetry is the number read from left to right or to the left, it is still a number (example 12321). (Note This article only consider the numbers 5 digits symmetry does not correspond to 5 last digit of sim).

Prime number is a positive integer that can only 2 The only convention 1 and itself (examples of 7)

Given two integers a, b correspond 10⁴ <= A < b < 10⁵

Please help Cuong counts some nice sim satisfactory on that in paragraph [the,b].

Head at:

Two integers a, b separated by a space (10⁴ <= A < b < 10⁵)

Head out:

A single integer is the number of the beautiful sim.

Example

SIMSODEP.INP	SIMSODEP.OUT
11111 33333	32

Suggestions, The answer:

Nature problem is just counting the number of last number is prime, just as some symmetry in paragraph [the,b] (10⁴ <= A < b < 10⁵).

So you just need to learn how to check 1 number is prime and not checked 1 symmetry number is not to be. Then browse each number from a to b. Note the comment in paragraph [the, b] so we must consider both a and b.

How to check a number n is prime, not:

• If n < 2 it is not a prime number.

• If n > 2. Browse from 2 the square root of n, if n is divisible then some period in this paragraph, then n is not a prime number, if after inspection that it is not divisible by the number n is prime.

Checking n (have 5 number) symmetry is not.

Suppose n consists 5 digits ABCDE.

Get a comparison with e, Get b compared to d. If a = e and b = d, then n is the number of symmetry. Conversely, it is not. I have:

a = n / 10000.

and n = % 10.

After comparing see a = e had removed a and f out by n to get BCD:

n = (n000) / 10 ( In that: % 10000 to take BCDE, further subdivided for 10 to take bcd). From here there:

b = n / 100

d = n % 10

("%" Is the division took balances, by n is an integer, 10, 100, 10000 should also be an integer "/" is the integer portion division).

Code: File name: SIMSODEP.c

#include <stdio.h>	// scanf, printf
#include <math.h>	// sqrt 

/* Kiem tra so n la so nguyen to khong
	Tra ve 1 neu la so nguyen to
	Tra ve 0 neu khong la so nguyen to
*/

int ktNT (int n) {		
	if(n < 2) return 0;
	int m = sqrt(n);
	for(int i = 2; i <= m; i++ ) {
		if(n % i == 0) return 0;
	}
	
	return 1;
}

/* Kiem tra so n co la so doi xung khong (n co 5 chu so)
	Tra ve 1 neu la so doi xung
	Tra ve 0 neu khong la so doi xung
*/

int ktDX(int n) {
	if(n % 10 == n / 10000) {
		n = (n%10000) / 10;
		if(n % 10 == n / 100) {
			return 1;
		}
	}
	return 0;
}

int main()
{	
	int a, b, i, dem = 0;
	scanf("%d%d", &a, &b);

	for(i = a; i <= b; i++) {
		if(ktNT(i) && ktDX(i)) {
			dem++;
		}
	}
	printf("%d", dem);
	return 0;
}

Bài 3: Robot (20 điểm)

Đề bài:

ROBOT

Runtime: 1 cause

Point: 20

UIT&TT is a team Robocon 2018. Robocon law of the year 2018 is to make the fastest robot from starting point to destination, however according to some rules:

For a record grid of squares of integers from 0 to 100. These numbers are a time (seconds) the robots must stop upon entering the cell. Ie if the robot goes into cells with values 5 must stop 5 seconds. Robots must always go from left to right direction ie can go cross on the right corner, diagonal down-right corner, or straight to right. Each time going into a cell only.

Initially, Robots may be derived from any cell of the first column and to follow rules on a cell to any of the last column is stopped.

Teams are suffering from a problem is how to find my way to a total time of the landing of the robot is the shortest (Excluding travel time switch, only time stopped in the box).

Input:

• The first line consists of 2 positive integer n, m respectively number of rows and columns of the grid.

• n the next line, each containing m numbers (each number with a value of 0 to 100).

Output:

• A unique number is the shortest time the robot can go from left to right.

Example:

ROBOT.INP	ROBOT.OUT
4 3 4 5 7 5 2 1 6 5 3 5 6 9	7

Giải thích: Với lưới ô vuông 4x3 như trên, robot có thể đi như sau để được tổng thời gian dừng là bé nhất: A[0][0] → A[1][1] → A[1][2] , do vậy tổng thời gian dừng là 4 + 2 + 1 = 7.

Gợi ý, lời giải:

Bài này bản chất là tìm đường đi sao cho từ một ô bất kỳ cột đầu tiên đên ô bất kỳ cột cuối cùng mà tổng đường đi là bé nhất.

Giả sử ta tìm và tính được tất cả các ô tại cột cuối cùng là bé nhất có thể khi đi từ một ô nào đó ở cột đầu tiên đến cột cuối cùng. Khi đó kết quả chính là ô bé nhất trong các ô ở cột cuối cùng.
Theo quy tắc từ một ô, ta có thể đi tới 3 ô ở cột tiếp theo như sau:




Do vậy, ta cũng có thể suy ra là để đi tới một ô nào đó, ta có thể xuất phát từ một trong 3 ô ở cột trước.

Giả sử ta đi tới ô [i][j] thì ô này sẽ có thể đi từ 3 ô cột trước là: [i-1][j-1], [i][j-1], [i+1][j-1]. Để ô [i][j] bé nhất, ta chỉ cần cộng giá trị của nó với ô bé nhất trong 3 ô kia là được. Cứ làm theo quy tắc đó, ta có thể tính lần lượt các của các cột từ trái sang phải.

Ta tạo ra ma trận b để chứa kết quả đường đi. Vậy lưới ô vuông như ví dụ. ta tính được như sau: (ma trận a bên trái, ma trận b bên phải).




• Cột đầu tiên của ma trận b ta giữ nguyên như cột đầu tiên của ma trận a.

• Để đi đến ô b[0][1], ta có thể đi từ b[0][0] hoặc b[1][0], nhưng để b[0][1] bé nhất thì phải chọn đi từ b[0][0] khi đó b[0][1] = a[0][1]+ b[0][0] = 5 + 4 = 9.

• Để đi đến b[1][1] ta có thể đi từ b[0][0] hoặc b[1][0] hoặc b[2][0], nhưng để b[1][1] bé nhất ta phải chọn đi từ b[0][0], khi đó b[1][1] = a[1][1] + b[0][0] = 2 + 4 = 6.

• Tương tự với các ô khác, ta sẽ có được bảng thứ 2 như trên.

Thuật toán này gọi là Quy hoạch động. Ngoài ra các bạn có thể sử dụng các thuật toán duyệt đồ thị đểm làm bài này cũng được nhưng sẽ phức tạp hơn chút.

Để code bài này, chúng ta cần lưu ý là đi đến ô [i][j] có thể đi từ 3 ô là [i-1][j-1], [i][j-1], [i+1][j-1], do vậy cẩn thận với i – 1, j – 1. Chúng ta thêm các ô bao quanh để tránh bị sai sót. Do số lớn nhất của 1 ô là 100, do vậy tổng lớn nhất của tất cả các ô là 106, chúng ta tìm nhỏ nhất nên chỉ cần để các ô bao quanh là 106 +1 (M) thì trong quá trình tính toán sẽ không ảnh hưởng gì đến kết quả bé nhất.

M	M	M
4	9	13
5	6	7
6	10	9
5	11	19
M	M	M

File name: ROBOT.c

#include <stdio.h>

#define M  1E6 + 1

/* Tim so lon nha trong 2 so */
int min2 (int a, int b) 
{
	return a < b ? a : b;
}

/* Tim so lon nha trong 3 so */
int min3 (int a, int b, int c)
{
	return min2 ( a, min2 (b, c) );
}

int main()
{
	int m,n;
	int a[102][100];
	int b[102][100];
	
	int i,j,s;
	
	scanf("%d%d", &m, &n);
	
	for(i = 1; i <= m; i++)
		for(j = 0; j < n; j++) 
			scanf("%d", &a[i][j]);
			
	// cho cot dau cua b bang cot dau cua a
	for (i = 1; i <= m; i++) 
		b[i][0] = a[i][0];

	// hang dau va hang cuoi cua b nhan gia tri lon nhat M
	for(j = 0; j < n; j++)
	{
		b[0][j] = M;
		b[m+1][j] = M;
	}

	// Tinh toan ma tran b. 
	for(j = 1; j < n; j++)
		for(i = 1; i <= m; i++) 
			b[i][j] = a[i][j] + min3 (b[i-1][j-1], b[i][j-1], b[i+1][j-1]);

	// duyet cot cuoi cung cua ma tran b tim min trong cot cuoi.
	s = M;
	for(i=1; i<= m; i++)
		if(s > b[i][n-1])
			s = b[i][n-1];
	
	printf("%d", s);

	return 0;
}