იმათ, ვისაც პროგრამირების ოლიმპიადაში მონაწილეობა არასოდეს მიგიღიათ, ალბათ გაგიჩნდებათ შეკითხვა - როგორია ეს ოლიმპიადები? რისი ცოდნაა საჭირო მათში მონაწილეობის მისაღებად, რა სახის დავალებებს იძლევიან და ამ დავალებების შესრულების ქვეშ რას მოიაზრებენ? არსებობს სხვადასხვა სახის შეჯიბრებები, რომლებიც პროგრამირებასთანაა დაკავშირებული, მაგრამ მათი უმეტესობა ერთნაირი სქემით ტარდება. ახლა მე შევეცდები, ზოგადი წარმოდგენა შეგიქმნათ ამ პროცესზე.

პროგრამირების შეჯიბრზე მონაწილეს ეძლევა ერთი კომპიუტერი, რამდენიმე ამოცანა და ფიქსირებული დროის შუალედი მათ ამოსახსნელად. ამოცანის ამოხსნა, განსხვავებით სხვა ოლიმპიადებისგან, არ გულისხმობს ფურცელზე რამის თეორიულად დამტკიცებას ან გამოყვანას. ამის მაგივრად, ოლიმპიადის მონაწილემ უნდა დაწეროს პროგრამა, რომელიც პირობაში მითითებულ დავალებას შეასრულებს გარკვეულწილი შეზღუდვების გათვალისწინებით. შემდეგ იგი ამ პროგრამის კოდს სერვერზე აგზავნის, სადაც ხორციელდება მისი გატესტვა. პროგრამის დასაწერად არ არის საჭირო რაიმე ტექნოლოგიების ღრმა ცოდნა, პირიქით, იგი ერთფაილიანი კონსოლური აპლიკაცია უნდა იყოს. განვიხილოთ ამის ორი ძირითადი მიზეზი.

პირველ რიგში, პროგრამას ასეთი მარტივი სახე იმისთვის უნდა ჰქონდეს, რომ მისი ავტომატურად გატესტვა იყოს შესაძლებელი. სერვერზე მას შემავალი მონაცემების რამოდენიმე კრებულზე (თითოეულს ტესტს ეძახიან) გაუშვებენ და შეამოწმებენ, რომ პროგრამამ თითოეულზე სწორი პასუხი გამოიტანოს. თუმცა სისწორის გარდა, პროგრამას კიდევ ორ მოთხოვნას უყენებენ: იგი საკმარისად სწრაფად უნდა მუშაობდეს და გამოყოფილ მეხსიერებაზე მეტს არ იყენებდეს. პროგრამის მუშაობის დროს და გამოყენებულ მეხსიერებას ყოველ ტესტზე ამოწმებენ.

მეორე და უფრო ზოგადი მიზეზი არის თვითონ ამ შეჯიბრებათა მიზანი. პროგრამირების ოლიმპიადები არა მარტო მონაწილეთა ცოდნას, არამედ პოტენციალსაც ამოწმებენ.

ახლა მოდით განვიხილოთ საოლიმპიადო ამოცანის სახე ერთი მარტივი ამოცანის მაგალითზე.

ამოცანა "ჯამი"

მოცემული ნატურალური რიცხვი N-ისთვის გამოთვალეთ 1-დან N-მდე ჩათვლით რიცხვების ჯამი.

შეზღუდვები: 1≤N≤100

შემომავალი მონაცემების ფორმატი: ფაილის ერთადერთი სტრიქონი შეიცავს რიცხვს N.

გამოსატანი მონაცემების ფორმატი: უნდა გამოიტანოთ ერთადერთი რიცხვი - 1-დან N-მდე რიცხვების ჯამი.

შემომავალი მონაცემების მაგალითი (ფაილი sum.in): 5

გამოსატანი მონაცემების მაგალითი (ფაილი sum.out): 15

ერთი ტესტის გავლის დროის შეზღუდვა: 1 წამი

ერთ ტესტზე გამოყენებული მეხსიერების შეზღუდვა: 64 MB

აი დაახლოებით ასეთი სახით არის ხოლმე მოცემული ამოცანის პირობა. დავალება, მე მგონი, გასაგებია. პირველი ამოხსნა, რაც შეიძლება თავში მოუვიდეს ადამიანს, არის 1-დან N-მდე ციკლის გაშვება და რიცხვების აჯამვა. ასეთი მიდგომის C++ ენაზე დაწერილ კოდს ასეთი სახე აქვს:

