Đề ôn tập môn Tin học THCS - Đề số 8 - Năm học 2024-2025

Nội dung tài liệu: Đề ôn tập môn Tin học THCS - Đề số 8 - Năm học 2024-2025

1. De on so 8 NUMBER2.pas Description Tèo có một số lá bài, trong đó có Ai lá bài ghi giá trị i. Hai lá bài x, y được gọi là một cặp nếu |x-y| ≤1 Hỏi Tèo có thể tạo tối đa bao nhiêu cặp lá bài biết rằng không có lá bài nào nằm trong hai cặp khác nhau. Input Dòng đầu ghi số nguyên dương N (1≤N≤105) N dòng tiếp theo, mỗi dòng gồm một số nguyên Ai (1≤Ai≤109) Output Kết quả bài toán Sample Input 1 4 4 0 3 2 Sample Output 1 4 Hint Có: 4 lá bài ghi số 1, 0 lá bài ghi số 2, 3 lá bài ghi số 3, 2 lá bài ghi số 4,
2. Có thể tạo tối đa 4 cặp lá bài (1,1),(1,1),(3,4),(3,4) var a: array[0..100000] of longint; t,kq:int64;i,n:longint; f,g:text; Begin assign(f,'number2.inp'); reset(f); assign(g,'number2.out'); rewrite(g); Readln(f,n); for i:=1 to n do readln(f,a[i]); t:=0; for i:=1 to n+1 do begin t:=t+a[i]; if a[i]=0 then begin kq:=kq+t div 2; t:=0; end; end; Write(g,kq); Close(f); Close(g); end. REVERSE.pas Description Trong lúc buồn chán, Dũng đã tìm một xâu s gồm ∣s∣ kí tự là các chữ cái tiếng Anh in thường và đảo ngược một số xâu con liên tiếp của xâu s. Viết chương trình tìm xâu s sau khi Dũng thực hiện lần lượt m đảo. Input Dòng đầu ghi xâu s, (2≤∣s∣≤2×105) Dòng thứ hai là số nguyên m (1≤m≤105) Dòng thứ ba gồm m số nguyên ai (1≤ai≤2∣s∣), mỗi số mô tả lần đảo một xâu con liên tiếp từ kí tự thứ ai đến kí tự thứ ∣s∣−ai+1 của Dũng. Các kí tự trong xâu s được đánh số từ 1 đến ∣s∣. Output Dòng duy nhất ghi xâu ss sau khi Dũng thực hiện lần lượt mm lần đảo. Sample Input 1 kcchinbayble 4
3. 2 2 2 2 Sample Output 1 kcchinbayble Sample Input 2 haideu 1 1 Sample Output 2 uediah Hint •Ở ví dụ 1, Dũng đảo xâu con từ kí tự thứ 2 đến kí tự thứ 11 một số chẵn lần nên xâu không thay đổi Ở ví dụ thứ 2, Dũng đảo cả xâu s var f,g:text; s:ansistring; m,n,i,x,kt:longint; tg:char; d:array[0..1000000] of longint; begin assign(f,'reverse.inp'); reset(f); assign(g,'reverse.out'); rewrite(g); readln(f,s); readln(f,m); for i:=1 to m do begin read(f,x); inc(d[x]); end; kt:=0; for i:=1 to length(s) div 2 do
4. begin if d[i] mod 2 = 1 then inc(kt); if kt mod 2 = 1 then begin tg:=s[i]; s[i]:=s[length(s)-i+1]; s[length(s)-i+1]:=tg; end; end; writeln(g,s); close(f); close(g); end. Tree.pas) giới hạn thời gian cho mỗi bài kiểm tra 2 giây giới hạn bộ nhớ cho mỗi bài kiểm tra 512 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Người làm vườn Alexey dạy lập trình cạnh tranh cho học sinh trung học. Để chúc mừng Alexey vào Ngày nhà giáo, các sinh viên đã tặng anh một bộ sưu tập gậy gỗ, trong đó mỗi cây gậy đều có chiều dài nguyên. Bây giờ Alexey muốn trồng một cây từ họ. Cây trông giống như một đa tuyến trên mặt phẳng, bao gồm tất cả các que. Đa tuyến bắt đầu tại điểm( 0 , 0 ). Trong khi xây dựng đa tuyến, Alexey sẽ gắn từng que theo từng thứ tự tùy ý. Mỗi thanh phải thẳng đứng hoặc nằm ngang (nghĩa là song song với OX hoặc là O Y). Không được phép hai thanh liên tiếp được căn chỉnh đồng thời theo chiều ngang hoặc đồng thời theo chiều dọc. Xem hình ảnh dưới đây để làm rõ. Alexey muốn tạo ra một đa tuyến theo cách mà kết thúc của nó càng xa càng tốt từ ( 0 , 0 ). Xin hãy giúp anh ấy trồng cây theo cách này. Lưu ý rằng đa tuyến xác định hình dạng của cây có thể có tự giao và tự chạm, nhưng có thể chứng minh rằng câu trả lời tối ưu không chứa bất kỳ giao điểm hoặc tự chạm nào. Đầu vào Dòng đầu tiên chứa một số nguyên nn (1 ≤ n ≤ 100000) - số gậy mà Alexey có được như một món quà. Dòng thứ hai chứa nn số nguyên a1, ... , an (1 ≤ ai≤ 10000) - chiều dài của gậy.
5. Đầu ra In một số nguyên - là vuông của khoảng cách lớn nhất có thể từ( 0 , 0 ) đến cuối cây. Ví dụ đầu vào Sao chép 3 1 2 3 đầu ra Sao chép 26 đầu vào Sao chép 4 1 1 2 2 đầu ra Sao chép 20 Ghi chú Các hình ảnh sau đây cho thấy cây tối ưu cho các thử nghiệm ví dụ. Khoảng cách bình phương trong ví dụ đầu tiên bằng5 ⋅ 5 + 1 ⋅ 1 = 265⋅5+1⋅1= =26và trong ví dụ thứ hai 4 ⋅ 4 + 2 ⋅ 2 = 204⋅4+2⋅2= =20.
6. 1. var n,i:longint; 2. ans,ans1:int64; 3. a:array[1..100000]of longint; 4. procedure qsort(l,r:longint); 5. var i,j,k,mid:longint; 6. begin 7. i:=l;j:=r; 8. mid:=a[(i+j) div 2]; 9. repeat 10. while a[i]<mid do inc(i); 11. while a[j]>mid do dec(j); 12. if i<=j then 13. begin 14. k:=a[i];a[i]:=a[j];a[j]:=k; 15. inc(i); 16. dec(j); 17. end; 18. until i>j; 19. if i<r then qsort(i,r); 20. if j>l then qsort(l,j); 21. end; 22. begin 23. readln(n); 24. ans:=0;ans1:=0; 25. for i:=1 to n do begin read(a[i]);ans:=ans+a[i];end; 26. qsort(1,n); 27. for i:=1 to n div 2 do ans1:=ans1+a[i]; 28. writeln(ans1*ans1+(ans-ans1)*(ans-ans1)); 29. end. Bakery.pas giới hạn thời gian cho mỗi bài kiểm tra 2 giây
7. giới hạn bộ nhớ cho mỗi bài kiểm tra 256 megabyte đầu vào đầu vào tiêu chuẩn đầu ra đầu ra tiêu chuẩn Masha muốn mở tiệm bánh của riêng mình và nướng bánh nướng xốp tại một trong n thành phố được đánh số từ 1 đến n . Có m đường hai chiều, mỗi đường nối một số thành phố. Để nướng bánh nướng xốp trong tiệm bánh của mình, Masha cần thiết lập nguồn cung cấp bột từ một số kho. Chỉ có k kho, nằm ở thành phố khác nhau được đánh số a 1 ,  a 2 , ...,  a k . Thật không may, luật pháp của đất nước Masha sống trong việc cấm mở tiệm bánh ở bất kỳ thành phố nào có kho lưu trữ trong đó. Cô ấy có thể mở nó chỉ trong một trong một n  -  k các thành phố, và, tất nhiên, giao hàng bột phải được thanh toán - cho mỗi km đường dẫn giữa lưu trữ và bánh Masha nên chú 1 rúp. Chính thức, Masha sẽ trả x rúp, nếu cô ấy sẽ mở tiệm bánh ở một số thành phố b ( a i  ≠  b cho mỗi 1 ≤  i  ≤  k ) và chọn một lưu trữ ở một số thành phố s ( s  =  a j đối với một số 1 ≤  j  ≤  k ) và b và s được kết nối bởi một số đường có chiều dài tóm tắt x (nếu có nhiều hơn một đường, Masha có thể chọn đường nào sẽ được sử dụng). Masha rất tiết kiệm và lý trí. Cô ấy quan tâm đến một thành phố, nơi cô ấy có thể mở tiệm bánh của mình (và chọn một trong những kho chứa k và một trong những con đường giữa thành phố với tiệm bánh và thành phố có kho) và trả số lượng rúp tối thiểu có thể để giao bột. Xin hãy giúp Masha tìm thấy số tiền này. Đầu vào Dòng đầu tiên chứa ba số nguyên n , m và k ( 1 ≤  n ,  m  10 5 , 0 ≤  k  ≤  n ) - số thành phố ở quốc gia Masha sống, số đường giữa chúng và số của kho bột tương ứng. Sau đó m dòng theo sau. Mỗi trong số chúng chứa ba số nguyên u , v và l ( 1 ≤  u ,  v  ≤  n , 1 ≤  l  ≤ 10 9 , u  ≠  v ) có nghĩa là có một con đường giữa các thành phố u và v có chiều dài l km. Nếu k  > 0 , thì dòng cuối cùng của đầu vào chứa k số nguyên khác nhau a 1 ,  a 2 , ...,  a k ( 1 ≤  a i  ≤  n ) - số thành phố có kho chứa bột nằm ở. Nếu k  = 0 thì dòng này không được trình bày trong đầu vào . Đầu ra In số lượng rúp tối thiểu có thể Masha phải trả cho việc giao bột trong dòng duy nhất. Nếu bánh không thể mở được (trong khi thỏa mãn điều kiện) trong bất kỳ n thành phố, in  - 1 trong dòng duy nhất.
8. Ví dụ đầu vào Sao chép 5 4 2 1 2 5 1 2 3 2 3 4 1 4 10 1 5 đầu ra Sao chép 3 đầu vào Sao chép 3 1 1 1 2 3 3 đầu ra Sao chép -1 Ghi chú Hình ảnh minh họa trường hợp mẫu đầu tiên. Các thành phố có kho lưu trữ nằm trong và con đường đại diện cho câu trả lời bị tối đi. 1. var a,b,c,f:array [1..100000]of integer;
9. 2. n,m,k,i,x,min:integer; 3. begin 4. read(n,m,k); 5. for i:=1 to m do 6. read(a[i],b[i],c[i]); 7. for i:=1 to k do 8. begin 9. read(x); 10. f[x]:=1; 11. end; 12. min:=1000000001; 13. for i:=1 to m do 14. if (f[a[i]]+f[b[i]]=1)then 15. if (c[i]<min)then min:=c[i]; 16. if (min=1000000001)then write(-1)else write(min); 17. end.