回答学生计算OLP ICTU 2017

十一月 21, 2017 nguyenvanquan7826 算法 留下一个回应

HINTS解决方案OLP考试的学员NEWS ICTU 2017

这里的主题, 引导, 考试说明. 该代码是用C语言编写, 其他语言做同样的. 所有职位都使用标准输入输出 (打字, 输出到屏幕).

下载PDF文件

帖子 1: 营业额 (50 点)

主题:

成交

运行: 1 原因

点: 50

世界经济正在销售的企业做全球统计. 他们调查随机全国业务和销售记录 (通过计算 $). 问题是有很多的受访企业和众多商家的钱是巨大的 (可能会 1000 十亿 $) 令经济学家感到困惑. 你的任务是帮助经济筛选出最大的收入和企业调查的最小收益.

输入:

– 第一行包括 1 整数n是被调查企业数 ( 5 <= N <= 105 ).

– 第二行包含n个整数一个在 用在 企业营收为第i个, 用空格隔开的每个号码
( |该在| <= 1012 ).

产量:

含 2 号码, 每个号码分别位于线路和收入的最大和最小FOUND.

例:

DOANHTHU.INP

DOANHTHU.OUT

10

1 2 8 8 3 4 11 6 6 7

11

1

建议, 答案:

这个问题的实质是进入整数n, 找到并打印数量最多, 我们最小. 我们使用数组 该 节省一些. 最大和最小的变量用于存储的最大值和最小. 但是应该注意的:

  • 最初分配的最大和最小的值是一个[0] 不应该被标注为 0 或任何其他的一些.

  • 所述阵列的和最大的数据类型, 分应该是 很长很长 为 |该在| <= 1012. 您可以参考来限制网络上的类型的大小. 使用时 很长很长, 进出口格式 %LLD.

代码: 文件名: 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;
}

帖子 2: 辛美丽 (30 点)

主题:

simsodep

运行: 2 秒

点: 30

为了庆祝强度的生日所以家长已经决定买一部iPhone提升X. 当然自带设备被众多美丽的SIM卡. 他的力量要寻找自己的一些美丽的方式. 父母给了力量到SIM一些不错的店, 强度宁愿一个SIM满足条件 5 两个对称的和为素数结束.

对称是从左向右或向左读出数字，它仍然是一个数 (例 12321). (注意：本文只考虑数字 5 数字对称不符合 5 SIM卡的最后一位).

质数是一个正整数，只能 2 唯一的约定 1 和本身 (示例 7)

给定两个整数a, b分别对应 104 <= A < B < 105

请帮助库·康特斯一些不错的SIM卡上，在一段令人满意 [该,B].

头 在:

两个整数a, b。通过用空格隔开 (104 <= A < B < 105)

头 出:

一个整数是美丽的SIM卡的数量.

例

SIMSODEP.INP

SIMSODEP.OUT

11111 33333

32

建议, 答案:

自然的问题是只计算最后一个号码的数量为素数, 正如一些段对称 [该,B] (104 <= A < B < 105).

所以，你只需要学习如何检查 1 数是素数，未选中 1 对称数是不是要. 然后从一个浏览每个数字至b. 注意段落的评论 [该, B] 因此，我们必须考虑a和b.

如何检查数n是素数，而不是:

  • 如果n < 2 它是不是质数.

  • 如果n > 2. 从浏览 2 n的平方根, 如果n整除那么在这段时期一些，那么n不是素数, 如果经检查，这是不是整除数n是素数.

检查ñ (有 5 数字) 对称是不.

假设n包含 5 数字ABCDE.

获得随e的比较, 获取比d b. 如果A = E和B = d，则n是对称的数. 相反，它是不是. 我有:

A = N / 10000.

且n = % 10.

比较看后= E已经删除和n个获得BCD˚F出:

N = (N％10000) / 10 ( 在这: % 10000 采取BCDE, 进一步细分为 10 采取BCD). 从这里有:

B =Ñ / 100

d = N % 10

(“％”是分裂了余额, 由n是一个整数, 10, 100, 10000 也应该是一个整数“/”是整数部分除法).

代码: 文件名: 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:

机器人

运行: 1 原因

点: 20

UIT&TT是一个团队的机器人大赛 2018. 今年的机器人大赛法 2018 是从出发点到目的地做出最快的机器人, 然而，根据一定的规则:

对于来自整数的平方的记录格 0 到 100. 这些数字是时间 (秒) 机器人必须停止在进入细胞. 即，如果机器人进入与值的单元 5 必须停止 5 秒. 机器人必须由左到右的方向，即去可以去出右侧角球横, 角右下拐角, 或直右. 每次进入一个细胞只.

开始, 机器人可以从第一列的任意单元格中导出，并且任何最后一列的停止跟随在细胞规则.

团队是从问题的痛苦是如何找到我的方式向机器人着陆的总时间最短 (剔除旅行时间开关, 唯一一次停在箱).

输入:

  • 第一行包括 2 整数n, 米分别编号网格的行和列的.

  • n中的下一行, 每个包含m个 (用的值中的每个数 0 到 100).

产量:

  • 独特的数字是最短的时间内机器人可以由左向右走.

例:

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

文件名: 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;
}