#include <cstdio>
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	int sum=0,N,i;
	scanf("%d",&N);
	for(i=1;i<=N;i++) sum+=i;
	printf("%d\n",sum);
	return 0;
}

აქ მინდა თქვენი ყურადღება გავამახვილო freopen ბრძანებებზე - მათი მეშვეობით თქვენ ახდენთ ფაილების სტანდარტულ შემავალ/გამომავალ ნაკადებზე გადამისამართებას, რაც ფაილებთან შემდგომი მუშაობისგან გარიდებთ და ოლიმპიადაზე დროს მოგაგებინებთ.

როდესაც ამ კოდს სერვერზე გააგზავნით, მას რამდენიმე ტესტზე შეამოწმებენ. ტესტებში, საზოგადოდ, არ იქნება ყველა შესაძლო შემავალი მონაცემების კრებული, მაგრამ იქნება იმდენი, რომ თუ თქვენი ამოხსნა მათ გადის, დიდი ალბათობით ითქვას, რომ იგი სწორია.

ეს ამოხსნა აბსოლუტურად საკმარისია მოცემული შეზღუდვების პირობებში (N≤100), მაგრამ ახლა დავუშვათ, რომ N ზევიდან ერთი მილიარდით იყო შემოსაზღვრული. თანამედროვე პერსონალური კომპიუტერი (სერვერიც ჩვეულებრივი კომპიუტერია) ერთ წამში ამდენ აჯამვას ვერ მოახდენს, ამიტომ ჩვენი მიდგომა უკვე უვარგისი ხდება. აქ უკვე სხვა ალგორითმის მოფიქრება გვიწევს, რომელიც ამ შემთხვევაში უბრალოდ არითმეტიკული პროგრესიის ჯამის ფორმულის გახსენებაში გამოიხატება: 1+2+...+N = (1+N)*N/2. თუმცა დაკვირვებული თვალი შენიშნავდა, რომ დიდი N-ისთვის ეს ჯამი აღარ ეტევა ჩვეულებრივ 32-ბიტიან ტიპში და საჭიროებს 64-ბიტიანი ტიპის გამოყენებას. ამ ყველაფრის გათვალისწინებით ჩვენი კოდი შემდეგნაირად გადაკეთდა:

#include <cstdio>
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	int N;
	scanf("%d",&N);
	long long sum=(N+1)*(long long)N/2;
	printf("%lld\n",sum);
	return 0;
}

ასევე შეგიძლიათ იხილოთ ამავე ამოცანის ამოხსნის კოდის მაგალითი სხვა პროგრამირების ენებზე:

var n,sum:int64;
begin
	assign(input, 'sum.in');
	reset(input);
	assign(output, 'sum.out');
	rewrite(output);
	readln(n);
	sum:=(n+1)*n/2;
	writeln(sum);
	close(input);
	close(output);
end.

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws FileNotFoundException, IOException {
		Scanner in = new Scanner(new File("sum.in"));
		PrintWriter out = new PrintWriter(new File("sum.out"));
		int N = in.nextInt();
		long sum = (N + 1) * (long) N / 2;
		out.println(sum);
		out.flush();
	}
}

using System;
using System.IO;

class Program
{
   static void Main(string[] args)
   {
       StreamReader sr = new StreamReader("sum.in");
       int n = Convert.ToInt32(sr.ReadLine());
       StreamWriter sw = new StreamWriter("sum.out");
       long result = 1L * n * (n + 1) / 2;
       sw.WriteLine(result.ToString());
       sr.Close();
       sw.Close();
   }
}

<?php
	$input = fopen('sum.in','r');
	$output = fopen('sum.out','w');
	fscanf($input,'%d',&$n);

	$sum = bcmul(($n + 1),$n/2);
	fprintf($output,"%s\n",$sum);

	fclose($input);
	fclose($output);
?>

