apraksts uzdevumi suutiit jauns statuss rezultati helps apraksts

kodusal Kodu salīdzināšana 1 sek.


 Uzdevums

Firma “Racine Business Networks” (RBN) ir iesūdzējusi tiesā firmu “Heuristic Algorithm Languages” (HAL) apsūdzot, ka HAL ir paņēmusi izejas kodu no RBN UNIXŌ un iekļāvusi to atvērtā koda operāciju sistēmā HALnix.

Gan RBN, gan HAL lieto programmēšanas valodu, kuras instrukcijas pieraksta pa vienai katrā rindā sekojošā formā: STOREA = STOREB + STOREC , kur STOREA, STOREB, un STOREC ir mainīgo nosaukumi. Precīzāk, pirmā mainīgā nosaujums sākas pirmajā kolonnā, tam seko tukšumsimbols, vienādības zīme, tukšumsimbols, otrā mainīgā nosaukums, tukšumsimbols, pluszīme, tukšumsimbols, trešā mainīgā nosaukums. Viena un tā paša mainīgā nosaukums vienā instrukcijā var parādīties vairākkārt. Katra mainīgā nosaukums sastāv no viena līdz astoņiem ASCII tabulas lielajiem burtiem ('A'…'Z').

RBN apsūdz HAL, ka tā ir nokopējusi tieši no RBN programmas izejas koda pēc kārtas esošas koda instrukcijas, izdarot tajās nelielas izmaiņas:

  • RBN apgalvo, ka HAL ir izmainījusi dažu mainīgo vārdus, lai nomaskētu savu noziegumu. Tas ir, ka HAL ir paņēmusi pēc kārtas esošas instrukcijas no RBN programmas, nomainījusi visās kāda mainīgā izmantošanas vietās tā vārdu uz kādu citu. Protams, kāda mainīgā jaunais vārds var būt tāds pats kā kāda mainīgā vecais vārds. Protams, diviem dažādiem mainīgajiem nevar būt vienāds jaunais vārds.
  • Tāpat RBN apgalvo, ka HAL varēja izmainīt dažās instrukcijās labās puses mainīgo kārtību. Piemēram, STOREA = STOREB + STOREC varētu būt aizstāts ar STOREA = STOREC + STOREB.
  • RBN apgalvo, ka HAL nav minījusi instrukciju kārtību RBN izejas kodā.

Dotiem firmu RBN un HAL programmu izejas kodiem nosakiet lielāko, pēc kārtas esošo, instrukciju skaitu HAL programmā, kas varētu būt ņemts no RBN programmas, veicot tajā iepriekšminētos pārveidojumus. Ievērojiet, ka instrukciju virknei abās programmās nav noteikti jāsākas vienā un tajā pašā vietā(rindā ar to pašu numuru).

 
 Ievaddati

Ievaddatu faila kodusal.dat pirmajā rindā doti divi naturāli skaitļi, kas atdalīti ar tukšumsimbolu - R un H (1 ≤ R ≤ 1000; 1 ≤ H ≤ 1000). R ir instrukciju skaits firmas RBN programmas izejas kodā, bet H ir instrukciju skaits firmas HAL programmas izejas kodā.

Nākošajās R faila rindās dota RBN programma.

Nākošajās H faila rindās dota HAL programma

 
 Izvaddati

Izvaddatu faila kodusal.rez vienīgajā rindā jāizvada viens vesels skaitlis, kas ir lielākais pēc kārtas esošo instrukciju skaits, ko HAL varētu būt nokopējušas no RBN un pārveidojušas iepriekš aprakstītajā veidā.

 
 Piemērs

kodusal.datkodusal.rez
4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN + D
HN = HA + HB
2

  Piezīme: RBN programmas pirmajām divām rindām atbilst HAL programmas otrā un trešā rinda, ja pārveidošana notiek šādi: RA uz HM, RB uz D, RC uz HN, D uz HA, RE uz HB. Trīs vai vairāk rindu atbilstības šajā gadījumā nav.

 
 Atsauces
Uzdevums izmantots 15. Vispasaules informātikas olimpiādē IOI'2003 Kenošā(ASV) 2003.gadā

Drukāšanai

 

Copyright © 2001 Girts Folkmanis, LIIS