回答学生コンピューティングOLP ICTU 2017

11月 21, 2017 nguyenvanquan7826 アルゴリズム 応答を残し

ヒントソリューションOLPのEXAMの学生NEWS ICTU 2017

ここにスレッドです, ガイド, 試験の説明. コードはC言語で書かれています, 他の言語は、同じことを行います. すべての投稿は、標準出力を使用して入力します (タイピング, 画面に出力).

PDFファイルをダウンロード

投稿 1: 売上高 (50 ポイント)

スレッド:

の売上高

ランタイム: 1 原因

ポイント: 50

世界経済は、世界的に事業の売上高の統計を行っています. 彼らはランダムな国家事業とレコードの売上を調査しました (で計算 $). 問題は、調査対象企業の多くがあり、多くの企業のお金は膨大です (来るかもしれません 1000 十億 $) 経済学者が混乱して作ります. あなたの仕事は経済が最大の収益と、調査対象企業の最小の収入をフィルタリングできるようにすることです.

入力:

– 最初の行は、で構成されてい 1 整数nは、調査対象企業の数です ( 5 <= A <= 105 ).

– 2行目は、n個の整数を含んでいますで とともにで 企業収益は、i番目でした, スペースで区切られた各番号
( |ザ·で| <= 1012 ).

出力:

なります 2 数, 各番号は、それぞれのラインと収益の最大と最小FOUNDに位置しています.

例:

DOANHTHU.INP

DOANHTHU.OUT

10

1 2 8 8 3 4 11 6 6 7

11

1

提案します, 答え:

問題の本質は、整数nを入力することです, 見つけて、最大数を印刷, 私たちの最も小さいです. 私たちは、配列を使用します ザ· 一部を保存します. 最大と最小の最大値を格納するために使用される変数と最も小さいです. しかし、注意すべきです:

  • 最初に割り当てられた最大値と最小値はAです[0] 表示されるべきではありません 0 または任意の他のいくつかの.

  • 配列aと最大のデータ型, 分はする必要があります 長い長いです 以下のために |ザ·で| <= 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

強度の誕生日を祝うために両親はXを強化するiPhoneを購入することを決定しましたので、. もちろん、美しいシムの数は、デバイスとされています. 彼の力は、自分の美しい道の一部について見てみたいです. 両親はSIMにいくつかの素晴らしいお店が力を与えました, 強度は、SIMが条件を満たし好みます 5 対称性の両方の素数として終了.

対称性は、それはまだ数、左から右または左に読ま数です (例 12321). (この記事では、数字のみを考慮します 5 に対応していない数字対称性 5 シムの最後の桁).

素数ができるだけで、正の整数であります 2 唯一の大会 1 それ自体 (の例 7)

与えられた二つの整数, B対応 104 <= A < B < 105

クオンは、段落内のその上満足のいくいくつかの素晴らしいシムをカウント助けてください [ザ·,B].

ヘッド で:

二つの整数, Bスペースで区切っ (104 <= A < B < 105)

ヘッド アウト:

単一の整数は美しいシムの数であります.

例

SIMSODEP.INP

SIMSODEP.OUT

11111 33333

32

提案します, 答え:

自然の問題は、ちょうど最後の番号の数が素数であるカウントされます, ただ、段落内のいくつかの対称性 [ザ·,B] (104 <= A < B < 105).

だから、あなただけをチェックする方法を学ぶ必要があります 1 番号がチェックプライムとではありません 1 対称番号はならないです. そして、aからbまでの各番号を参照. 段落のコメントを注意してください [ザ·, B] 私たちは、AとBの両方を考慮しなければなりません.

番号を確認nは素数である、ないにする方法:

  • n個の場合 < 2 それは素数ではありません.

  • n個の場合 > 2. からブラウズ 2 n個の平方根, nは、この段落の一部の期間割り切れるである場合、nが素数ではありません, それが数nで割り切れないこと検査後は素数である場合.

n個のチェック (持っている 5 数字) 対称ではありません.

仮定nは構成されてい 5 数字ABCDE.

電子との比較を取得, Dに比べてBゲット. = eおよびB = Dの場合、nは対称の数であります. 逆に、そうではありません. 私が持っている:

N = / 10000.

そしてn = % 10.

参照比較した後= eは削除していたとBCDを取得するためのnでf outは:

N = (n個の％10000) / 10 ( その中で: % 10000 BCDE取ります, さらに細分化のために 10 BCDを取ります). そこここから:

B = N / 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, Mグリッドの行と列のそれぞれ数.

  • 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;
}