არსებობს ოლიმპიადების სხვადასხვა ფორმატი, რომლებიც განსხვავდება ხანგრძლივობით, ამოცანების რაოდენობით, შეფასების სისტემით, მონაწილეთა რანჟირების წესებით, etc. მაგალითად, მოსწავლეთა საერთაშორისო ოლიმპიადაზე იძლევიან 4 ამოცანას და 5 საათს მათ ამოსახსნელად. მონაწილე თავისი პროგრამის მიერ ნაჩვენებ შედეგს ოლიმპიადის დამთავრებამდე ვერ იგებს, ანუ მან ლოკალურად მაქსიმალურად უნდა გატესტოს თავისი ნამუშევარი. სამაგიეროდ, მას ეწერება ქულა ყოველ ცალკეულ გავლილ ტესტში, ანუ შეიძლება არასაკმარისად სწრაფი ან არც თუ მთლად სწორი პროგრამით დააგროვოს რაღაც ქულა. სრულიად საპირისპირო სისტემით ტარდება სტუდენტური ოლიმპიადების უმეტესობა. ასეთ ოლიმპიადებზე, მონაწილეს ამოცანა ჩათვლილად მხოლოდ მაშინ ეთვლება, თუ ის ყველა ტესტს გადის (და რანჟირება ამოცანების რაოდენობით ხდება). პასუხს, სწორია თუ არა მისი ამოხსნა, მონაწილე კოდის სერვერზე გაგზავნისთანავე იგებს. ჩვენი სერია ზუსტად ასეთი სისტემით ჩატარდება.

eJudge სისტემის გამოყენების ინსტრუქცია

მაშ ასე, იმათ, ვისაც ოლიმპიადებზე არ გქონიათ შეხება eJudge სისტემასთან, ანაც სულაც არ გქონიათ პროგრამირების შეჯიბრებებში მონაწილეობის გამოცდილება, სისტემა პირველ ჯერზე შეიძლება გაუგებრად მოგეჩვენოთ. ჩვენ არ გვინდა, რომ ამასთან რაიმე პრობლემები შეგექმნათ, ამიტომ შევეცდები მაქსიმალურად სრულად აღვწერო ყველაფერი, რაც შეიძლება eJudge-ში მოგიწიოთ. ჩვენ შექმნილი გვაქვს ე.წ. "სატესტო" ტური, სადაც თქვენ ინტერნეტ-რაუნდებამდე შეგიძლიათ გამოცადოთ სისტემა. ამ ტურში არის რამდენიმე მარტივი ამოცანა, რომლებიც სისტემასთან გარკვევაში დაგეხმარებიან. თვითონ სატესტო ტური რეალური რაუნდისგან ტექნიკურად მხოლოდ იმით განსხვავდება, რომ იგი უვადოა და მასში შესვლა და ამოცანების ამოხსნა ნებისმიერ დროს შეგიძლიათ (თუმცა ჯერ-ჯერობით არ გვაქვს შესაძლებლობა, რომ სერვერი სულ იყოს მუშა მდგომარეობაში). სატესტო ტურში შესასვლელად უნდა მიჰყვეთ ბმულს.

აი, მოვხვდით კიდევაც eJudge სისტემაში. ნებისმიერ რაუნდში შესვლისას თქვენ ანალოგიურ გვერდზე აღმოჩნდებით, სადაც თქვენი მომხმარებლის სახელის და პაროლის შეყვანას მოგთხოვენ. ასევე არის შესაძლებლობა, რუსულ ენაზე გადაიყვანოთ ინტერფეისი. ამ ყველაფრის შემდეგ უნდა დააჭიროთ ღილაკს "Log in". შედეგად თქვენ აღმოჩნდებით შეჯიბრების გვერდზე. თუ თქვენ სისტემაში რაუნდის დაწყებამდე შეხვალთ, გვერდს ასეთი სახე ექნება:

აქ ბევრ ვერაფერს გააკეთებთ, მაქსიმუმ შეგიძლიათ Settings მენიუში პაროლი შეიცვალოთ.

ხოლო თუ თქვენ მიმდინარე რაუნდის გვერდზე შეხვალთ, მაშინ რადიკალურად განსხვავებულ სურათს ნახავთ:

პირველი, რაც დაგჭირდებათ მიმდინარე შეჯიბრების დროს - ამოცანების პირობები. ინტერნეტ-რაუნდებისთვის ჩვენ დაარქივებულ პირობებს საიტზე წინასწარ დავდებთ, ვინაიდან ზოგჯერ პირობები საკმაოდ დიდია ზომაში და ამის გამო ნელი ინტერნეტის მქონე მონაწილეები დაზარალდებიან. არქივს პაროლი ედება, რომელიც რაუნდის დაწყებისთანავე გამოჩნდება სისტემაში. ამისთვის უნდა გადახვიდეთ მენიუზე "Clars" და შესაბამისი შეტყობინება წაიკითხოთ.

ასევე პირობები ღია სახით რაუნდის დაწყებისთანავე იქნება ხელმისაწვდომი მენიუ "Statements"-ში.

შემდეგი, რაც უნდა შეგეძლოთ, არის ამოხსნის სერვერზე გაგზავნა. შეამჩნევდით, რომ მენიუებში "Info", "Summary" და "Submissions" ჩამოწერილია ასოები A, B, C, D, E. ეს ასოები შეესაბამებიან ამოცანებს (საზოგადოდ, იქ შეიძლება ნებისმიერი ტექსტი ეწეროს, მაგრამ ჩვენს ინტერნეტ-რაუნდებზე ამოცანები ყოველთვის A-დან E-მდე იქნება "გადანომრილი"). რომელიმეს რომ დააჭიროთ, მოხვდებით ამ ამოცანის ინტერფეისში, სადაც შემოთავაზებულია გარკვეულწილი ინფორმაცია (შემავალი და გამომავალი ფაილის სახელი, ერთ ტესტზე დროის და მეხსიერების შეზღუდვა), რომლის პოვნა ამოცანების პირობებშიც შეგიძლიათ. ასევე ამ ინტერფეისიდან ხდება შესაბამის ამოცანაზე ამოხსნის გაგზავნა. ამისთვის Language-ში უნდა აირჩიოთ ის ენა, რომელზეც დაწერილია თქვენი კოდი (მაგალითად fpc პასკალისთვის; javac Java-სთვის და gcc C++-ისთვის), File-ში მიუთითოთ თქვენი კოდის მისამართი თქვენს კომპიუტერზე და დააჭიროთ ღილაკს Send.

შედეგად ამ ამოცანისთვის გაჩნდება "Previous submissions of this problem", სადაც შეგიძლიათ ნახოთ თქვენს ამოხსნაზე გამოტანილი ვერდიქტი. OK ნიშნავს, რომ ამოხსნამ ყველა ტესტი გაიარა და შესაბამისად ამოცანა ჩაგეთვალათ.

OK-ის გარდა, ამოხსნამ შეიძლება მიიღოს შემდეგი ვერდიქტები:

Wrong answer - ერთ-ერთ ტესტზე თქვენმა ამოხსნამ არასწორი პასუხი გამოიტანა. თვითონ ტესტის ნახვა არ შეგიძლიათ, მაგრამ გეძლევათ მისი ნომერი "Failed test" სვეტში და ამით შეგიძლიათ რაღაც დასკვნები გამოიტანოთ. საოლიმპიადო ამოცანებში 20-იდან 100 ტესტამდე არის ხოლმე ამოცანის სპეციფიკიდან გამომდინარე და მაგალითად თუ თქვენი ამოხსნა 30-ე ტესტზე იჭრება, დიდი ალბათობით შეგიძლიათ თქვათ, რომ მიდგომა სწორია და პატარა შეცდომაა გამოპარული - აბა 29 ტესტს როგორ გაივლიდა :)

Presentation error - თქვენი კოდის მიერ გამოტანილი პასუხის ფორმატი არ შეესაბამება მოთხოვნილს.

Time-limit exceeded - ერთ-ერთ ტესტზე თქვენმა ამოხსნამ მითითებულ დროის შეზღუდვაზე უფრო დიდხანს იმუშავა.

Memory limit exceeded - ერთ-ერთ ტესტზე თქვენმა ამოხსნამ გამოყოფილ მეხსიერებაზე უფრო მეტის გამოყენება სცადა.

Run-time error - ერთ-ერთ ტესტზე თქვენი ამოხსნის შესრულებისას შეცდომა დაფიქსირდა. მაგალითად, ეს შეიძლება იყოს ნულზე გაყოფის მცდელობა, მასივის ფარგლებს გარეთ გასვლა, სტეკის გადავსება.

Compilation error - თქვენი კოდი არ დაკომპილირდა. ამ დროს "View report" სვეტში თქვენ შეგიძლიათ დეტალები შეამოწმოთ.

Check failed - ეს ნიშნავს, რომ ამოხსნის გატესტვა ვერ მოხერხდა. ეს არის ხოლმე დაკავშირებული სერვერის რაიმე პრობლემასთან და ამ შემთხვევაში უნდა დაელოდოთ ორგანიზატორების რეაქციას.

ოლიმპიადების დროს ხშირად ძალზედ მნიშვნელოვანია იცოდეთ თქვენი კონკურენტების მიმდინარე შედეგი. იმის გარდა, რომ ჩნდება სპორტული აზარტი, თქვენ შეგიძლიათ ნახოთ, რომელ ამოცანებს ხსნის ხალხი და ამით შეაფასოთ ამოცანის სირთულე. რეალურ შეჯიბრებებზე, როდესაც 5 საათში 10 ამოცანა უნდა ამოხსნათ, ყველა ამოცანაზე სერიოზულ ფიქრს უბრალოდ ვერ მოასწრებთ. eJudge-ში მიმდინარე ცხრილის სანახავად არსებობს მენიუ "Standings".

"გავშიფროთ" ის ცხრილი, რომელსაც სურათზე ხედავთ. აქ ჩანს, რომ შეჯიბრებაში ჯერ მხოლოდ ერთმა ადამიანმა მიიღო მონაწილეობა და ამოხსნილი აქვს სამი ამოცანა (სვეტი "Total"). მისი ჯამური საჯარიმო დრო არის 206 წუთი (სვეტი "Penalty"). მან ამოხსნა ამოცანები A და C პირველ ცდაზე (რასაც შეესაბამება ამ ამოცანების სვეტში დაწერილი პლიუსი), ამოხსნა ამოცანა E მეორე ცდიდან (ამოცანის შესაბამის სვეტში წერია +X, სადაც X წარუმატებელი ცდების რაოდენობაა), გააკეთა სამი წარუმატებელი ცდა ამოცანა D-ზე და ხელი არ მოუკიდებია ამოცანა B-ზე. ამოცანების მიხედვით ჯამური სტატისტიკა შეგიძლიათ ქვემოთ იხილოთ "Total" და "Success" სტრიქონებში.

და ბოლოს, eJudge-ს აქვს ორგანიზატორებთან ურთიერთობის სპეციალური საშუალება. ეს საჭიროა, თუ, მაგალითად, მონაწილეს მიაჩნია, რომ პირობა ცალსახად არ განსაზღვრავს ამოცანას, ან დარწმუნებულია, რომ ტესტები არაკორექტულია, ანაც რავი ბევრი რამე შეიძლება მოიგონო :D რა თქმა უნდა, ჩვენ მაქსიმალურად შევეცდებით, რომ მსგავსი სიტუაციები არ გაჩნდეს, მაგრამ შეცდომა ყველას მოსდის. მაშ ასე, შეკითხვის გასაგზავნად უნდა გადახვიდეთ მენიუში "Submit clar", აირჩიოთ ამოცანა, რომელსაც ეხება თქვენი შეკითხვა (თუ შეკითხვა ზოგადი სახისაა, problem-ში ნურაფერს მიუთითებთ), დაწეროთ შეტყობინების ტექსტი და გააგზავნოთ Send ღილაკზე დაჭერით.

პასუხს თქვენთვის უკვე ნაცნობ "Clars" მენიუში უნდა ელოდოთ. გაითვალისწინეთ, რომ პირობასთან დაკავშირებული შეკითხვებს, რომლებზეც პასუხი ისედაც არის პირობაში, ჩვენგან "Read the problem" პასუხი მოჰყვებათ. თუ თქვენი შეკითხვა საფუძვლიანია, ჩვენ გიპასუხებთ "Yes" ან "No"-ს. ზოგ შემთხვევაში შეიძლება საჭიროდ ჩავთვალოთ უფრო ვრცელი პასუხის გაცემა, ან შეტყობინების პასუხის ყველა მონაწილესთან გაგზავნა.

ამით მოვრჩები eJudge სისტემის აღწერასაც და საერთოდ ამ გვერდსაც. ყველას წარმატებებს გისურვებთ :)